Set vs List when need both unique elements and access by index

Question

I need to keep a unique list of elements seen and I also need to pick random one from them from time to time. There are two simple ways for me to do this.

1. Keep elements seen in a Set - that gives me uniqueness of elements. When there is a need to pick random one, do the following:

   elementsSeen.toArray()[random.nextInt(elementsSeen.size())]
   

2. Keep elements seen in a List - this way no need to convert to array as there is the get() function for when I need to ask for a random one. But here I would need to do this when adding.

   if (elementsSeen.indexOf(element)==-1) {elementsSeen.add(element);}
   

So my question is which way would be more efficient? Is converting to array more consuming or is indexOf worse? What if attempting to add an element is done 10 or 100 or 1000 times more often?

I am interested in how to combine functionality of a list (access by index) with that of a set (unique adding) in the most performance effective way.

Answer 1

If using more memory is not a problem then you can get the best of both by using both list and set inside a wrapper:

public class MyContainer<T> {
    private final Set<T> set = new HashSet<>();
    private final List<T> list = new ArrayList<>();

    public void add(T e) {
        if (set.add(e)) {
            list.add(e);
        }
    }

    public T getRandomElement() {
        return list.get(ThreadLocalRandom.current().nextInt(list.size()));
    }
    // other methods as needed ...
}

Answer 2

HashSet and TreeSet both extend AbstractCollection, which includes the toArray() implementation as shown below:

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

As you can see, its responsible for allocating the space for an array, as well as creating an Iterator object for copying. So, for a Set, adding is O(1), but retrieving a random element will be O(N) because of the element copy operation.

A List, on the other hand, allows you quick access to a specific index in the backing array, but doesn't guarantee uniqueness. You would have to re-implement the add, remove and associated methods to guarantee uniqueness on insert. Adding a unique element will be O(N), but retrieval will be O(1).

So, it really depends on which area is your potential high usage point. Are the add/remove methods going to be heavily used, with random access used sparingly? Or is this going to be a container for which retrieval is most important, since few elements will be added or removed over the lifetime of the program?

If the former, I'd suggest using the Set with toArray(). If the latter, it may be beneficial for you to implement a unique List to take advantage to the fast retrieval. The significant downside is add contains many edge cases for which the standard Java library takes great care to work with in an efficient manner. Will your implementation be up to the same standards?

Answer 3

Write some test code and put in some realistic values for your use case. Neither of the methods are so complex that it's not worth the effort, if performance is a real issue for you.

I tried that quickly, based on the exact two methods you described, and it appears that the Set implementation will be quicker if you are adding considerably more than you are retrieving, due to the slowness of the indexOf method. But I really recommend that you do the tests yourself - you're the only person who knows what the details are likely to be.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class SetVsListTest<E> {
    private static Random random = new Random();
    private Set<E> elementSet;
    private List<E> elementList;

    public SetVsListTest() {
        elementSet = new HashSet<>();
        elementList = new ArrayList<>();
    }

    private void listAdd(E element) {
        if (elementList.indexOf(element) == -1) {
            elementList.add(element);
        }
    }

    private void setAdd(E element) {
        elementSet.add(element);
    }

    private E listGetRandom() {
        return elementList.get(random.nextInt(elementList.size()));
    }

    @SuppressWarnings("unchecked")
    private E setGetRandom() {
        return (E) elementSet.toArray()[random.nextInt(elementSet.size())];
    }

    public static void main(String[] args) {
        SetVsListTest<Integer> test;
        List<Integer> testData = new ArrayList<>();
        int testDataSize = 100_000;
        int[] addToRetrieveRatios = new int[] { 10, 100, 1000, 10000 };

        for (int i = 0; i < testDataSize; i++) {
            /*
             * Add 1/5 of the total possible number of elements so that we will
             * have (on average) 5 duplicates of each number. Adjust this to
             * whatever is most realistic
             */
            testData.add(random.nextInt(testDataSize / 5));
        }

        for (int addToRetrieveRatio : addToRetrieveRatios) {
            /*
             * Test the list method
             */
            test = new SetVsListTest<>();
            long t1 = System.nanoTime();
            for(int i=0;i<testDataSize; i++) {
                // Use == 1 here because we don't want to get from an empty collection
                if(i%addToRetrieveRatio == 1) {
                    test.listGetRandom();
                } else {
                    test.listAdd(testData.get(i));
                }
            }
            long t2 = System.nanoTime();
            System.out.println(((t2-t1)/1000000L)+" ms for list method with add/retrieve ratio "+addToRetrieveRatio);

            /*
             * Test the set method
             */
            test = new SetVsListTest<>();
            t1 = System.nanoTime();
            for(int i=0;i<testDataSize; i++) {
                // Use == 1 here because we don't want to get from an empty collection
                if(i%addToRetrieveRatio == 1) {
                    test.setGetRandom();
                } else {
                    test.setAdd(testData.get(i));
                }
            }
            t2 = System.nanoTime();
            System.out.println(((t2-t1)/1000000L)+" ms for set method with add/retrieve ratio "+addToRetrieveRatio);
        }
    }
}

