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

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

本文介绍了Stream.sorted().Limit()的性能的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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()的性能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:Stream.sorted().Limit()的性能

基础教程推荐