Cumulative Sum using Java 8 stream API

Question

I have a List of Integer say list1, and I want to get another list list2 which will contain the cumulative sum up until the current index from start. How can I do this using 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));
}

How can I change above imperative style code into declarative one ?

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

Answer 1

Streams are not suited for this kind of task, as there is state involved (the cumulative partial sum). Instead, you could use Arrays.parallelPrefix:

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

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

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

This first copies list1 to an array by using Collection.toArray, which is available since JDK 11. If you are not on Java 11 yet, you could replace the first line with the traditional toArray call:

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

This solution doesn't use streams, yet it's declarative, because Arrays.parallelPrefix receives the cumulative operation as an argument (Integer::sum in this case).

Time complexity is O(N), though there might be some non-minor constant costs involved associated with setting up the infrastructure needed for parallel processing. However, according to the docs:

Parallel prefix computation is usually more efficient than sequential loops for large arrays

So it seems it's worth giving this approach a try.

Also, it's worth mentioning that this approach works because Integer::sum is an associative operation. This is a requirement.

Answer 2

For every index: iterate from zero to that index, get each element, and get the sum
Box the ints to Integers
Collect to a list

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

You're adding every number together every time, rather than reusing the previous cumulative result, but streams do not lend themselves to looking at results from previous iterations.

You could write your own collector but at this point, honestly why are you even bothering with streams?

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(); }
        )
    );

Answer 3

An O(n) (works only sequentially) solution would be the following, but I don't find it very elegant. I guess it is a matter of taste

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

Answer 4

You can use sublist to sum up until the current index from start:

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

Answer 5

You can just use Stream.collect() for that:

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);
        });

This solution also works for parallel streams. Use list1.parallelStream() or list1.stream().parallel() instead of list1.stream().

The result in both cases is: [1, 3, 6, 10]