Stream.sorted() тогда собирать, или собирать потом List.sort()?
В общем, есть ли разница в производительности между этими двумя частями кода?
List<Integer> list1 = someStream1.sorted().collect(toList());
// vs.
List<Integer> list2 = someStream2.collect(toList());
list2.sort(Comparator.naturalOrder())
Вариант 2 явно отвратителен, и его следует избегать, но мне любопытно, есть ли какие-либо оптимизации производительности, встроенные в основные (хех, основнойпоток) реализации Stream, которые привели бы к разнице в производительности между этими двумя.
Я полагаю, что, поскольку поток содержит строго больше информации о ситуации, у него будет лучшая возможность для оптимизации. Например, я представляю, если бы это было findFirst() колл прикололся, это исключило бы своего рода, в пользу min операция.
5 ответов
Оба варианта должны привести к одному и тому же конечному результату. Но характеристики времени выполнения могут отличаться. Что если исходный поток параллельный? Тогда вариант 1 будет выполнять сортировку параллельно, тогда как вариант 2 не будет выполнять "последовательную" сортировку. Результат должен быть таким же, но общее время выполнения соотв. Тогда загрузка процессора может сильно отличаться.
Я бы определенно предпочел вариант 1, а не 2: зачем сначала создавать список, а потом сортировать его?!
Представьте, например, что вы позже хотите собрать в неизменный список. Тогда весь код, следующий за вашим вторым шаблоном, сломается. Принимая во внимание, что код, написанный с использованием шаблона 1, не будет затронут вообще!
Конечно, в приведенном здесь примере это не должно приводить к проблемам, но что если sort() происходит в немного другом месте?!
В первом случае сортировка происходит при вызове collect, Если поток уже отсортирован, это будет запретом (данные будут просто проходить как есть). Может не иметь большого значения, но звонит Collections.sort в уже отсортированной коллекции все еще O(n).
Также первый случай выигрывает от параллельного выполнения, так как по крайней мере OpenJDK использует Arrays.parallelSort,
Кроме того, первая строка чище, лучше для понимания и менее подвержена ошибкам при рефакторинге.
Концептуально потоки обычно рассматриваются как "временные" данные, которые обрабатываются / обрабатываются, и сбор потока передает представление о том, что вы закончили манипулировать им.
В то время как второй фрагмент должен работать, первый будет более идиоматичным способом выполнения действий.
Согласно документации, похоже, что первая сортировка не является стабильной реализацией сортировки для неупорядоченных потоков:
Для упорядоченных потоков сортировка стабильна. Для неупорядоченных потоков гарантии стабильности не предоставляются.
но вторая - это стабильная реализация сортировки:
Эта реализация представляет собой стабильную, адаптивную, итеративную сортировку слиянием, которая требует гораздо меньше, чем n lg(n) сравнений, когда входной массив частично отсортирован, и в то же время обеспечивает производительность традиционной сортировки слиянием, когда входной массив упорядочен случайным образом. Если входной массив почти отсортирован, реализация требует приблизительно n сравнений.
Таким образом, стабильность алгоритма сортировки является одним из различий между этими двумя методами сортировки списков.
Список, из которого вы вернетесь Collectors.toList() не гарантируется возможность редактирования. Это может быть ArrayList или ImmutableList, вы не можете знать. Поэтому вы не должны пытаться изменить этот список.