Output on my machine was:

819 ms for list method with add/retrieve ratio 10
1204 ms for set method with add/retrieve ratio 10
1547 ms for list method with add/retrieve ratio 100
133 ms for set method with add/retrieve ratio 100
1571 ms for list method with add/retrieve ratio 1000
23 ms for set method with add/retrieve ratio 1000
1542 ms for list method with add/retrieve ratio 10000
5 ms for set method with add/retrieve ratio 10000

Answer 4

You could extend HashSet and track the changes to it, maintaining a current array of all entries.

Here I keep a copy of the array and adjust it every time the set changes. For a more robust (but more costly) solution you could use toArray in your pick method.

class PickableSet<T> extends HashSet<T> {
    private T[] asArray = (T[]) this.toArray();

    private void dirty() {
        asArray = (T[]) this.toArray();
    }

    public T pick(int which) {
        return asArray[which];
    }

    @Override
    public boolean add(T t) {
        boolean added = super.add(t);
        dirty();
        return added;
    }

    @Override
    public boolean remove(Object o) {
        boolean removed = super.remove(o);
        dirty();
        return removed;
    }
}

Note that this will not recognise changes to the set if removed by an Iterator - you will need to handle that some other way.

Answer 5

So my question is which way would be more efficient?

Quite a difficult question to answer depending on what one does more, insert or select at random?

We need to look at the Big O for each of the operations. In this case (best cases):

• Set: Insert O(1)
• Set: toArray O(n) (I'd assume)
• Array: Access O(1)

vs

• List: Contains O(n)
• List: Insert O(1)
• List: Access O(1)

So:

• Set: Insert: O(1), Access O(n)
• List: Insert: O(n), Access O(1)

So in the best case they are much of a muchness with Set winning if you insert more than you select, and List if the reverse is true.

Now the evil answer - Select one (the one that best represents the problem (so Set IMO)), wrap it well and run with it. If it is too slow then deal with it later, and when you do deal with it, look at the problem space. Does your data change often? No, cache the array.

Answer 6

It depends what you value more.

List implementations in Java normally makes use of an array or a linked list. That means inserting and searching for an index is fast, but searching for a specific element will require looping thought the list and comparing each element until the element is found.

Set implementations in Java mainly makes use of an array, the hashCode method and the equals method. So a set is more taxing when you want to insert, but trumps list when it comes to looking for an element. As a set doesn't guarantee the order of the elements in the structure, you will not be able to get an element by index. You can use an ordered set, but this brings with it latency on the insert due to the sort.

If you are going to be working with indexes directly, then you may have to use a List because the order that element will be placed into Set.toArray() changes as you add elements to the Set.

Hope this helps :)