执行O(1)登录列表

Question

我有一个函数,它选择a的随机元素List并返回它.列表可以并且非常长(数百万个元素),并且此函数每秒被调用数千次,因此效率很重要.

我目前的实现如下:

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

此解决方案存在两个问题.

1. List.get不保证可以参加比赛O(1).LinkedList例如,实现它O(n).
2. size不保证O(1)在所有List实现中运行.

第二点不是很有说服力,因为我所知道的所有实现都实现了它O(1).第一点是有问题的.

是否有任何方法可以保证(不是编译/运行时异常)实现O(1).我想把界面改为:

MyClass getRandomElement(ArrayList<MyClass> myClasses)

这太严格了.我希望用户能够使用一个调用此函数ImmutableList.它甚至被推荐.

我可以声明该值是ArrayList或的实例ImmutableList.这将排除任何其他O(1)实现,但我可以忍受它.然而,它是运行时实施而不是编译时执行.我不确定这项检查的运行时开销是多少.

这是最好的做法吗？

Answer 1

来自Javadoc RandomAccess:

鼓励使用通用列表算法来检查给定列表是否是此接口的实例,然后应用将在应用于顺序访问列表时提供较差性能的算法,并在必要时更改其行为以保证可接受的性能.

听起来很像你正在寻找的,只要你能接受运行时检查.

实际上,看起来您可以在编译时使用交集类型执行此操作:

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

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

这种方法的缺点是你实际上需要知道列表的具体(ish)类型才能调用它.例如,您无法调用getRandomElement(...)以下方法:

void doSomethingWithRandomElements(List<String> strings) { ... }

除了调用之外,它不需要列表的随机访问属性getRandomElement(strings).

然后,您需要恢复到运行时检查,或者您也需要将通用约束传播到该方法,并且所有调用该方法等等都会很快变得混乱.

编译时和运行时强制之间的选择在很大程度上取决于您希望如何使用它.