CODEWITHSUNDEEP
javajava-8java-stream
run_time_error
run_time_error

Reputation: 707

Cumulative Sum using Java 8 stream API

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]

Upvotes: 21

Views: 10707

Answers (6)

M. Justin
M. Justin

Reputation: 21123

The JEP 461: Stream Gatherers Java 22 preview language feature adds built-in support for this sort of cumulative accumulation:

// [1, 3, 6, 10]
List<Integer> incrementalSums = Stream.of(1, 2, 3, 4)
        .gather(Gatherers.scan(() -> 0, Integer::sum))
        .toList();

This uses the new Stream.gather method with the new built-in Gatherers.scan gatherer to convert the initial stream to a stream of sums.

Javadocs

Gatherer:

An intermediate operation that transforms a stream of input elements into a stream of output elements, optionally applying a final action when the end of the upstream is reached. […]

[…]

There are many examples of gathering operations, including but not limited to: grouping elements into batches (windowing functions); de-duplicating consecutively similar elements; incremental accumulation functions (prefix scan); incremental reordering functions, etc. The class Gatherers provides implementations of common gathering operations.

Stream.gather:

Returns a stream consisting of the results of applying the given gatherer to the elements of this stream.

Gatherers.scan

Returns a Gatherer that performs a Prefix Scan -- an incremental accumulation -- using the provided functions. Starting with an initial value obtained from the Supplier, each subsequent value is obtained by applying the BiFunction to the current value and the next input element, after which the resulting value is produced downstream.

Example:

// will contain: ["1", "12", "123", "1234", "12345", "123456", "1234567", "12345678", "123456789"]
List<String> numberStrings =
    Stream.of(1,2,3,4,5,6,7,8,9)
          .gather(
              Gatherers.scan(() -> "", (string, number) -> string + number)
           )
          .toList();

Upvotes: 1

fps
fps

Reputation: 34460

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.

Upvotes: 21

Yassin Hajaj
Yassin Hajaj

Reputation: 21975

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]

Upvotes: 6

Samuel Philipp
Samuel Philipp

Reputation: 11042

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]

Upvotes: 3

Michael
Michael

Reputation: 44150

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

Upvotes: 6

Ruslan
Ruslan

Reputation: 6290

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

Upvotes: 3

Related Questions