流的性能。排序（）。限制（）

Question

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

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

排序是以排序qty项的方式执行的，还是对整个列表进行排序？换句话说，如果qty是固定的，那么这个操作是否在O（n）中？留档不会单独指定这些方法的性能，也不会相互关联指定这些方法的性能。

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

Answer 1

这依赖于实现，也可能取决于流管道是否可以“看穿”排序（）和限制（）之间的潜在操作。

即使您询问OpenJDK实现，它也可能会发生变化，因为Javadoc对运行时行为没有任何保证。但是没有，目前它没有实现k-min选择算法。

您还必须记住，sorted（）不适用于无限流，除非它们已经具有sorted特性。

Answer 2

我的StreamEx库中有一个特殊的收集器执行此操作：MoreCollectors。最少（数量）：

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

它在内部使用PriorityQueue，在未排序的输入上使用小数量时，实际工作速度明显更快。但是请注意，如果输入大部分是排序的，则sorted（）。限制（数量）可能工作得更快，因为TimSort对于预排序数据的速度非常快。

Answer 3

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

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

话虽如此，如果我们看一下OpenJDK实现，流的排序结果是SortedOps类（参见这里的源代码），您会发现排序方法最终返回有状态操作的扩展。例如：

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

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

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

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

来代替

.sorted().limit(4)