How to make a sorted set with O (1) random access by index

Question

It requires collecting rows in which elements are inserted that need to be sorted, and also not duplicated, can be obtained through the index.

• I can use TreeSet , which removes duplicates and sorts everything in but cannot get through the index. to get index, I can make ArrayList and addAll elements for it, but this addAll takes a lot of time.

or

• I can use ArrayList , insert, and then remove duplicates with another method, and then use the Collections.sort method to sort the items.

But the fact is that all this takes time, are there any direct ways for this, the collection is sorted, not duplicated, with O (1) random access by index.

Answer 1

There is a data type in the collection collection called SetUniqueList, which I believe is appropriate for your needs. Check this:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/SetUniqueList.html

Answer 2

You can use the second idea:

I can use ArrayList, insert the necessary ones and then delete duplicates of another method, then using the Collections.sort method to sort the items.

but instead of deleting duplicates before sorting, you can sort ArrayList , then all duplicates will be located in consecutive positions and can be deleted in one pass subsequently.

At this stage, both methods have the same common complexity: O (N * logN), and it is worth noting that you cannot get a sorted sequence faster than this in any case (without additional exploitation of some knowledge of values).

Answer 3

The real problem here is that the OP did not tell us about the real problem. Thus, many people are aware of data structures and publish answers without even thinking.

The real symptom, as pointed out in an OP comment, is that it takes 700 ms to place the rows in the TreeSet, and another 700 ms to copy this TreeSet to an ArrayList. Obviously, the program does not do what the OP thinks, since the copy should take no more than a few microseconds. In fact, the program below, running on my ancient Thinkpad, only takes 360 ms to create 100,000 random rows, put them in a TreeSet and copy this TreeSet to an ArrayList.

However, the OP chose the answer (twice). Perhaps if / when the OP decides to think about a real problem, this SSCCE example will be useful. He is CW, so feel free to edit it.

---

 import java.lang.management.ManagementFactory; import java.lang.management.ThreadMXBean; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.TreeSet; public class Microbench { public static void main(String[] argv) throws Exception { ThreadMXBean threadBean = ManagementFactory.getThreadMXBean(); long start = threadBean.getCurrentThreadCpuTime(); executeTest(); long finish = threadBean.getCurrentThreadCpuTime(); double elapsed = (finish - start) / 1000000.0; System.out.println(String.format("elapsed time = %7.3f ms", elapsed)); } private static List<String> executeTest() { String[] data = generateRandomStrings(100000); TreeSet<String> set = new TreeSet<String>(); for (String s : data) set.add(s); return new ArrayList<String>(set); } private static String[] generateRandomStrings(int size) { Random rnd = new Random(); String[] result = new String[size]; for (int ii = 0 ; ii < size ; ii++) result[ii] = String.valueOf(rnd.nextLong()); return result; } } 

Answer 4

Performance depends on how often items are added and how often they will be available by index.

I can use TreeSet, which removes duplicates and sorts everything in order, but cannot get through the index. to extract by index, I can make arraylist and addall attributes for it, but this addAll takes a lot of time.

List.addAll (yourSortedSet) will take at least O (n) time and space every time you want to access the SortedSet as a List (i.e. by element index).

I can use ArrayList, insert the necessary ones, and then remove duplicates by another method, and then use the Collections.sort method to sort the items.

sorting will certainly take more O (n) each time you want to sort the presentation of your list.

Another solution

If you often do not select an index, then it is more efficient to do this as follows:

Just saving a String to a SortedSet can be a TreeSet extension and provide / implement your own get(int i) method, where you iterate to the ith element and return that element. In the worst case, it will be O (n); otherwise, it will be much smaller. Thus, you do not perform any comparison or conversion or copying of strings. No more space required.

Answer 5

I'm not sure you are checking the card? I mean using your string as a key in TreeMap.

In Map, this is O (1) for the key to find its position (hash value). And the TreeMap keySet will return a sorted set of keys in TreeMap.

Does this fit your requirements?

Answer 6

If you are attached to the List at the beginning and at the end of the operation, convert it to Set using the "copy" (or addAll ) addAll after filling in the elements, this will remove duplicates. If you convert it to a TreeSet with the corresponding Comparator , it even sorts it. Then you can convert it back to List .

Answer 7

Use a Hashmap, you will solve the problem with unique values ​​and sort it by some sorting methods. If possible, use quicksort.

Answer 8

Perhaps using LinkedList (which takes up less memory than arraylist) with a boolean method that determines whether this item is on the list and the QuickSort algorithm. All structures in java should be sorted somehow and protected from duplicates, I think, therefore, everything takes time ...

Answer 9

There are two ways to do this using LinkedMap, where each element on the map is unique or make your own list and add redefinition method.

 import java.util.ArrayList; public class MyList<V> extends ArrayList<V>{ private static final long serialVersionUID = 5847609794342633994L; public boolean add(V object) { //make each object unique if(contains(object)){ return false; } //you can make here ordering and after save it at position //your ordering here //using extended method add super.add(yourposition,object); } } 

Answer 10

I also ran into the problem of finding an item in a specific place in TreeMap. I enlarged the tree with weights that allow you to access elements by index and find elements in indexes. The project is called indexed-tree-map http://code.google.com/p/indexed-tree-map/ . The implementation for finding the index of an element or element in an index in a sorted map is not based on linear iteration, but on a binary tree search. Updating tree weights is also based on climbing vertically. Therefore, no linear iterations.