В ответе Эрана описаны различия между версиями reduce
с двумя и тремя аргументами в том, что первая уменьшает Stream<T>
до T
, тогда как последний уменьшает Stream<T>
до U
. Однако на самом деле это не объясняло необходимости дополнительной функции объединителя при уменьшении Stream<T>
до U
.
Один из принципов проектирования Streams API заключается в том, что API не должен различаться между последовательными и параллельными потоками, или, другими словами, конкретный API не должен препятствовать правильной работе потока ни последовательно, ни параллельно. Если ваши лямбда-выражения имеют правильные свойства (ассоциативность, отсутствие помех и т. Д.), Поток, выполняемый последовательно или параллельно, должен давать те же результаты.
Давайте сначала рассмотрим вариант сокращения с двумя аргументами:
T reduce(I, (T, T) -> T)
Последовательная реализация проста. Идентификационное значение I
«накапливается» с нулевым элементом потока для получения результата. Этот результат накапливается с первым элементом потока, чтобы дать другой результат, который, в свою очередь, накапливается со вторым элементом потока и так далее. После накопления последнего элемента возвращается окончательный результат.
Параллельная реализация начинается с разделения потока на сегменты. Каждый сегмент обрабатывается своим собственным потоком последовательным способом, который я описал выше. Теперь, если у нас есть N потоков, у нас есть N промежуточных результатов. Их нужно свести к одному результату. Поскольку каждый промежуточный результат относится к типу T, а у нас их несколько, мы можем использовать одну и ту же функцию накопителя, чтобы уменьшить эти N промежуточных результатов до одного результата.
Теперь давайте рассмотрим гипотетическую операцию сокращения двух аргументов, которая сокращает Stream<T>
до U
. На других языках это называется «складкой» или «складкой». left "операция, так что я назову ее здесь. Обратите внимание, этого нет в Java.
U foldLeft(I, (U, T) -> U)
(Обратите внимание, что значение идентификатора I
относится к типу U.)
Последовательная версия foldLeft
аналогична последовательной версии reduce
, за исключением того, что промежуточные значения имеют тип U, а не тип T. Но в остальном все то же самое. (Гипотетическая foldRight
операция будет аналогичной, за исключением того, что операции будут выполняться справа налево, а не слева направо.)
Теперь рассмотрим параллельную версию foldLeft
. Начнем с разделения потока на сегменты. Затем мы можем заставить каждый из N потоков уменьшить значения T в своем сегменте до N промежуточных значений типа U. Что теперь? Как нам перейти от N значений типа U к одному результату типа U?
Чего не хватает, так это еще одной функции, которая объединяет несколько промежуточных результатов типа U в один результат типа U. Если у нас есть функция, которая объединяет два значения U в одно, этого достаточно, чтобы уменьшить любое количество значений. до одного - точно так же, как и исходное сокращение выше. Таким образом, операция редукции, дающая результат другого типа, требует двух функций:
U reduce(I, (U, T) -> U, (U, U) -> U)
Или, используя синтаксис Java:
<U> U reduce(U identity, BiFunction<U,? super T,U> accumulator, BinaryOperator<U> combiner)
Таким образом, чтобы выполнить параллельное сокращение до другого типа результата, нам понадобятся две функции: одна, которая накапливает элементы T до промежуточных значений U, а вторая объединяет промежуточные значения U значений в один результат U. Если мы не переключаем типы, оказывается, что функция аккумулятора такая же, как и функция объединения. Вот почему приведение к одному и тому же типу имеет только функцию накопителя, а приведение к другому типу требует отдельных функций накопителя и сумматора.
Наконец, Java не предоставляет foldLeft
и foldRight
операций, потому что они подразумевают определенный порядок операций, который по своей сути является последовательным. Это противоречит принципу проектирования, изложенному выше, о предоставлении API-интерфейсов, которые в равной степени поддерживают последовательную и параллельную работу.
person
Stuart Marks
schedule
19.06.2014