Накопительная сумма с использованием потокового API Java 8

У меня есть список целых чисел, скажем, list1, и я хочу получить другой список list2, который будет содержать совокупную сумму вплоть до текущего индекса с начала. Как я могу сделать это с помощью Stream API Java 8?

List<Integer> list1 = new ArrayList<>();
list1.addAll(Arrays.asList(1, 2, 3, 4));
List<Integer> list2 = new ArrayList<>();
// initialization
list2.add(list1.get(0));
for(int i=1;i<list1.size();i++) {
// increment step
    list2.add(list2.get(i-1) + list1.get(i));
}

Как я могу изменить вышеуказанный императивный код стиля в декларативный?

list2 should be [1, 3, 6, 10]

Ответы

Ответ 1

Потоки не подходят для такого рода задач, так как в них участвует состояние (накопленная частичная сумма). Вместо этого вы можете использовать Arrays.parallelPrefix:

Integer[] arr = list1.toArray(Integer[]::new);

Arrays.parallelPrefix(arr, Integer::sum);

List<Integer> list2 = Arrays.asList(arr);

Сначала он копирует list1 в массив с помощью Collection.toArray, который доступен с JDK 11. Если вы еще не используете Java 11, вы можете заменить первую строку традиционным вызовом toArray:

Integer[] arr = list1.toArray(new Integer[0]);

Это решение не использует потоки, но оно декларативно, потому что Arrays.parallelPrefix получает накопительную операцию в качестве аргумента (в данном случае Integer::sum).

Сложность по времени составляет O(N), хотя могут быть некоторые неминимальные постоянные затраты, связанные с настройкой инфраструктуры, необходимой для параллельной обработки. Однако согласно документам:

Параллельное вычисление префикса обычно более эффективно, чем последовательные циклы для больших массивов

Так что, похоже, стоит попробовать этот подход.

Также стоит отметить, что этот подход работает, потому что Integer::sum является ассоциативной операцией. Это требование.

Ответ 2

Для каждого индекса: итерация от нуля до этого индекса, получение каждого элемента и получение суммы
Поместите целые числа в Integer
Собрать в список

IntStream.range(0, list1.size())
    .map(i -> IntStream.rangeClosed(0, i).map(list1::get).sum())
    .boxed()
    .collect(Collectors.toList());

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

Вы могли бы написать свой собственный сборщик, но на данный момент, честно говоря, почему вы вообще беспокоитесь о потоках?

list1.stream()
    .collect(
        Collector.of(
            ArrayList::new,
            (a, b) -> a.add(a.isEmpty() ? b : b + a.get(a.size() - 1)),
            (a, b) -> { throw new UnsupportedOperationException(); }
        )
    );

Ответ 3

Вы можете использовать sublist для суммирования до текущего индекса с начала:

List<Integer> list = IntStream.range(0, list1.size())
        .mapToObj(i -> list1.subList(0, i + 1).stream().mapToInt(Integer::intValue).sum())
        .collect(Collectors.toList());

Ответ 4

Решение O(n) (работает только последовательно) будет следующим, но я не считаю его очень элегантным. Я думаю, это дело вкуса

AtomicInteger ai = new AtomicInteger();
List<Integer> collect = list1.stream()
                             .map(ai::addAndGet)
                             .collect(Collectors.toList());
System.out.println(collect); // [1, 3, 6, 10]

Ответ 5

Вы можете просто использовать Stream.collect() для этого:

List<Integer> list1 = Arrays.asList(1, 2, 3, 4);
List<Integer> list2 = list1.stream()
        .collect(ArrayList::new, (sums, number) -> {
            if (sums.isEmpty()) {
                sums.add(number);
            } else {
                sums.add(sums.get(sums.size() - 1) + number);
            }
        }, (sums1, sums2) -> {
            if (!sums1.isEmpty()) {
                int sum = sums1.get(sums1.size() - 1);
                sums2.replaceAll(num -> sum + num);
            }
            sums1.addAll(sums2);
        });

Это решение также работает для параллельных потоков. Используйте list1.parallelStream() или list1.stream().parallel() вместо list1.stream().

Результат в обоих случаях: [1, 3, 6, 10]