当前位置: 首页 > 知识库问答 >
问题:

将PriorityQueue转换为排序数组的最佳方法

华献
2023-03-14

我关注的是从包含数千个元素的Java PriorityQueue创建排序数组的不同风格。Java8文档说

如果需要有序遍历,请考虑使用数组。排序(pq.toArray())。

然而,我确实喜欢流式API,所以我最初的想法是

Something[] elems = theHeap.stream().sorted(BY_CRITERION.reversed())
                       .toArray(Something[]::new);

(其中,BY_criteria是PriorityQueue的自定义比较器,我确实想要它的相反顺序。)与下列习惯用法相比,使用这个习惯用法有什么缺点吗

Something[] elems = theHeap.toArray(new Something[0]);
Arrays.sort(elems, BY_CRITERION.reversed());

后面的代码显然更直接地遵循了API文档的建议,但除此之外,它在内存方面真的更有效吗,比如分配的临时结构更少等等。?

我认为流解决方案必须在临时结构(数组?)中缓冲流元素然后对它们进行排序,最后将排序后的元素复制到toArray()中分配的数组中。

而命令式解决方案将把堆元素缓冲在新分配的数组中,然后对它们进行排序。所以这可能会减少一次拷贝操作。(和一个数组分配。Collection.toArray(新的T[size])与Collection的讨论。。toArray(新T[0])在这里是切向相关的。例如,请参阅此处了解为什么在OpenJDK上后者更快。)

而排序效率呢?rrays.sort的医生说

临时存储要求各不相同,从近似排序的输入数组的小常量到随机排序的输入数组的n/2对象引用

而留档的Stream.sorted()在这一点上是沉默的。因此,至少在可靠记录方面,势在必行的解决方案似乎有优势。

但还有什么需要知道的吗?

共有1个答案

傅穆冉
2023-03-14

从根本上说,这两种变体的作用是相同的,因为它们都是库的预期用例中的有效解决方案,所以在选择算法或添加优化方面,实现没有理由选择其中一种。

在实践中,这意味着最昂贵的操作,排序,最终在内部以相同的实现方法结束。流实现的排序(…)操作将所有元素缓冲到一个中间数组中,然后调用数组。排序(T[],int,int,Comparator)

所以关于Arrays.sort的时间和空间复杂性的所有内容也适用于Stream.sort。但是有一个性能差异。对于Java10的OpenJDK实现,Stream无法将排序的与后续的toArray步骤融合,从而直接将结果数组用于排序步骤。因此,目前,Stream变体承担了从用于排序的中间数组到传递给toArray的函数创建的最终数组的最后复制步骤。但是未来的实现可能会学习这个技巧,那么,两个解决方案之间就不会有任何相关的性能差异。

 类似资料:
  • 问题内容: 顾名思义,将字符串数组转换为向量的最佳方法是什么? 谢谢 问题答案: 调用Vector的构造函数,该构造函数使用现有集合(在本例中为数组)初始化自身:

  • 如何将按排序顺序转换为而不更改()?我们希望保留和。 将2,3,1添加到将其排序为1,2,3。从创建一个将具有2,3,1的顺序。中的和方法也将具有2,3,1的顺序。我猜这与的实现有关。

  • 我必须以JSON格式转换数据表单以发送到webAPI。 我有一个从第1页调用的弹出表单: 第1页有以下代码: 输出JSON不正确。代码返回如下字符串: ! DOCTYPE html 什么是最好的方法来字符串化输入数据?我哪里错了?

  • 问题内容: 我有一个我想完全输出为String的。本质上,我想使用由制表符分隔的每个元素按顺序输出。有什么快速的方法可以做到这一点吗?你可以遍历它(或删除每个元素)并将其连接为字符串,但我认为这会非常慢。 问题答案: 基本上,使用循环来迭代是唯一的选择: 不要使用此代码,请继续阅读此答案的底部,以了解为什么不希望使用此代码,以及应该使用哪个代码代替: 实际上,字符串串联就可以了,因为javac编译

  • 我想构建一个Android应用程序,它可以识别语音并将其转换为发音文本(即比较特殊单词和用户语音之间的真实发音或口音)。我只知道可以创建语音到文本。我想转换用户说的任何单词。 有没有API来做?如果没有,请帮助我如何实现它。

  • 问题内容: 除了遍历所述集合的内容并将每个项目手动推入数组之外,是否有更有效的方法将HTMLCollection转换为数组? 问题答案: var arr = Array.prototype.slice.call( htmlCollection ) 使用“本地”代码将具有相同的效果。 编辑 由于这有很多观点,请注意(按@oriol的评论),以下更简洁的表达 实际上 等效: 但是,请注意@JussiR