java - collection.stream().skip().findFirst()的效率

Question

假设 set 是一个包含 n 元素的 HashSet 而 k 是一些 int 在 0(含)和 n(不含)之间。

有人可以简单地解释一下当您这样做时实际发生了什么吗？

set.stream().skip(k).findFirst();

具体来说，这个的时间复杂度是多少？将 spliterator() 添加到 Collection 接口(interface)是否意味着我们现在可以比 Java 7 更快地访问集合的“随机”元素？

Answer 1

当前的实现复杂度为 O(k)，更等同于:

Iterator<?> it = set.iterator();
for(int i=0; i<k && it.hasNext(); i++) it.next();
return it.hasNext() ? Optional.of(it.next()) : Optional.empty();

当前的实现从不考虑顺序流的 ORDERED 特性。 @the8472 答案中引用的代码片段仅适用于并行流。在并行情况下，摊销的复杂性大致为 O(k/n)，其中 n 是处理器的数量。