CODEWITHSUNDEEP
javalistsorting
cypronmaya
cypronmaya

Reputation: 520

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

Need a collection of strings where elements inserted needed to be sorted and also non-duplicate, can be retrieved through index.

or

But the thing is, all these take time, is there any straight-way to achieve this, a collection -sorted, non-duplicate, with O(1) random access by index.

Upvotes: 6

Views: 4642

Answers (10)

Vitaly Sazanovich
Vitaly Sazanovich

Reputation: 694

I also faced the problem of finding element at a certain position in a TreeMap. I enhanced the tree with weights that allow accessing elements by index and finding elements at indexes. The project is called indexed-tree-map https://github.com/geniot/indexed-tree-map . The implementation for finding index of an element or element at an index in a sorted map is not based on linear iteration but on a tree binary search. Updating weights of the tree is also based on vertical tree ascent. So no linear iterations.

Upvotes: 0

Wilmer
Wilmer

Reputation: 1045

There's a Data Type in the commons collection called SetUniqueList that I believe meetsyour needs perfectly. Check it out:

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

Upvotes: 3

pesoklp13
pesoklp13

Reputation: 349

there is two ways to do that use LinkedMap where each element in map is unique or make your own extention of list and override method add 

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);
    }
}

Upvotes: 0

kdgregory
kdgregory

Reputation: 39606

The real problem here is that the OP has not told us the real problem. So lots of people guess at data structures and post answers without really thinking.

The real symptom, as the OP stated in a comment, is that it takes 700ms to put the strings in a TreeSet, and another 700 ms to copy that TreeSet into an ArrayList. Obviously, the program is not doing what the OP thinks it is, as the copy should take at most a few microseconds. In fact, the program below, running on my ancient Thinkpad, takes only 360ms to create 100,000 random strings, put them in a TreeSet, and copy that TreeSet into an ArrayList.

That said, the OP has selected an answer (twice). Perhaps if/when the OP decides to think about the real problem, this example of an SSCCE will be helpful. It's 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;
    }
}

Upvotes: 2

kdabir
kdabir

Reputation: 9868

The performance depends on how frequently the elements are added and how frequently they will be accessed by index.

I can use TreeSet which removes duplicates and sorts everything in order but cannot retrieve through index. for retrieving through index, i can make arraylist and addall elements to it, but this addAll takes lot of time.

List.addAll(yourSortedSet) will take atleast O(n) time and space each time you want to access the SortedSet as List (i.e. by the index of element).

I can use ArrayList,insert required and then remove duplicates by some other method, then using Collections.sort method to sort elements.

sorting will certainly take More than O(n) each time you want a sorted view of your list.

One more solution

If you are not fetching by the index very often then it is more efficient to do it as follows:

Just store Strings in a SortedSet may be extend TreeSet and provide/implement your own get(int i) method where you iterate till the ith element and return that element. In the worst case, this will be O(n) otherwise much lesser. This way you are not performing any comparison or conversion or copying of Strings. No extra space is needed.

Upvotes: 1

Animator
Animator

Reputation: 179

Maybe using LinkedList (which takes less memory than arraylist) with boolean method which determines if that element is already in the list and a QuickSort algorithm. All structures in java have to be somehow sorted and protected from duplicates I think, so everything takes time...

Upvotes: 0

Tudor
Tudor

Reputation: 62469

You can use the second idea:

I can use ArrayList,insert required and then remove duplicates by some other method, then using Collections.sort method to sort elements.

but instead of removing the duplicates before the sort, you could sort the ArrayList first, then all duplicates are on consecutive positions and can be removed in a single pass afterwards.

At this point, both your methods have the same overall complexity: O(N*logN) and it's worth noting that you cannot obtain a sorted sequence faster than this anyway (without additional exploitation of some knowledge about the values).

Upvotes: 2

pesoklp13
pesoklp13

Reputation: 349

Use a Hashmap you will have solved problem with unique values and sort it by some of sorting methods. If it is possible use quicksort.

Upvotes: 0

zeller
zeller

Reputation: 4974

If you are bound to the List at the beginning and the end of the operation, convert it into a Set with the "copy" constructor (or addAll) after the elements are populated, this removes the duplicates. If you convert it into a TreeSet with an appropriate Comparator it'll even sort it. Than, you can convert it back into a List.

Upvotes: 0

julian0zzx
julian0zzx

Reputation: 263

I am not sure, do you test map? I mean use your string as key in a TreeMap.

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

Does this fit your requirement?

Upvotes: 0

Related Questions