Map to a running sum in Java 8

Question

If I have a collection:

List<Long> numbers = asList(2, 2, 4, 5);

How can I map/process these to build up a running total. To produce something like:

List<Long> runningTotals = asList(2, 4, 8, 13);

Even better, how can I build a list of something (like a tuple) so I can preserve the orignals:

((2 -> 2), (2 -> 4), (4 -> 8), (5 -> 13));

Answer 1

You don't need Java 8 to do this. Indeed, this problem doesn't lend itself well to streams, because the calculation is stateful, in that it depends upon the sum of previous elements, so you don't get an advantage from things like parallelization.

You may as well just use a plain old loop:

ListIterator<Long> it = list.listIterator();
Long previous = it.next();  // Assuming the list isn't empty.
while (it.hasNext()) {
  it.set(previous += it.next());
}

In terms of the second requirement, do you really need to preserve the original elements in tuples? You can simply subtract each element in the running total list from its predecessor to recover the original:

AbstractList<Long> something = new AbstractList<Long>() {
  @Override public int size() { return list.size(); }
  @Override public Long get(int i) {
    if (i > 0) {
      return list.get(i) - list.get(i - 1);
    } else {
      return list.get(i);
    }
  }
};

Answer 2

Update: As Holger pointed out in the comments using Stream.reduce() for this purpose is not correct. See Reduction and Mutable Reduction or Java 8 Streams - collect vs reduce for more information.

You can use Java Stream.collect() instead to generate your list with sums:

List<Long> numbers = Arrays.asList(2L, 2L, 4L, 5L);
List<Pair> results = numbers.stream()
        .collect(ArrayList::new, (sums, number) -> {
            if (sums.isEmpty()) {
                sums.add(new Pair(number, number));
            } else {
                sums.add(new Pair(number, number + sums.get(sums.size() - 1).getSum()));
            }
        }, (sums1, sums2) -> {
            if (!sums1.isEmpty()) {
                long sum = sums1.get(sums1.size() - 1).getSum();
                sums2.forEach(p -> p.setSum(p.getSum() + sum));
            }
            sums1.addAll(sums2);
        });

This combines all the numbers and creates a pair for each number with the addition to the previous sum. It uses the following Pair class as helper:

public class Pair {
    private long number;
    private long sum;

    public Pair(long number, long sum) {
        this.number = number;
        this.sum = sum;
    }

    public long getNumber() {
        return number;
    }

    public void setSum(long sum) {
        this.sum = sum;
    }

    public long getSum() {
        return sum;
    }
}

You can easily change that helper class if you want to add some more information.

The result at the end is:

[
    Pair{number=2, sum=2}, 
    Pair{number=2, sum=4}, 
    Pair{number=4, sum=8}, 
    Pair{number=5, sum=13}
]

Answer 3

You can use Arrays#parallelPrefix to accomplish your goal:

List<Long> numbers = Arrays.asList(2L, 2L, 4L, 5L);
long[] copiedArray = numbers.stream().mapToLong(Long::longValue).toArray();

Arrays.parallelPrefix(copiedArray, Long::sum);

System.out.println(IntStream.range(0, numbers.size())
        .mapToObj(i -> "(" + numbers.get(i) + " -> " + copiedArray[i] + ")")
        .collect(Collectors.joining(", ", "[", "]")));

Output:

[(2 -> 2), (2 -> 4), (4 -> 8), (5 -> 13)]