Stream.sorted().limit()的性能

Question

Java流体育运动都sorted和limit方法,它们分别返回流的分类版本,并只返回返回一个流的项目的指定数量的流.当这些操作连续应用时,例如:

stream.sorted().limit(qty).collect(Collectors.toList())

排序是以对项目进行排序qty还是整个列表排序的方式执行的？换句话说,如果qty是固定的,这个操作是在O(n)吗？文档没有单独指定这些方法的性能或相互结合使用.

我问的原因是这些操作的明显必要实现是排序然后限制,花时间?(n * log(n)).但是这些操作可以一起执行,O(n * log(qty))智能流式框架可以在执行之前查看整个流以优化这种特殊情况.

Answer 1

让我首先指出Java语言规范对如何实现流的限制很少.因此,询问Java流的性能真的没有太大意义:它们在实现之间会有很大差异.

另请注意,这Stream是一个界面.您可以创建自己的类,以实现您想要的Stream任何性能或特殊行为sorted.因此,Stream即使在一个实现的上下文中,真正询问性能也毫无意义.OpenJDK实现有很多实现该Stream接口的类.

话虽如此,如果我们看看OpenJDK实现,流的排序最终在SortedOps类中(参见此处的源代码),您会发现排序方法最终返回有状态操作的扩展.例如:

private static final class OfInt extends IntPipeline.StatefulOp<Integer>

这些方法检查上游是否已经排序,在哪种情况下它们只是将它传递给下游.它们对于大小的流(即上游)也有特殊的例外情况,它们预先分配它们最终排序的数组,这将提高效率(超过SpinedBuffer它们用于未知大小的流).但是,只要上游尚未排序,它们就接受所有项目,然后对它们进行排序,然后发送到accept下游实例的方法.

因此得出的结论是,OpenJDK sorted实现收集所有项目,然后进行排序,然后发送到下游.在某些情况下,当下游将丢弃某些元素时,这将浪费资源.对于特殊情况,您可以自由地实现自己的专用排序操作,该操作比此更有效.可能最直接的方法是实现一个Collector保存流中n个最大或最小项的列表.您的操作可能看起来像:

.collect(new CollectNthLargest(4)).stream()

取代

.sorted().limit(4)

Answer 2

我的StreamEx库中有一个特殊的收集器执行此操作MoreCollectors.least(qty)：：

List<?> result = stream.collect(MoreCollectors.least(qty));

它在内部使用PriorityQueue，并且实际上在未排序的输入上以较小的数量运行得更快。但请注意，如果输入大部分已排序，则sorted().limit(qty)可能会工作得更快，因为 TimSort 对于预排序数据来说速度非常快。