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

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

11 голосов
/ 20 марта 2019

У меня есть список целых чисел, скажем, 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]

Ответы [ 5 ]

10 голосов
/ 20 марта 2019

Потоки не подходят для такого рода задач, поскольку в них присутствует состояние (накопленная частичная сумма). Вместо этого вы можете использовать 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 является ассоциативной операцией . Это требование.

5 голосов
/ 20 марта 2019

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

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 голосов
/ 20 марта 2019

Решение 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]
3 голосов
/ 20 марта 2019

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

List<Integer> list = IntStream.range(0, list1.size())
        .mapToObj(i -> list1.subList(0, i + 1).stream().mapToInt(Integer::intValue).sum())
        .collect(Collectors.toList());
1 голос
/ 20 марта 2019

Вы можете просто использовать 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]

...