Лучший способ преобразовать PriorityQueue в отсортированный массив - PullRequest
Новая
       6

Лучший способ преобразовать PriorityQueue в отсортированный массив

0 голосов
/ 28 июня 2018

Меня интересуют разные стили создания отсортированного массива из Java PriorityQueue, содержащей несколько тысяч элементов. Java 8 документов скажем

Если вам нужен упорядоченный обход, рассмотрите возможность использования 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 doc, но кроме этого, действительно ли он более эффективен с точки зрения памяти, например, когда выделяется меньше временных структур и т. Д.?

Я бы подумал, что потоковое решение должно будет буферизовать элементы потока во временной структуре (массив?), А затем отсортировать их и, наконец, скопировать отсортированные элементы в массив, выделенный в toArray().

Хотя императивное решение буферизует элементы кучи во вновь выделенном массиве, а затем сортирует их. Так что это может быть на одну операцию копирования меньше. (И одно выделение массива. Обсуждение Collection.toArray(new T[size]) против Collection.toArray(new T[0]) здесь тангенциально связано. Например, см. здесь , чтобы узнать, почему в OpenJDK последний работает быстрее.)

А как насчет эффективности сортировки? Документы Arrays.sort () скажем

Требования к временному хранилищу варьируются от небольшой константы для почти отсортированных входных массивов до n / 2 ссылок на объекты для произвольно упорядоченных входных массивов

пока документация Stream.sorted() об этом молчит. Так что, по крайней мере, с точки зрения надежности документирования, императивное решение, похоже, имеет преимущество.

Но что еще нужно знать?

1 Ответ

0 голосов
/ 28 июня 2018

По сути, оба варианта выполняют одно и то же, и, поскольку оба являются допустимыми решениями в предполагаемых случаях использования библиотеки, нет причин, по которым реализации должны отдавать предпочтение одному из других в отношении выбора алгоритмов или добавления оптимизаций.

На практике это означает, что самая дорогая операция, сортировка, заканчивается внутри тех же методов реализации. Операция sorted(…) реализации Stream буферизует все элементы в промежуточный массив с последующим вызовом Arrays.sort(T[], int, int, Comparator<? super T>), который делегирует тот же метод, что и метод Arrays.sort(T[], Comparator<? super T>), который вы используете в первом варианте, цель - метод сортировки во внутреннем TimSort классе.

Таким образом, все, что было сказано о сложности времени и пространства для Arrays.sort, относится и к Stream.sort. Но есть разница в производительности. Для реализаций OpenJDK вплоть до Java 10 Stream не может объединить sorted с последующим шагом toArray, чтобы напрямую использовать массив результатов для этапа сортировки. Таким образом, в настоящее время вариант Stream переносит последний шаг копирования из промежуточного массива, используемого для сортировки, в окончательный массив, созданный функцией, переданной в toArray. Но будущие реализации могут усвоить этот трюк, и тогда между этими двумя решениями не будет существенной разницы в производительности.

...