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

EN

首先，我要指出的是，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)

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

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

它在内部使用使用 PriorityQueue，对于未排序的输入，它的工作速度要快得多。注意，如果输入大部分是排序的，那么sorted().limit(qty)的工作速度可能会更快，因为对于预置的数据，TimSort非常快。

这取决于实现，也可能取决于流管道是否能够“看穿”sorted()和limit()之间的潜在操作。

即使您要询问OpenJDK实现，它也可能发生更改，因为javadocs无法保证运行时行为。但是没有，目前它还没有实现k-min选择算法.

您还必须记住，除非sorted()已经具有SORTED特性，否则它们不会在无限流上工作。