performance of Stream.sorted().limit()(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()的性能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本文标题为:Stream.sorted().Limit()的性能
- 在 Java 中,如何将 String 转换为 char 或将 char 转换 2022-01-01
- Eclipse 的最佳 XML 编辑器 2022-01-01
- 如何使 JFrame 背景和 JPanel 透明且仅显示图像 2022-01-01
- GC_FOR_ALLOC 是否更“严重"?在调查内存使用情况时? 2022-01-01
- 如何指定 CORS 的响应标头? 2022-01-01
- 将 Java Swing 桌面应用程序国际化的最佳实践是什么? 2022-01-01
- 转换 ldap 日期 2022-01-01
- java.lang.IllegalStateException:Bean 名称“类别"的 BindingResult 和普通目标对象都不能用作请求属性 2022-01-01
- 获取数字的最后一位 2022-01-01
- 未找到/usr/local/lib 中的库 2022-01-01