Производительность Stream.sorted(). limit()

Java-потоки поддерживают как методы sorted, так и limit, которые соответственно возвращают отсортированную версию потока и возвращают поток, просто возвращающий указанное количество элементов потока. Когда эти операции применяются последовательно, например:

stream.sorted().limit(qty).collect(Collectors.toList())

сортировка выполняется таким образом, что сортирует элементы qty или сортируется весь список? Другими словами, если qty фиксировано, эта операция выполняется в O(n)? В документации не указывается производительность этих методов отдельно или в сочетании друг с другом.

Причина, по которой я спрашиваю, заключается в том, что очевидной императивной реализацией этих операций было бы сортировать, а затем ограничивать, принимая время Θ(n * log(n)). Но эти операции вместе могут быть выполнены в O(n * log(qty)), а интеллектуальная инфраструктура потоковой передачи может просматривать весь поток до его выполнения, чтобы оптимизировать этот частный случай.

Ответ 1

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

Также обратите внимание, что Stream - это интерфейс. Вы можете создать свой собственный класс, который реализует Stream, чтобы иметь любую производительность или специальное поведение на sorted, которое вы хотите. Так что действительно спрашивать о производительности Stream не имеет смысла даже в контексте одной реализации. В реализации OpenJDK есть много классов, которые реализуют интерфейс Stream.

Сказав, что если мы посмотрим на реализацию OpenJDK, сортировка потоков заканчивается в классе SortedOps (см. источник здесь), вы обнаружит, что методы сортировки в конечном итоге возвращают расширения операций с состоянием. Например:

private static final class OfInt extends IntPipeline.StatefulOp<Integer>

Эти методы проверяют, отсортирован ли верхний поток, в каком случае они просто передают его в нисходящий поток. У них также есть особые исключения для потоковых потоков (то есть вверх по течению), которые предопределяют массивы, которые они сортируют, что улучшит эффективность (более чем SpinedBuffer, которые они используют для неизвестных потоков размера). Но всякий раз, когда восходящий поток еще не отсортирован, они принимают все элементы, затем сортируют их, а затем отправляют в метод accept для последующего экземпляра.

Итак, вывод из этого состоит в том, что реализация OpenJDK sorted собирает все элементы, затем сортирует, а затем отправляет нисходящий поток. В некоторых случаях это будет тратить ресурсы, когда нисходящий поток будет отбрасывать некоторые элементы. Вы можете реализовать свою собственную специализированную операцию сортировки, которая более эффективна, чем это для особых случаев. Вероятно, самым простым способом является реализация Collector, которая хранит список из n самых больших или наименьших элементов в потоке. Ваша операция может выглядеть примерно так:

.collect(new CollectNthLargest(4)).stream()

Чтобы заменить

.sorted().limit(4)

Ответ 2

В моей библиотеке StreamEx есть специальный сборщик, который выполняет эту операцию: MoreCollectors.least(qty):

List<?> result = stream.collect(MoreCollectors.least(qty));

использует PriorityQueue внутри и фактически работает значительно быстрее с небольшим количеством на несортированных входах. Однако обратите внимание, что если ввод в основном отсортирован, то sorted().limit(qty) может работать быстрее, так как TimSort невероятно быстр для предварительных данных.

Ответ 3

Это зависит от реализации и может также зависеть от того, может ли конвейер потока "видеть" потенциальные операции между sorted() и limit().

Даже если вы спросите о реализации OpenJDK, оно может быть изменено, поскольку javadocs не дает никаких гарантий относительно поведения во время выполнения. Но нет, в настоящее время он не реализует алгоритм выбора k-min.

Вы также должны иметь в виду, что sorted() не работает с бесконечными потоками, если у них уже нет атрибута SORTED.