Краткий ответ

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

Исторический контекст

Модель Stream API позволяет разделить обработку источника на независимые части, вычислить их параллельно и затем объединить частичные результаты. Такой подход эффективен только тогда, когда результат не зависит от конкретной структуры разбиения.

Для этого операции свёртки должны обладать математическими свойствами, позволяющими безопасно менять порядок группировки вычислений. Главное из них — ассоциативность.

Постановка проблемы

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

Если функция неассоциативна, выражения (a ⊗ b) ⊗ c и a ⊗ (b ⊗ c) дают разные результаты. Следовательно, разные варианты разбиения одного источника могут приводить к разным итогам, а результат параллельного вычисления может не совпасть с последовательным.

Подробное решение

Контракт параллельной свёртки требует, чтобы функция объединения была ассоциативной. Нейтральный элемент также должен быть действительно нейтральным: объединение с ним не должно менять результат.

Например, вычитание неассоциативно: (10 - 5) - 2 не равно 10 - (5 - 2). Поэтому использование вычитания в качестве функции свёртки нарушает контракт параллельного reduce.

import java.util.stream.IntStream;

int result = IntStream.rangeClosed(1, 4)
    .parallel()
    .reduce(0, (left, right) -> left - right);

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

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

Если операция по смыслу неассоциативна, безопасные варианты — последовательная обработка, изменение алгоритма на ассоциативный или накопление данных в структуре, которую можно корректно объединять. Простое добавление parallel() проблему не решает.

Ситуация из практики

Сервис агрегирует финансовые корректировки. Разработчик выбирает параллельный reduce с операцией вычитания, рассчитывая получить последовательное применение скидок и возвратов.

Рассматривались три варианта. Параллельная свёртка была отклонена: результат зависит от разбиения. Последовательный reduce сохраняет требуемый порядок, но не ускоряется на больших объёмах. Переделка операции в вычисление суммы знаковых корректировок делает агрегацию ассоциативной и сохраняет возможность параллельной обработки.

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

Что кандидаты часто упускают

1. Обязательно ли операции свёртки быть коммутативной?

Нет, обязательное требование — ассоциативность, а не коммутативность. Например, конкатенация строк некоммутативна, но может быть ассоциативной: (a + b) + c равно a + (b + c). На упорядоченном потоке такая операция может корректно сохранять порядок, хотя параллельный результат не обязан быть независимым от порядка элементов.

2. Почему неправильный identity-элемент тоже ломает параллельный reduce?

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

3. Можно ли исправить неассоциативную свёртку характеристикой UNORDERED?

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