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]
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.
For every index: iterate from zero to that index, get each element, and get the sum
Box the ints to Integer
s
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(); }
)
);
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]
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());
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With