Чем stream отличается от итератора java
Перейти к содержимому

Чем stream отличается от итератора java

  • автор:

Обход элементов в Java 8 stream: аналог Continue в forEach

Для ручного перехода между элементами потока можно использовать итератор. Он предлагает управляющие методы, вроде next(). В отличие от forEach, этот инструмент предоставляет больше контроля над итерациями.

Скопировать код

Iterator it = myStream.iterator(); while(it.hasNext()) < YourType item = it.next(); // Обработка элемента >

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

Лямбды в контексте Java

В лямбда-выражениях forEach команда return не останавливает цикл, а лишь прекращает обработку текущего элемента. Каждый элемент обрабатывается лямбдами как отдельный метод.

Скопировать код

list.stream().forEach(item -> < if (item.isSkipWorthy()) < // Запрос на пропуск элемента return; // Выход только из обработки текущего элемента >// Продолжение обработки >);

Здесь return выполняет функцию, аналогичную continue в обычных for и while циклах, но только в рамках лямбды.

Отсев элементов: плюсы, минусы и подводные камни

Метод filter предлагает возможность применения логики continue в инвертированном виде.

Скопировать код

list.stream().filter(item -> !item.isSkipWorthy()).forEach(item -> < // Обработка только принятых элементов >);

С применением обратной логики (!condition) в условии вы сможете сосредоточиться на элементах, которые соответствуют вашему условию.

Улучшение читаемости кода

Превращение лямбд в явные методы усовершенствовывает читаемость и упрощает управление кодом.

Скопировать код

list.stream().forEach(this::itemProcessor); // Метод-ссылка private void itemProcessor(YourType item) < if (item.needsEarlyExit()) < return; // Только выход из текущей обработки >// Продолжение выполнения >

В данном случае вполне очевидно, что return означает больше похож на небольшой перерыв, а не окончательный выход.

Всемогущий takeWhile

В Java 9 был добавлен метод takeWhile, который прекращает обработку элементов, как только встречает условие.

Скопировать код

list.stream().takeWhile(item -> !item.stopOmeterReadingHigh()).forEach(this::itemProcessor);

С помощью takeWhile можно прекратить выполнение при условии, которое было задано.

Старшые методы все еще в строю!

Когда работа с потоками становится излишне сложной, вы всегда можете использовать обычные циклы с предварительной фильтрацией списка:

Скопировать код

List VIPsOnly = list.stream() .filter(item -> !item.isSkipWorthy()) .collect(Collectors.toList()); for (YourType item : VIPsOnly) < // Здесь можно все: break, continue и даже изменять индекс цикла за чашкой кофе. >

Классический цикл for-each возвращает объекту полный контроль над итерацией.

Визуализация

Поток можно представить как автобус, перевозящий элементы:

Скопировать код

stream.forEach(item -> < System.out.println("Посетитель: " + item); // Билеты только в один конец, нет выходов и пропусков. >);

Маршрут:

Первая остановка: �� (Наслаждаемся, без пропусков) Следующая остановка: �� (Хотелось бы пропустить, но у forEach нет такой функции) Конечная остановка: �� (Нет прямого пути к финишу)

Как бы мы не хотели сделать пересадку или выйти на определенной станции, потоки не предусматривают такой возможности ����

Объяснение при применении своего итератора

Для реализации сложных итераций вы можете применить свой итератор:

Скопировать код

StreamEx.of(list).forEachIndexed((index, item) -> < if (itsASkipDay(item, index)) < return; // Действует как continue, готовы к следующему шагу >// Начало обработки элементов >);

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

При использовании «поточной» обработки

Прежде чем воспользоваться потоками, рассмотрите следующие советы:

  1. Сложные сценарии с вложенными циклами: Здесь обычные циклы могут быть эффективнее.
  2. Множественные состояния или условия: Потоки могут лишь усложнить код.
  3. Тоска по break или continue: Вероятно, вам стоит вернуться к классическим методам.

Замечания по использованию потоков и их альтернатив

Будьте внимательны с потоками:

  • Параллельные потоки: Они не гарантируют порядок выполнения для forEach.
  • Состояние лямбд: Изменение состояния внутри лямбды может привести к неожиданному поведению.

Возможные альтернативы:

  • flatMap, map, reduce: Используйте эти методы или библиотеку StreamEx для реализации сложных сценариев итерации.

Полезные материалы

  1. Oracle JavaDocs: Stream Interface — подробно о Stream API от Oracle.
  2. Break or return from Java 8 stream forEach? — обсуждение возможностей прерывания или выхода из stream.forEach.
  3. Java Stream findFirst() with Example — шаг за шагом об использовании findFirst в потоках.

Цикл foreach против Iterable.foreach в Java 8: что лучше?

У меня есть много циклов, которые могут быть упрощены с помощью лямбд, но есть ли какие-то реальные преимущества от использования Iterator.foreach ? Улучшится ли производительность и читабельность кода?

Отслеживать
Anton Sorokin
задан 22 фев 2019 в 8:33
Anton Sorokin Anton Sorokin
6,998 6 6 золотых знаков 37 37 серебряных знаков 65 65 бронзовых знаков
ассоциация: stackoverflow.com/questions/16635398/…
22 фев 2019 в 12:40

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

С точки зрения производительности нет никаких обещанных заметных преимуществ от использования Iterable.forEach по сравнению с foreach .

Performs the given action on the contents of the Iterable, in the order elements occur when iterating, until all elements have been processed or the action throws an exception.

Т.е. понятно, что не будет никакого явного параллелизма. Добавление параллелизма будет нарушением LSP.

Про читабельность кода: вы вероятно используете Iterable.foreach только с короткими однострочными лямбдами. Если «тело» лямбды увеличится, то читабельность скорее всего будет хуже, чем в цикле.

Примечание: этот ответ работает при использовании StreamAPI . Если используется только java.util.Iterable , то этот ответ перестает работать.

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

list.parallelStream().forEach(e -> e.operation); 

Однако использование не-параллельных стримов при обработке малого количества данных будет дольше, чем foreach и циклы.

Вывод:

  1. Между Iterable.foreach и циклом foreach в производительности разницы нет.
  2. Если тело лямбды будет небольшим, то лучше использовать Iterable.foreach .
  3. Если вы хотите прирост в производительности, то вам лучше использовать parallelStream.foreach() .

Разница между Collection.stream().forEach() и Collection.forEach()

В большинстве случаев оба дадут одинаковые результаты, но мы рассмотрим некоторые тонкие различия.

2. Простой список​

Во-первых, давайте создадим список для повторения:

 ListString> list = Arrays.asList("A", "B", "C", "D"); 

Самый простой способ — использовать расширенный цикл for:

 for(String s : list)    //do something with s   > 

Если мы хотим использовать Java в функциональном стиле, мы также можем использовать forEach() .

Мы можем сделать это непосредственно в коллекции:

 ConsumerString> consumer = s ->  System.out::println >;  list.forEach(consumer); 

Или мы можем вызвать forEach() для потока коллекции:

 list.stream().forEach(consumer); 

Обе версии будут перебирать список и печатать все элементы:

ABCD ABCD 

В этом простом случае не имеет значения, какую функцию forEach() мы используем.

3. Порядок исполнения​

Collection.forEach() использует итератор коллекции (если он указан), поэтому определяется порядок обработки элементов. Напротив, порядок обработки Collection.stream().forEach() не определен.

В большинстве случаев не имеет значения, какой из двух мы выберем.

3.1. Параллельные потоки​

Параллельные потоки позволяют нам выполнять поток в несколько потоков, и в таких ситуациях порядок выполнения не определен. Java требует только завершения всех потоков перед вызовом какой-либо терминальной операции, такой как Collectors.toList() .

Давайте рассмотрим пример, в котором мы сначала вызываем forEach() непосредственно для коллекции, а затем — для параллельного потока:

 list.forEach(System.out::print);   System.out.print(" ");  list.parallelStream().forEach(System.out::print); 

Если мы запустим код несколько раз, то увидим, что list.forEach() обрабатывает элементы в порядке вставки, а list.parallelStream().forEach() выдает разные результаты при каждом запуске.

Вот один из возможных выходов:

 ABCD CDBA 
 ABCD DBCA 

3.2. Пользовательские итераторы​

Давайте определим список с пользовательским итератором для перебора коллекции в обратном порядке:

 class ReverseList extends ArrayListString>     @Override   public IteratorString> iterator()     int startIndex = this.size() - 1;   ListString> list = this;    IteratorString> it = new IteratorString>()     private int currentIndex = startIndex;    @Override   public boolean hasNext()    return currentIndex >= 0;   >    @Override   public String next()    String next = list.get(currentIndex);   currentIndex--;   return next;   >    @Override   public void remove()    throw new UnsupportedOperationException();   >   >;   return it;   >   > 

Затем мы снова пройдемся по списку с помощью forEach() непосредственно в коллекции, а затем в потоке:

 ListString> myList = new ReverseList();  myList.addAll(list);   myList.forEach(System.out::print);   System.out.print(" ");  myList.stream().forEach(System.out::print); 

И получаем разные результаты:

 DCBA ABCD 

Причина разных результатов заключается в том, что forEach() , используемый непосредственно в списке, использует пользовательский итератор, а stream().forEach() просто берет элементы из списка один за другим, игнорируя итератор.

4. Модификация коллекции​

Многие коллекции (например , ArrayList или HashSet ) не должны изменяться структурно при их повторении. Если элемент будет удален или добавлен во время итерации, мы получим исключение ConcurrentModification .

Кроме того, коллекции рассчитаны на быстрый сбой, а это означает, что исключение генерируется, как только происходит модификация.

Точно так же мы получим исключение ConcurrentModification при добавлении или удалении элемента во время выполнения потокового конвейера. Однако исключение будет выброшено позже.

Еще одно тонкое различие между двумя методами forEach() заключается в том, что Java явно позволяет изменять элементы с помощью итератора. Потоки, напротив, не должны мешать друг другу.

Рассмотрим удаление и изменение элементов более подробно.

4.1. Удаление элемента​

Давайте определим операцию, которая удаляет последний элемент («D») нашего списка:

 ConsumerString> removeElement = s ->    System.out.println(s + " " + list.size());   if (s != null && s.equals("A"))    list.remove("D");   >   >; 

Когда мы перебираем список, последний элемент удаляется после того, как напечатан первый элемент («A»):

 list.forEach(removeElement); 

Поскольку forEach() работает без сбоев, мы останавливаем итерацию и видим исключение перед обработкой следующего элемента :

 A 4   Exception in thread "main" java.util.ConcurrentModificationException   at java.util.ArrayList.forEach(ArrayList.java:1252)   at ReverseList.main(ReverseList.java:1) 

Давайте посмотрим, что произойдет, если вместо этого мы используем stream().forEach() :

 list.stream().forEach(removeElement); 

Здесь мы продолжаем перебирать весь список, прежде чем увидим исключение :

 A 4   B 3   C 3   null 3   Exception in thread "main" java.util.ConcurrentModificationException   at java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1380)   at java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:580)   at ReverseList.main(ReverseList.java:1) 

Однако Java не гарантирует, что исключение ConcurrentModificationException будет выброшено вообще. Это означает, что мы никогда не должны писать программу, зависящую от этого исключения.

4.2. Изменение элементов​

Мы можем изменить элемент во время итерации по списку:

 list.forEach(e ->    list.set(3, "E");   >); 

Но хотя нет проблем с выполнением этого с помощью Collection.forEach() или stream().forEach() , Java требует, чтобы операция над потоком не мешала. Это означает, что элементы не должны изменяться во время выполнения потокового конвейера.

Причина этого в том, что поток должен способствовать параллельному выполнению. Здесь изменение элементов потока может привести к неожиданному поведению.

5. Вывод​

В этой статье мы видели несколько примеров, которые показывают тонкие различия между Collection.forEach() и Collection.stream().forEach() .

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

Если нам не нужен поток, а нужно только перебирать коллекцию, первым выбором должно быть использование forEach() непосредственно в коллекции.

Исходный код примеров из этой статьи доступен на GitHub .

  • 1. Обзор
  • 2. Простой список
  • 3. Порядок исполнения
    • 3.1. Параллельные потоки
    • 3.2. Пользовательские итераторы
    • 4.1. Удаление элемента
    • 4.2. Изменение элементов

    Пишем свой Spliterator

    Многие из вас уже попробовали на вкус Stream API — потоки Java 8. Наверняка у некоторых возникло желание не только пользоваться готовыми потоками от коллекций, массивов, случайных чисел, но и создать какой-то принципиально новый поток. Для этого вам потребуется написать свой сплитератор. Spliterator — это начинка потока, публичная часть его внутренней логики. В этой статье я расскажу, как и зачем я писал сплитератор.

    Что же такое сплитератор

    Сплитератор — это интерфейс, который содержит 8 методов, причём четыре из них уже имеют реализацию по умолчанию. Оставшиеся методы — это tryAdvance , trySplit , estimateSize и characteristics . Существуют также специальные модификации сплитератора для примитивных типов int , long и double : они добавляют несколько дополнительных методов, чтобы избежать боксинга. Сплитератор похож на обычный итератор. Основное отличие — умение разделиться (split) на две части — лежит в основе параллельной работы потоков. Также в целях оптимизации сплитератор имеет ряд флагов-характеристик и может сообщить точно или приблизительно свой размер. Наконец, сплитератор никогда не модифицирует источник данных: у него нет метода remove как у итератора. Рассмотрим методы подробнее:

    • tryAdvance(Consumer) — объединение методов итератора hasNext() и next() . Если у сплитератора есть следующий элемент, он должен вызвать переданную функцию с этим элементом и вернуть true , иначе функцию не вызывать и вернуть false .
    • trySplit() — попытаться поделиться надвое. Метод возвращает новый сплитератор, который будет пробегать по первой половине исходного набора данных, при этом сам текущий сплитератор перепрыгивает на вторую половину. Лучше всего, когда половины примерно равны, но это не обязательно. Особенно неравномерно делятся сплитераторы с бесконечным набором данных: после деления один из сплитераторов обрабатывает конечный объём, а второй остаётся бесконечным. Метод trySplit() имеет законное право не делиться и вернуть null (не случайно там try). Обычно это делается, когда в текущем сплитераторе осталось мало данных (скажем, только один элемент).
    • characteristics() — возвращает битовую маску характеристик сплитератора. Их на данный момент восемь:
      1. ORDERED — если порядок данных имеет значение. К примеру, сплитератор от HashSet не имеет этой характеристики, потому что порядок данных в HashSet зависит от реализации. Отсутствие этой характеристики автоматически переведёт параллельный поток в неупорядоченный режим, благодаря чему он сможет работать быстрее. Раз в источнике данных порядка не было, то и дальше можно за ним не следить.
      2. DISTINCT — если элементы заведомо уникальны. Любой Set или поток после операции distinct() создаёт сплитератор с такой характеристикой. Например, операция distinct() на потоке из Set выполняться не будет вообще и, стало быть, времени лишнего не займёт.
      3. SORTED — если элементы сортированы. В таком случае обязательно вернуть и ORDERED и переопределить метод getComparator() , вернув компаратор сортировки или null для «естественного порядка». Сортированные коллекции (например, TreeSet ) создают сплитератор с такой характеристикой, и с ней потоковая операция sorted() может быть пропущена.
      4. SIZED — если известно точное количество элементов сплитератора. Такую характеристику возвращают сплитераторы всех коллекций. После некоторых потоковых операций (например, map() или sorted() ) она сохраняется, а после других (скажем, filter() или distinct() ) — теряется. Она полезна для сортировки или, скажем, операции toArray() : можно заранее выделить массив нужного размера, а не гадать, сколько элементов понадобится.
      5. SUBSIZED — если известно, что все дочерние сплитераторы также будут знать свой размер. Эту характеристику возвращает сплитератор от ArrayList , потому что при делении он просто разбивает диапазон значений на два диапазона известной длины. А вот HashSet её не вернёт, потому что он разбивает хэш-таблицу, для которой не известно, сколько содержится элементов в каждой половине. Соответственно дочерние сплитераторы уже не будут возвращать и SIZED.
      6. NONNULL — если известно, что среди элементов нет null . Эту характеристику возвращает, например, сплитератор, созданный ConcurrentSkipListSet : в эту структуру данных null поместить нельзя. Также её возвращают все сплитераторы, созданные на примитивных типах.
      7. IMMUTABLE — если известно, что источник данных в процессе обхода заведомо не может измениться. Сплитераторы от обычных коллекций такую характеристику не возвращают, но её выдаёт, например, сплитератор от Collections.singletonList() , потому что этот список изменить нельзя.
      8. CONCURRENT — если известно, что сплитератор остаётся рабочим после любых изменений источника. Такую характеристику сообщают сплитераторы коллекций из java.util.concurrent . Если сплитератор не имеет характеристик IMMUTABLE и CONCURRENT, то хорошо бы заставить его работать в fail-fast режиме, чтобы он кидал ConcurrentModificationException , если заметит, что источник изменился.

      Насколько мне известно, последние три характеристики сейчас потоками никак не используются (в том числе в коде Java 9).

    • estimateSize() — метод должен возвращать количество оставшихся элементов для SIZED-сплитераторов и как можно более точную оценку в остальных случаях. Например, если мы создадим сплитератор от HashSet и разделим его с помощью trySplit() , estimateSize() будет возвращать половину от исходного размера коллекции, хотя реальное количество элементов в половине хэш-таблицы может отличаться. Если элементов бесконечное количество или посчитать их слишком трудозатратно, можно вернуть Long.MAX_VALUE .

    Когда сплитератор писать не надо

    Главное понимать, что сам по себе сплитератор вам не нужен, вам нужен поток. Если вы можете создать поток, используя существующий функционал, то стоит сделать именно так. К примеру, хотите вы подружить потоки с XML DOM и создавать поток по NodeList . Стандартного такого метода нет, но его легко написать без дополнительных сплитераторов:

    public class XmlStream < static Streamof(NodeList list) < return IntStream.range(0, list.getLength()).mapToObj(list::item); >>

    Аналогично можно добавить потоки к любой нестандартной коллекции (ещё пример — org.json.JSONArray ), которая умеет быстро вернуть длину и элемент по порядковому номеру.

    Если вам трудно или лень писать trySplit , лучше не пишите сплитератор вообще. Вот один товарищ пишет библиотеку protonpack, полностью игнорируя существование параллельных потоков. Он написал много сплитераторов, которые вообще не умеют делиться. Сплитератор, который вообще не делится — это плохой, негодный сплитератор. Не делайте так. В данном случае лучше написать обычный итератор и создать по нему сплитератор с помощью методов Spliterators.spliterator или, если вам заранее неизвестен размер коллекции, то Spliterators.spliteratorUnknownSize. Эти методы имеют хоть какую-то эвристику для деления: они обходят часть итератора, вычитывая его в массив и создавая новый сплитератор для этого массива. Если в потоке будет дальше длительная операция, то распараллеливание всё равно ускорит работу.

    Если вы реализуете стандартный интерфейс Iterable или Collection , то вам совершенно бесплатно выдаётся default -метод spliterator() . Стоит, конечно, посмотреть, нельзя ли его улучшить. Так или иначе, свои сплитераторы требуется писать весьма редко. Это может пригодиться, если вы разрабатываете свою структуру данных (например, коллекцию на примитивах, как делает leventov).

    И всё-таки напишем

    Мы напишем новый сплитератор для решения такой задачи: по заданному потоку создать поток пар из соседних значений исходного потока. Так как общепринятого типа для представления пары значений в Java нет и возможных вариантов слишком много (использовать массив из двух значений, список из двух значений, Map.Entry с одинаковым типом ключа и значения и т. д.), мы отдадим это на откуп пользователю: пусть сам решает, как объединить два значения. То есть мы хотим создать метод с такой сигнатурой:

    public static Stream pairMap(Stream stream, BiFunction mapper)

    С его помощью можно использовать любой тип для представления пары. Например, если мы хотим Map.Entry :

    public static Stream> pairs(Stream stream) < return pairMap(stream, AbstractMap.SimpleImmutableEntry::new); >

    А можно вообще сразу вычислить что-нибудь интересное, не складывая пары в промежуточный контейнер:

    public static Stream diff(Stream stream) < return pairMap(stream, (a, b) ->b - a); >

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

    Мы хотим, чтобы наш pairMap выглядел как обычная промежуточная (intermediate) операция, то есть фактически никаких вычислений производиться не должно, пока дело не дойдёт до терминальной операции. Для этого надо взять spliterator у входного потока, но ничего с ним не делать, пока нас не попросят. Ещё одна маленькая, но важная вещь: при закрытии нового потока через close() надо закрыть исходный поток. В итоге наш метод может выглядеть так:

    public static Stream pairMap(Stream stream, BiFunction mapper) < return StreamSupport.stream(new PairSpliterator<>(mapper, stream.spliterator()), stream.isParallel()).onClose(stream::close); >

    Исходный поток после вызова метода spliterator() становится «использованным», с ним больше каши не сваришь. Но это нормально: так происходит со всеми промежуточными потоками, когда вы добавляете новую операцию. Метод Stream.concat(), склеивающий два потока, выглядит примерно так же. Осталось написать сам PairSpliterator .

    Переходим к сути дела

    Самое простое — это написать метод characteristics() . Часть характеристик наследуется у исходного сплитератора, но необходимо сбросить NONNULL, DISTINCT и SORTED: мы не можем гарантировать этих характеристик после применения произвольной mapper-функции:

    public int characteristics()

    Реализация метода tryAdvance должна быть довольно простой. Надо лишь вычитывать данные из исходного сплитератора, запоминая предыдущий элемент в промежуточном буфере, и вызывать для последней пары mapper . Стоит только помнить, находимся мы в начале потока или нет. Для этого пригодится булева переменная hasPrev , указывающая, есть ли у нас предыдущее значение.

    Метод trySplit лучше всего реализовать, вызвав trySplit у исходного сплитератора. Основная сложность тут — обработать пару на стыке двух разделённых кусков исходного потока. Эту пару должен обработать сплитератор, который обходит первую половину. Соответственно, он должен хранить первое значение из второй половины и, когда доберётся до конца, сработать ещё раз, подав его в mapper вместе с последним своим значением.

    Разобравшись с этим, напишем конструкторы:

    class PairSpliterator implements Spliterator  < Spliteratorsource; boolean hasLast, hasPrev; private T cur; private final T last; private final BiFunction mapper; public PairSpliterator(BiFunction mapper, Spliterator source) < this(mapper, source, null, false, null, false); >public PairSpliterator(BiFunction mapper, Spliterator source, T prev, boolean hasPrev, T last, boolean hasLast) < this.source = source; // исходный сплитератор this.hasLast = hasLast; // есть ли дополнительный элемент в конце (первый из следующего куска) this.hasPrev = hasPrev; // известен ли предыдущий элемент this.cur = prev; // предыдущий элемент this.last = last; // дополнительный элемент в конце this.mapper = mapper; >// . >

    Метод tryAdvance (вместо лямбды для передачи в исходный tryAdvance воспользуемся ссылкой на сеттер):

    void setCur(T t) < cur = t; >@Override public boolean tryAdvance(Consumer action) < if (!hasPrev) < // мы в самом начале: считаем один элемент из источника if (!source.tryAdvance(this::setCur)) < return false; // источник вообще пустой — выходим >hasPrev = true; > T prev = cur; // запоминаем предыдущий элемент if (!source.tryAdvance(this::setCur)) < // вычитываем следующий из источника if (!hasLast) return false; // совсем всё закончилось — выходим hasLast = false; // обрабатываем пару на стыке двух кусков cur = last; >action.accept(mapper.apply(prev, cur)); // передаём в action результат mapper'а return true; >

    А вот и метод trySplit() :

    public Spliterator trySplit() < SpliteratorprefixSource = source.trySplit(); // пытаемся разделить источник if (prefixSource == null) return null; // не вышло — тогда мы сами тоже не делимся T prev = cur; // это последний считанный до сих пор элемент, если он вообще был if (!source.tryAdvance(this::setCur)) < // вычитываем первый элемент второй половины source = prefixSource; // вторая половина источника оказалась пустой — смысла делиться нет return null; >boolean oldHasPrev = hasPrev; hasPrev = true; // теперь текущий сплитератор обходит вторую половину, а для первой создаём новый return new PairSpliterator<>(mapper, prefixSource, prev, oldHasPrev, cur, true); >

    Написать estimateSize() несложно: если исходный сплитератор способен оценить свой размер, надо лишь проверить флаги и подправить его на единичку туда или обратно:

    public long estimateSize() < long size = source.estimateSize(); if (size == Long.MAX_VALUE) // источник не смог оценить свой размер — мы тоже не можем return size; if (hasLast) // этот сплитератор будет обрабатывать дополнительную пару на стыке кусков size++; if (!hasPrev && size >0) // этот сплитератор ещё не вычитал первый элемент size--; return size; >

    В подобном виде этот сплитератор и попал в мою библиотеку StreamEx. Отличие только в том, что потребовалось сделать версии для примитивных типов, ну и pairMap — это не статический метод.

    Всё это, небось, сильно тормозит?

    Со скоростью всё не так плохо. Возьмём для примера вот такую задачу со StackOverflow: из заданного набора чисел Integer оставить только те, которые меньше следующего за ними числа, и сохранить результат в новый список. Сама по себе задача очень простая, поэтому существенная часть времени будет уходить на оверхед. Можно предложить две наивные реализации: через итератор (будет работать с любой коллекцией) и через доступ по номеру элемента (будет работать только со списком с быстрым случайным доступом). Вот вариант с итератором (naiveIterator):

    List result = new ArrayList<>(); Integer last = null; for (Integer cur : input)

    А вот со случайным доступом (naiveGet):

    List result = new ArrayList<>(); for (int i = 0; i

    Решение с помощью библиотеки StreamEx очень компактно и работает с любым источником данных (streamEx):

    List result = StreamEx.of(input).pairMap((a, b) -> a < b ? a : null).nonNull().toList();

    Комментаторами было предложено ещё три работающих решения. Наибольшее число голосов набрало более-менее традиционное, которому на входе требуется список со случайным доступом (назовём это решение stream):

    List result = IntStream.range(0, input.size() - 1).filter(i -> input.get(i) < input.get(i + 1)).mapToObj(input::get) .collect(Collectors.toList());

    Следующее — это reduce с побочным эффектом, который не параллелится (reduce):

    List result = new ArrayList<>(); input.stream().reduce((a, b) -> < if (a < b) result.add(a); return b; >);

    И последнее — это свой коллектор, который также не параллелится (collector):

    public static Collector> collectPrecedingValues() < int[] holder = < Integer.MAX_VALUE >; return Collector.of(ArrayList::new, (l, elem) -> < if (holder[0] < elem) l.add(holder[0]); holder[0] = elem; >, (l1, l2) -> < throw new UnsupportedOperationException("Don't run in parallel"); >); > List result = input.stream().collect(collectPrecedingValues());

    В сравнение также попадают распараллеленные версии stream и streamEx. Опыт будем проводить на массивах случайных целых чисел длиной n = 10 000, 100 000 и 1 000 000 элементов (в результат попадёт порядка половины). Полный код JMH-бенчмарка здесь. Проверено, что все алгоритмы выдают одинаковый результирующий массив.

    Замеры проводились на четырёхъядерном Core-i5. Результаты выглядят так (все времена в микросекундах на операцию, меньше — лучше):

    Алгоритм n = 10 000 n = 100 000 n = 1 000 000
    naiveIterator 97.7 904.0 10592.7
    naiveGet 99.8 1084.4 11424.2
    collector 112.5 1404.9 14387.2
    reduce 112.1 1139.5 12001.5
    stream 146.4 1624.1 16600.9
    streamEx 115.2 1247.1 12967.0
    streamParallel 56.9 582.3 6120.5
    streamExParallel 53.4 516.7 5353.4

    Видно, что версия с pairMap (streamEx) обгоняет и традиционный потоковый вариант (stream), и версию с коллектором, уступая только неправильному reduce. При этом параллельная версия streamEx также быстрее параллельной версии stream и существенно обгоняет все последовательные версии даже для небольшого набора данных. Это согласуется с эмпирическим правилом из Stream Parallel Guidance: имеет смысл параллелить задачу, если она выполняется не менее 100 микросекунд.

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

    • java
    • stream api
    • spliterator
    • параллельные вычисления
    • Java
    • Параллельное программирование

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *