Benjy Kessler Benjy Kessler - 5 months ago 12
Java Question

Enforcing O(1) get on List

I have a function that chooses a random element of a

List
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
    O(1)
    .
    LinkedList
    for example implements it in
    O(n)
    .

  2. size
    is not guaranteed to run in
    O(1)
    on all
    List
    implementations.



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

Is there any way to guarantee (not compile/run time exception) that the implementation is
O(1)
. 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
ImmutableList
. It is even recommended.

I could assert that the value is an instance of
ArrayList
or
ImmutableList
. This will preclude any other
O(1)
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

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.
Comments