Stream.sorted().Limit()的性能 [英] performance of Stream.sorted().limit()

问题描述

Java Streams同时使用sorted和limit方法，这两个方法分别返回流的排序版本和仅返回流中指定数量的项的流。当连续应用这些操作时，如：

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

是以对qty个项目进行排序的方式执行排序，还是对整个列表进行排序？换句话说，如果qty是固定的，那么这个操作在O(n)中吗？文档没有单独指定这些方法的性能，也没有指定它们联合使用的性能。

我问这个问题的原因是，这些操作显然必须实现排序，然后进行限制，这需要时间Θ(n * log(n))。但是这些操作可以一起在O(n * log(qty))中执行，并且智能流框架可以在执行之前查看整个流，以优化此特殊情况。

Java3>

首先让我概括地指出，推荐答案语言规范对如何实现流没有什么限制。因此，询问Java Streams的性能并没有太大的意义：不同的实现之间会有很大差异。

还请注意，Stream是一个接口。您可以创建自己的类来实现Stream，以便对sorted具有您想要的任何性能或特殊行为。因此，即使在一个实现的上下文中，真正询问Stream的性能也毫无意义。OpenJDK实现有很多实现Stream接口的类。

话虽如此，如果我们看一下OpenJDK实现，流的排序最终在SortedOps类中结束(请参阅参考资料here)，您会发现排序方法最终返回有状态操作的扩展。例如：

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

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

因此，由此得出的结论是OpenJDKsorted实现收集所有项，然后排序，然后向下发送。在某些情况下，当下游随后将丢弃某些元素时，这将浪费资源。对于特殊情况，您可以自由实现比这更高效的专用排序操作。可能最直接的方法是实现一个Collector，它保存流中n个最大或最小项的列表。然后，您的操作可能如下所示：

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

替换

.sorted().limit(4)

这篇关于Stream.sorted().Limit()的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！