将 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

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

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

中的排序方法

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

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

Best way to convert a PriorityQueue to a sorted array

java

arrays

sorting

priority-queue

java-stream