Що робить операція reduce()

Операція reduce() реалізує патерн імутабельної редукції: на кожному кроці вона повертає нове значення, не мутуючи вихідні об'єкти. Існують три перевантаження методу:

🟢 Junior Level

Коротка відповідь для співбесіди (30 секунд)

reduce() (Редукція / Згортання) — це термінальна операція Stream API, яка послідовно об’єднує всі елементи потоку в одне результуюче значення за допомогою заданої функції-акумулятора (наприклад, знаходження суми, добутку, мінімуму або конкатенації).

Операція reduce() реалізує патерн імутабельної редукції: на кожному кроці вона повертає нове значення, не мутуючи вихідні об’єкти. Існують три перевантаження методу:

reduce(BinaryOperator<T> accumulator) — повертає Optional<T> (оскільки потік може бути порожнім).
reduce(T identity, BinaryOperator<T> accumulator) — повертає T (при порожньому потоці повертається початкове значення identity).
reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner) — дозволяє повернути тип U, відмінний від типу елементів потоку T.

Приклади використання на Java 21

import java.util.List;
import java.util.Optional;

public class ReduceBasicsDemo {

    public static void main(String[] args) {
        List<Integer> numbers = List.of(2, 3, 4, 5);

        // 1. Без identity: повертає Optional
        Optional<Integer> productOpt = numbers.stream()
            .reduce((a, b) -> a * b);
        System.out.println("Добуток: " + productOpt.orElse(0)); // 120

        // 2. З початковим значенням (identity = 0 для суми): повертає примітив/значення
        int sum = numbers.stream()
            .reduce(0, Integer::sum);
        System.out.println("Сума: " + sum); // 14

        // 3. Пошук максимального елемента
        int max = numbers.stream()
            .reduce(Integer.MIN_VALUE, Integer::max);
        System.out.println("Максимум: " + max); // 5

        // 4. Поведінка на порожньому стрімі
        List<Integer> empty = List.of();
        int emptyResult = empty.stream().reduce(42, Integer::sum);
        System.out.println("Порожній стрім з identity: " + emptyResult); // 42
    }
}

🟡 Middle Level

Математичний контракт моноіда: Identity та Асоціативність

Коректність роботи reduce() (особливо при переході на parallelStream()) базується на концепції моноїда з абстрактної алгебри і вимагає суворого дотримання двох математичних властивостей:

1. Нейтральний елемент (`identity`)

Функція акумулятора повинна повертати вихідний елемент при передачі identity: $\text{accumulator}(\text{identity}, v) = v$

Для додавання: $\text{identity} = 0$ ($0 + x = x$).
Для множення: $\text{identity} = 1$ ($1 \times x = x$).
Для пошуку максимуму: $\text{identity} = -\infty$ (Integer.MIN_VALUE).

❌ Помилка: Якщо для підсумовування задати identity = 100, то в послідовному стрімі результат збільшиться на 100, а в паралельному стрімі з 4 потоків кожен потік додасть 100 до свого чанка, і підсумкова сума збільшиться на $4 \times 100 = 400$!

2. Асоціативність (Associativity)

Порядок групування операцій не повинен впливати на результат: $(a \circ b) \circ c = a \circ (b \circ c)$ Це дозволяє потокам ForkJoinPool довільно ділити потік на гілки та об’єднувати часткові результати в будь-якому порядку:

Послідовно:       ((1 + 2) + 3) + 4 = 10
Паралельно:       (1 + 2) + (3 + 4) = 3 + 7 = 10

❌ Неасоціативні операції: Віднімання (a - b) або ділення не мають властивості асоціативності: $(10 - 2) - 3 = 5$, але $10 - (2 - 3) = 11$. Виклик .parallelStream().reduce((a, b) -> a - b) поверне недетермінований хаотичний результат!

🔴 Senior Level

Третя сигнатура `reduce()`: Навіщо потрібен `Combiner`

<U> U reduce(U identity, 
             BiFunction<U, ? super T, U> accumulator, 
             BinaryOperator<U> combiner);

У цій сигнатурі тип акумулятора U відрізняється від типу елементів потоку T.

List<String> words = List.of("Java", "Stream", "API");

int totalLength = words.parallelStream()
    .reduce(
        0,                                 // identity: U (Integer)
        (acc, str) -> acc + str.length(),  // accumulator: (U, T) -> U
        Integer::sum                       // combiner: (U, U) -> U
    );

Механіка виконання:

У послідовному стрімі: combiner ніколи не викликається. Стрім іде послідовно, викликаючи accumulator.apply(acc, element) на кожному кроці.
У паралельному стрімі:
- Кожен робочий потік ForkJoinWorkerThread незалежно накопичує часткову суму елементів свого чанка в тип U за допомогою accumulator.
- На етапі завершення дочірніх завдань ForkJoinPool викликає combiner.apply(u1, u2) для попарного злиття проміжних результатів типу U в дереві згортання.

Антипатерн: Мутабельна редукція через `reduce()`

Часта помилка — спроба зібрати колекцію через reduce():

