Benjy Kessler Benjy Kessler - 1 year ago 46
Java Question

Enforcing O(1) get on List

I have a function that chooses a random element of a

and returns it. The list can and is very long (millions of elements) and this function is called thousands of times a second so efficiency is important.

My current implementation looks like:

MyClass getRandomElement(List<MyClass> myClasses) {
return myClasses.get(getRandomNumber(myClasses.size()));

There are two problems with this solution.

  1. List.get
    is not guaranteed to run in
    for example implements it in

  2. size
    is not guaranteed to run in
    on all

The second point is not very cogent because all implementations that I am aware of implement it in
. The first point is the problematic one.

Is there any way to guarantee (not compile/run time exception) that the implementation is
. I thought of changing the interface to:

MyClass getRandomElement(ArrayList<MyClass> myClasses)

This is too strict. I want users to be able to call this function with an
. It is even recommended.

I could assert that the value is an instance of
. This will preclude any other
implementations but I can probably live with it. It is however a runtime enforcement and not a compile time enforcement. And I am not sure what the runtime overhead of this check is.

Is this the best practice?

Answer Source

From the Javadoc of RandomAccess:

Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

Sounds a lot like what you are looking for, provided you can live with a runtime check.

Actually, it looks like you can do this at compile time, using an intersection of generic types:

<T, L extends List<T> & RandomAccess> T getRandomElement(L list) { ... }

getRandomElement(new ArrayList<String>());   // OK.
getRandomElement(new LinkedList<String>());  // Compiler error.