执行 O(1) 进入列表

Question

我有一个函数可以选择 List 和 returns 的随机元素。该列表可以而且非常长（数百万个元素）并且此函数每秒调用数千次，因此效率很重要。

我当前的实现如下：

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

这个解决方案有两个问题。

List.get 不保证运行在 O(1)。 LinkedList 例如在 O(n).
size 不能保证 O(1) 在所有 List 实现中运行。

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

有什么方法可以保证（不是 compile/run 时间异常）实现是 O(1)。我想到了将界面更改为：

MyClass getRandomElement(ArrayList<MyClass> myClasses)

这太严格了。我希望用户能够使用 ImmutableList 调用此函数。甚至推荐。

我可以断言该值是 ArrayList 或 ImmutableList 的一个实例。这将排除任何其他 O(1) 实现，但我可能可以接受它。但是，它是运行时间强制执行，而不是编译时强制执行。而且我不确定此检查的运行时间开销是多少。

这是最佳做法吗？

Answer 1

来自 RandomAccess 的 Javadoc：

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.

听起来很像您要找的东西，前提是您可以接受运行时检查。

实际上，您似乎可以在编译时使用交集类型执行此操作：

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

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

这种方法的缺点是您实际上需要知道列表的具体（大概）类型才能调用它。例如，您不能在如下方法中调用 getRandomElement(...)：

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

不需要列表的随机访问属性，除了调用 getRandomElement(strings)。

然后您需要恢复到运行时检查，或者您也需要将通用约束传播到该方法，以及调用该方法的所有内容等。它很快就会变得混乱。

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

Answer 2

你应该仔细考虑限制输入有什么好处，或者你想避免什么样的风险以及你在权衡什么。将参数类型限制为仅允许显式声明的 RandomAccess 列表，意味着您失去了传入由 JRE 方法编辑的任何随机访问列表 return 的能力，即

subList 应用于随机访问列表的结果
由Collections.unmodifiableList或Collections.synchronizedList
由 Arrays.asList
Collections.singletonList(…)。请注意，Collections.emptyList() 也是一个随机访问列表，但这是唯一不适合您的 getRandomElement 方法的列表示例。 nCopies 也是随机访问，但将其传递给 getRandomElement 毫无意义。

所有这些列表将在运行时实现 RandomAccess，但不会在编译时声明。在 Java 7 中，当您知道它实际上是一个随机访问列表时，您甚至无法将列表强制转换为 (List&RandomAccess)。

请注意，即使列表的类型是实现 RandomAccess 的已知实际类型，例如ArrayList，你强制开发人员在整个代码中维护编译时类型，从列表创建到你的方法被调用，而不是使用更抽象的类型，如 List 变量或参数，让单一方法的不灵活性扩展到使用它的所有方法。

所以你牺牲了很多。但是为了什么？

如果开发人员使用没有随机访问的列表并调用您的方法，则性能为 O(n)（即使 size() 和 get() 都是 O(n), 一个接一个地执行两者的净复杂度仍然是 O(n))。这不足为奇。一个操作对于随机访问列表是 O(1) 而对于其他操作是 O(n) 的现象一直存在，包括对于内部操作 List.get 本身。

因此，如果您的方法由于开发人员传入而以 O(n) 时间复杂度执行，例如aLinkedList，问题是开发者的decision of using a LinkedList in the first place。你不应该尝试用你的方法来解决这个问题。

顺便说一下，您可以尝试通过提供适应性实施来降低非随机访问情况的成本，例如：

public static <T> T getRandomElement(List<? extends T> list) {
    Random r = new Random();
    int size;
    if(list instanceof RandomAccess) {
        size = list.size();
        if(size == 0) throw new NoSuchElementException();
        return list.get(r.nextInt(list.size()));
    }
    size = 0;
    T picked = null;
    for(T element: list) {
       if(r.nextInt(++size) == 0) {
           picked = element;
       }
    }
    if(size == 0) throw new NoSuchElementException();
    return picked;
}

这不会改变 O(n) 处理非随机访问列表的性质，因为那是不可能的，它甚至不是 LinkedList 案例的改进 class 有一个 O(1) size() 方法。但是想象一下具有非平凡 size() 方法和弱一致性迭代器的并发列表。在那种情况下，此方法最终将 return 一个随机元素而不是失败。这甚至适用于非 List 集合。如果 get 或 size 的列表碰巧具有更差的复杂性，它也会将复杂性降低到 O(n)，假设合理的 Iterator.

更复杂的操作通常以更简单的方式实现，例如

public static <T> T getRandomElement(List<? extends T> list) {
    if(!(list instanceof RandomAccess)) {
        list = new ArrayList<>(list);
    }
    Random r = new Random();
    int size = list.size();
    if(size == 0) throw new NoSuchElementException();
    return list.get(r.nextInt(list.size()));
}

这将问题减少到一个不可避免的 O(n) 操作（当然，增加了 O(n) space 复杂性）。然后它可以以高效的方式进行，而不需要专门的代码。如果非随机访问列表的网络复杂度比 O(n) 差，这一点至关重要。看看 the implementation of Collections.shuffle 的实际例子。

执行 O(1) 进入列表

Enforcing O(1) get on List

java

collections

java-7