// ❌ АНТИПАТЕРН: $O(N^2)$ алокацій та поломка паралелізму
List<String> bad = stream.reduce(
    new ArrayList<>(),
    (list, item) -> {
        list.add(item); // Мутація спільного списку або постійне копіювання!
        return list;
    },
    (left, right) -> {
        left.addAll(right);
        return left;
    }
);

Чому це неприпустимо:

При паралельному виконанні різні потоки одночасно мутують один і той самий переданий об’єкт identity = new ArrayList<>(), породжуючи гонки даних.
Якщо створювати новий список на кожному кроці, складність алгоритму зросте з $O(N)$ до $O(N^2)$ через безперервне копіювання масивів.
Для накопичення в змінні структури даних існує спеціалізована операція мутабельної редукції — collect().

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь

«reduce() — це термінальна операція імутабельного згортання елементів стріма в одне підсумкове значення. Для коректної роботи акумулятора потрібне дотримання властивостей моноїда: наявність нейтрального елемента identity та сувора асоціативність функції (порядок об’єднання дужок не має значення). При неасоціативних операціях (наприклад, відніманні) паралельний стрім повертає хибний результат. Третє перевантаження reduce з combiner застосовується при зміні типу даних, при цьому combiner викликається виключно в паралельному режимі для злиття часткових результатів.»

Зведена таблиця трьох перевантажень `reduce`

Сигнатура	Тип, що повертається	Поведінка на порожньому стрімі	Призначення combiner
`reduce(accumulator)`	`Optional<T>`	`Optional.empty()`	Не потрібен (тип $T$)
`reduce(identity, accumulator)`	`T`	Повертає `identity`	Не потрібен (тип $T$)
`reduce(identity, accumulator, combiner)`	`U`	Повертає `identity`	Злиття результатів $U$ у `parallelStream`

Топ-4 каверзних запитання на інтерв’ю

1. Чому `reduce()` зі збиранням у `ArrayList` є антипатерном зі складністю $O(N^2)$?

reduce() призначений для незмінних типів даних (числа, рядки, об’єкти-значення). Якщо створювати новий список на кожному елементі, на кожному кроці $i$ копіюється $i$ елементів, що дає суму арифметичної прогресії $\sum_{i=1}^N i = O(N^2)$. Якщо ж мутувати переданий список, у паралельному режимі виникне гонка даних за один екземпляр identity. Для змінних колекцій потрібно використовувати collect().

2. Що станеться, якщо в ролі `identity` передати ненейтральний елемент (наприклад, 10 при підсумовуванні) у `parallelStream`?

Результат буде фатально завищений. У паралельному стрімі дані розбиваються на $K$ підзавдань за кількістю задіяних воркерів ForkJoinPool. Кожен воркер почне підсумовування зі значення identity = 10. При злитті результатів гілок число 10 буде враховане не один раз, а $K$ разів.

3. Чому параметр `combiner` узагалі не викликається в послідовному стрімі?

В однопотоковому виконанні немає паралельних гілок обчислень. Існує єдиний потік і один акумулятор типу U, який послідовно оновлюється через accumulator.apply(u, t). Зливати нічого, тому рантайм ReferencePipeline оптимізує код і повністю ігнорує combiner.

4. Як математичні властивості моноїда гарантують коректність `reduce` у паралельних стрімах?

Моноїд вимагає замкненості, нейтрального елемента та асоціативності. Асоціативність гарантує, що дерево декомпозиції ForkJoinTask може ділити масив у будь-яких точках і об’єднувати результати в довільному порядку вузлів дерева: $(A + B) + (C + D) = A + (B + (C + D))$. Це фундамент алгоритму «розділяй і володарюй».

Типові помилки та Red Flags

🚩 Використання неасоціативних операцій (віднімання, ділення) у reduce().
🚩 Використання reduce() для накопичення елементів у List, Set або StringBuilder замість collect().
🚩 Задання ненейтрального identity, що призводить до множення початкового зміщення в паралельних потоках.
🚩 Забування про примітивні стріми (mapToInt().sum()), що призводить до мільйонів алокацій автобоксингу в reduce(0, Integer::sum).

🟢 Junior Level

Коротка відповідь для співбесіди (30 секунд)

Приклади використання на Java 21

🟡 Middle Level

Математичний контракт моноіда: Identity та Асоціативність

1. Нейтральний елемент (identity)

2. Асоціативність (Associativity)

🔴 Senior Level

Третя сигнатура reduce(): Навіщо потрібен Combiner

Механіка виконання:

Антипатерн: Мутабельна редукція через reduce()

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь

Зведена таблиця трьох перевантажень reduce

Топ-4 каверзних запитання на інтерв’ю

1. Чому reduce() зі збиранням у ArrayList є антипатерном зі складністю $O(N^2)$?

2. Що станеться, якщо в ролі identity передати ненейтральний елемент (наприклад, 10 при підсумовуванні) у parallelStream?

3. Чому параметр combiner узагалі не викликається в послідовному стрімі?

4. Як математичні властивості моноїда гарантують коректність reduce у паралельних стрімах?