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

Question

我关注从包含几千个元素的 Java PriorityQueue 创建排序数组的不同风格。 Java 8 docs说

If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

但是，我确实喜欢流式 API，所以我最初拥有的是

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

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

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

后一种代码显然更直接地遵循了 API 文档的建议，但除此之外，它是否真的在内存方面更有效率，例如分配的临时结构更少等？

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

而命令式解决方案会将堆元素缓冲到新分配的数组中，然后对它们进行排序。所以这可能少了一次复制操作。 (还有一个数组分配。Collection.toArray(new T[size]) 与 Collection.toArray(new T[0]) 的讨论在这里无关紧要。例如，请参阅 here 了解为什么在 OpenJDK 上后者更快。)

那么排序效率呢？ Arrays.sort() 的文档说

Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays

同时 Stream.sorted() 的文档对这一点保持沉默。因此，至少在可靠记录方面，命令式解决方案似乎具有优势。

但是还有什么要知道的吗？

Answer 1

从根本上说，这两种变体的作用相同，并且由于它们都是库预期用例中的有效解决方案，因此在选择算法或添加优化方面，没有理由认为实现应该优先于另一种。

实际上，这意味着最昂贵的操作(排序)在内部以相同的实现方法结束。 sorted(…) Stream 实现的操作将所有元素缓冲到一个中间数组中，然后调用 Arrays.sort(T[], int, int, Comparator<? super T>) , 它将委托(delegate)给与方法 Arrays.sort(T[], Comparator<? super T>) 相同的方法您在第一个变体中使用，目标是内部 TimSort 中的排序方法类。

所有关于 Arrays.sort 的时间和空间复杂度的讨论适用于 Stream.sort以及。但是虽然有性能差异。对于 Java 10 之前的 OpenJDK 实现，Stream 无法融合 sorted与随后的 toArray步骤，直接使用结果数组进行排序步骤。因此，目前，Stream 变体承担了从用于排序的中间数组到由传递给 toArray 的函数创建的最终数组的最终复制步骤。 .但是 future 的实现可能会学习这个技巧，那么，这两种解决方案之间的相关性能将完全不同。