Поведение Stream.skip с неупорядоченной работой терминала

Я уже прочитал этот и эти вопросы, но все же сомневаюсь, что наблюдаемое поведение Stream.skip было предназначено авторами JDK.

Давайте будем иметь простой ввод чисел 1..20:

 List input = IntStream.rangeClosed(1, 20).boxed().collect(Collectors.toList()); 

Теперь давайте создадим параллельный stream, объединим unordered() с skip() разными способами и собираем результат:

 System.out.println("skip-skip-unordered-toList: " + input.parallelStream().filter(x -> x > 0) .skip(1) .skip(1) .unordered() .collect(Collectors.toList())); System.out.println("skip-unordered-skip-toList: " + input.parallelStream().filter(x -> x > 0) .skip(1) .unordered() .skip(1) .collect(Collectors.toList())); System.out.println("unordered-skip-skip-toList: " + input.parallelStream().filter(x -> x > 0) .unordered() .skip(1) .skip(1) .collect(Collectors.toList())); 

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

 skip-skip-unordered-toList: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] // absent values: 1, 2 skip-unordered-skip-toList: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20] // absent values: 1, 15 unordered-skip-skip-toList: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20] // absent values: 7, 18 

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

Давайте пропустим один элемент и собираем в пользовательскую коллекцию в неупорядоченном режиме. Наша пользовательская коллекция будет HashSet :

 System.out.println("skip-toCollection: " + input.parallelStream().filter(x -> x > 0) .skip(1) .unordered() .collect(Collectors.toCollection(HashSet::new))); 

Выход удовлетворительный:

 skip-toCollection: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] // 1 is skipped 

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

Однако давайте использовать эквивалентную неупорядоченную операцию ввода терминала collect(Collectors.toSet()) :

 System.out.println("skip-toSet: " + input.parallelStream().filter(x -> x > 0) .skip(1) .unordered() .collect(Collectors.toSet())); 

Теперь выход:

 skip-toSet: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20] // 13 is skipped 

Тот же результат может быть достигнут с любой другой неупорядоченной работой терминала (например, для findAny , anyMatch , anyMatch и т. Д.). Удаление unordered() шага в этом случае ничего не меняет. Кажется, что, хотя unordered() шаг правильно делает stream неупорядоченным, начиная с текущей операции, неупорядоченная операция терминала делает весь stream неупорядоченным с самого начала, несмотря на то, что это может повлиять на результат, если используется skip() . Это кажется мне совершенно неверным: я ожидаю, что использование неупорядоченного коллектора будет таким же, как преrotation streamа в неупорядоченный режим непосредственно перед операцией терминала и использование эквивалентного упорядоченного коллектора.

Поэтому мои вопросы:

  1. Является ли это поведением или это ошибка?
  2. Если да, то где-то это документировано? Я прочитал документацию Stream.skip () : он ничего не говорит о неупорядоченных терминальных операциях. Также документация Characteristics.UNORDERED не очень понятна и не говорит, что упорядочение будет потеряно для всего streamа. Наконец, раздел « Заказ » в сводке пакетов также не охватывает этот случай. Наверное, я что-то упустил?
  3. Если предполагается, что неупорядоченная операция терминала делает весь stream неупорядоченным, почему unordered() шаг делает его неупорядоченным только с этой точки? Могу ли я полагаться на это поведение? Или мне просто повезло, что мои первые тесты работают хорошо?

    Напомним, что цель флагов streamа (ORDERED, SORTED, SIZED, DISTINCT) – это позволить операциям избежать ненужной работы. Примеры оптимизаций, которые include флаги streamа:

    • Если мы знаем, что stream уже отсортирован, то sorted() является no-op;
    • Если мы знаем размер streamа, мы можем предварительно выделить массив правильного размера в toArray() , избегая копирования;
    • Если мы знаем, что вход не имеет значимого порядка встреч, нам не нужно предпринимать дополнительных шагов для сохранения порядка встреч.

    Каждый этап конвейера имеет набор флагов streamа. Промежуточные операции могут вводить, сохранять или очищать флаги streamа. Например, фильтрация сохраняет сортировку / отчетность, но не размерность; отображение сохраняет размер, но не отсортировано или не определено. Сортировка сортирует инъекции. Обработка флагов для промежуточных операций довольно проста, поскольку все решения являются локальными.

    Обработка флагов для терминальных операций более тонкая. ORDERED является самым важным флагом для терминальных операций. И если терминал op UNDERERED, мы возвращаем обратно неупорядоченность.

    Почему мы это делаем? Ну, рассмотрим этот трубопровод:

     set.stream() .sorted() .forEach(System.out::println); 

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

    Является ли это поведением или это ошибка?

    Да 🙂 Предполагается обратное распространение, так как это полезная оптимизация, которая не должна приводить к неправильным результатам. Тем не менее, часть ошибок состоит в том, что мы распространяем предыдущий skip , чего не следует. Таким образом, обратное распространение флага UNORDERED является чрезмерно агрессивным, и это ошибка. Мы опубликуем ошибку.

    Если да, то где-то это документировано?

    Это должна быть только деталь реализации; если бы он был правильно реализован, вы бы не заметили (кроме того, что ваши streamи быстрее).

    @ Рубен, ты, наверное, не понимаешь моего вопроса. Примерно проблема: почему unordered (). Collect (toCollection (HashSet :: new)) ведет себя иначе, чем collect (toSet ()). Конечно, я знаю, что toSet () неупорядочен.

    Наверное, но, во всяком случае, я дам ему вторую попытку.

    Посмотрев на Javadocs of Collectors toSet и toCollection, мы видим, что toSet предоставляет неупорядоченный сборщик

    Это {@link Collector.Characteristics # UNORDERED неупорядоченный} Collector.

    т.е. CollectorImpl с UNORDERED Characteristic. Взглянув на Javadoc Collector. Характеристики # UNDERERED мы можем прочитать:

    Указывает, что операция сбора не фиксирует сохранение порядка входящих элементов ввода

    В Javadocs of Collector мы также видим:

    Для параллельных коллекционеров реализация может свободно (но не обязана) выполнять одновременно. Одновременная редукция – это функция, в которой функция аккумулятора называется одновременно из нескольких streamов, используя один и тот же контейнер с одновременным изменением результатов, а не сохраняя результат, выделенный во время накопления. Совместное сокращение следует применять, только если сборщик имеет характеристики {@link Characteristics # UNORDERED} или если исходные данные неупорядочены

    Это означает для меня, что если мы установим признак UNORDERED , нам все равно, о порядке, в котором элементы streamа передаются на аккумулятор, и, следовательно, элементы могут быть извлечены из трубопровода в любом порядке ,

    Кстати, вы получаете то же поведение, если опускаете неупорядоченный () в своем примере:

      System.out.println("skip-toSet: " + input.parallelStream().filter(x -> x > 0) .skip(1) .collect(Collectors.toSet())); 

    Кроме того, метод skip () в Stream дает нам подсказку:

    Хотя {@code skip ()} обычно является дешевой операцией на последовательных поточных конвейерах, это может быть довольно дорогостоящим на упорядоченных параллельных трубопроводах

    а также

    Использование источника неупорядоченного streamа (например, {@link #generate (Поставщик)}) или удаление ограничения порядка с {@link #unordered ()} может привести к значительным ускорениям

    Когда используешь

     Collectors.toCollection(HashSet::new) 

    вы создаете нормальный «упорядоченный» сборщик (один без признака UNORDERED), что для меня означает, что вы заботитесь о заказе, и, следовательно, элементы извлекаются по порядку, и вы получаете ожидаемое поведение.

    Давайте будем гением компьютера.