Cumulative Sum using Java 8 stream APIHow does newly introduced Arrays.parallelPrefix(…) in Java 8 work?Map to a running sum in Java 8Is Java “pass-by-reference” or “pass-by-value”?How do I efficiently iterate over each entry in a Java Map?What is the difference between public, protected, package-private and private in Java?How do I read / convert an InputStream into a String in Java?When to use LinkedList over ArrayList in Java?How do I generate random integers within a specific range in Java?How do I convert a String to an int in Java?Creating a memory leak with JavaJava 8 List<V> into Map<K, V>How to Convert a Java 8 Stream to an Array?
Why didn't Boeing produce its own regional jet?
Am I breaking OOP practice with this architecture?
How can I deal with my CEO asking me to hire someone with a higher salary than me, a co-founder?
How to enclose theorems and definition in rectangles?
What is a Samsaran Word™?
How to remove border from elements in the last row?
How can I prove that a state of equilibrium is unstable?
Are British MPs missing the point, with these 'Indicative Votes'?
How could indestructible materials be used in power generation?
Processor speed limited at 0.4 Ghz
My ex-girlfriend uses my Apple ID to log in to her iPad. Do I have to give her my Apple ID password to reset it?
What historical events would have to change in order to make 19th century "steampunk" technology possible?
What is the most common color to indicate the input-field is disabled?
Sums of two squares in arithmetic progressions
How badly should I try to prevent a user from XSSing themselves?
Placement of More Information/Help Icon button for Radio Buttons
In Bayesian inference, why are some terms dropped from the posterior predictive?
How to compactly explain secondary and tertiary characters without resorting to stereotypes?
How to show a landlord what we have in savings?
How can saying a song's name be a copyright violation?
Avoiding the "not like other girls" trope?
Why are UK visa biometrics appointments suspended at USCIS Application Support Centers?
Machine learning testing data
What is an equivalently powerful replacement spell for the Yuan-Ti's Suggestion spell?
Cumulative Sum using Java 8 stream API
How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?Map to a running sum in Java 8Is Java “pass-by-reference” or “pass-by-value”?How do I efficiently iterate over each entry in a Java Map?What is the difference between public, protected, package-private and private in Java?How do I read / convert an InputStream into a String in Java?When to use LinkedList over ArrayList in Java?How do I generate random integers within a specific range in Java?How do I convert a String to an int in Java?Creating a memory leak with JavaJava 8 List<V> into Map<K, V>How to Convert a Java 8 Stream to an Array?
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]
java java-8 java-stream
add a comment |
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]
java java-8 java-stream
11
You'll notice from the answers that any solution using streams is going to be inefficient. Streams aren't really intended for this use case. (In general, streams aren't intended to replace all imperative code.)
– Louis Wasserman
Mar 20 at 16:48
@LouisWasserman I agree. But in this case I do not care about efficiency (probably should have mentioned it in the question). I wanted to write the same thing with something other than above mentioned imperative style. I could not do it myself, as I was stuck because the solution is kind of mixture of map and reduce operation
– run_time_error
Mar 20 at 17:17
Man, the lack of tuples really hurts here.
– Alexander
Mar 20 at 22:19
2
An extremely similar question was asked yesterday: stackoverflow.com/questions/55230261/…
– Jacob G.
Mar 21 at 0:41
add a comment |
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]
java java-8 java-stream
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]
java java-8 java-stream
java java-8 java-stream
edited Mar 20 at 16:38
Stefan Zobel
2,48231931
2,48231931
asked Mar 20 at 16:32
run_time_errorrun_time_error
166213
166213
11
You'll notice from the answers that any solution using streams is going to be inefficient. Streams aren't really intended for this use case. (In general, streams aren't intended to replace all imperative code.)
– Louis Wasserman
Mar 20 at 16:48
@LouisWasserman I agree. But in this case I do not care about efficiency (probably should have mentioned it in the question). I wanted to write the same thing with something other than above mentioned imperative style. I could not do it myself, as I was stuck because the solution is kind of mixture of map and reduce operation
– run_time_error
Mar 20 at 17:17
Man, the lack of tuples really hurts here.
– Alexander
Mar 20 at 22:19
2
An extremely similar question was asked yesterday: stackoverflow.com/questions/55230261/…
– Jacob G.
Mar 21 at 0:41
add a comment |
11
You'll notice from the answers that any solution using streams is going to be inefficient. Streams aren't really intended for this use case. (In general, streams aren't intended to replace all imperative code.)
– Louis Wasserman
Mar 20 at 16:48
@LouisWasserman I agree. But in this case I do not care about efficiency (probably should have mentioned it in the question). I wanted to write the same thing with something other than above mentioned imperative style. I could not do it myself, as I was stuck because the solution is kind of mixture of map and reduce operation
– run_time_error
Mar 20 at 17:17
Man, the lack of tuples really hurts here.
– Alexander
Mar 20 at 22:19
2
An extremely similar question was asked yesterday: stackoverflow.com/questions/55230261/…
– Jacob G.
Mar 21 at 0:41
11
11
You'll notice from the answers that any solution using streams is going to be inefficient. Streams aren't really intended for this use case. (In general, streams aren't intended to replace all imperative code.)
– Louis Wasserman
Mar 20 at 16:48
You'll notice from the answers that any solution using streams is going to be inefficient. Streams aren't really intended for this use case. (In general, streams aren't intended to replace all imperative code.)
– Louis Wasserman
Mar 20 at 16:48
@LouisWasserman I agree. But in this case I do not care about efficiency (probably should have mentioned it in the question). I wanted to write the same thing with something other than above mentioned imperative style. I could not do it myself, as I was stuck because the solution is kind of mixture of map and reduce operation
– run_time_error
Mar 20 at 17:17
@LouisWasserman I agree. But in this case I do not care about efficiency (probably should have mentioned it in the question). I wanted to write the same thing with something other than above mentioned imperative style. I could not do it myself, as I was stuck because the solution is kind of mixture of map and reduce operation
– run_time_error
Mar 20 at 17:17
Man, the lack of tuples really hurts here.
– Alexander
Mar 20 at 22:19
Man, the lack of tuples really hurts here.
– Alexander
Mar 20 at 22:19
2
2
An extremely similar question was asked yesterday: stackoverflow.com/questions/55230261/…
– Jacob G.
Mar 21 at 0:41
An extremely similar question was asked yesterday: stackoverflow.com/questions/55230261/…
– Jacob G.
Mar 21 at 0:41
add a comment |
5 Answers
5
active
oldest
votes
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.
1
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
2
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
2
Don’t make your life unnecessary hard. Uselist1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array totoArray(T[])
.”
– Holger
Mar 21 at 7:47
2
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
add a comment |
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();
)
);
5
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
1
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
add a comment |
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());
add a comment |
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]
7
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
@VenkataraghavanYanamandram with other solutions yes, but they areO(n^2)
– Yassin Hajaj
Mar 21 at 9:22
add a comment |
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]
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55265797%2fcumulative-sum-using-java-8-stream-api%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
1
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
2
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
2
Don’t make your life unnecessary hard. Uselist1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array totoArray(T[])
.”
– Holger
Mar 21 at 7:47
2
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
add a comment |
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.
1
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
2
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
2
Don’t make your life unnecessary hard. Uselist1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array totoArray(T[])
.”
– Holger
Mar 21 at 7:47
2
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
add a comment |
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.
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.
edited Mar 25 at 15:08
answered Mar 20 at 16:54
Federico Peralta SchaffnerFederico Peralta Schaffner
23.8k43780
23.8k43780
1
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
2
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
2
Don’t make your life unnecessary hard. Uselist1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array totoArray(T[])
.”
– Holger
Mar 21 at 7:47
2
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
add a comment |
1
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
2
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
2
Don’t make your life unnecessary hard. Uselist1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array totoArray(T[])
.”
– Holger
Mar 21 at 7:47
2
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
1
1
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
Never heard of parallel prefix. thank you very much for teaching me a new concept. :). I will definitely give a try.
– run_time_error
Mar 20 at 17:26
2
2
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
@run_time_error Here's more reading about the subject.
– Federico Peralta Schaffner
Mar 20 at 18:26
2
2
Don’t make your life unnecessary hard. Use
list1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array to toArray(T[])
.”– Holger
Mar 21 at 7:47
Don’t make your life unnecessary hard. Use
list1.toArray(new Integer[0])
. As elaborated in this great article, using a zero size is even more efficient in the commonly used Hotspot JVM. That’s one of the reasons why JDK 11’s new method just does the same: “The default implementation calls the generator function with zero and then passes the resulting array to toArray(T[])
.”– Holger
Mar 21 at 7:47
2
2
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
@run_time_error also worth reading: How does newly introduced Arrays.parallelPrefix(…) in Java 8 work?
– Holger
Mar 21 at 7:56
add a comment |
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();
)
);
5
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
1
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
add a comment |
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();
)
);
5
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
1
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
add a comment |
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();
)
);
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();
)
);
edited Mar 20 at 16:55
answered Mar 20 at 16:41
MichaelMichael
21.5k83572
21.5k83572
5
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
1
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
add a comment |
5
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
1
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
5
5
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
That's O(n^2) !! (as opposed to the O(n) of the OP)
– DodgyCodeException
Mar 20 at 16:42
1
1
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@DodgyCodeException Yes.
– Michael
Mar 20 at 16:44
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
@Michael thanks for your elaborate response. I have learnt that I can write my own collector. I know this is overkill. But good to know that there are other ways.
– run_time_error
Mar 20 at 17:24
add a comment |
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());
add a comment |
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());
add a comment |
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());
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());
edited Mar 20 at 16:44
answered Mar 20 at 16:43
RuslanRuslan
4,5211229
4,5211229
add a comment |
add a comment |
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]
7
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
@VenkataraghavanYanamandram with other solutions yes, but they areO(n^2)
– Yassin Hajaj
Mar 21 at 9:22
add a comment |
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]
7
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
@VenkataraghavanYanamandram with other solutions yes, but they areO(n^2)
– Yassin Hajaj
Mar 21 at 9:22
add a comment |
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]
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]
edited Mar 21 at 9:27
answered Mar 20 at 16:49
Yassin HajajYassin Hajaj
14.5k72961
14.5k72961
7
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
@VenkataraghavanYanamandram with other solutions yes, but they areO(n^2)
– Yassin Hajaj
Mar 21 at 9:22
add a comment |
7
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
@VenkataraghavanYanamandram with other solutions yes, but they areO(n^2)
– Yassin Hajaj
Mar 21 at 9:22
7
7
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
This solution only works as long as the stream is sequential. Parallelising it would break this completely.
– Ben R.
Mar 20 at 17:30
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
@ben In parallel stream you couldn't have cumulative sum right?
– Venkataraghavan Yanamandram
Mar 21 at 8:40
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
Ruslan's answer allows for parallel streaming. The only stateful operation is over the original list itself, which we can probably assume with relative safety is read-only. Each item in the list in his solution could query over the list independently of the other stream elements.
– Ben R.
Mar 21 at 9:21
@VenkataraghavanYanamandram with other solutions yes, but they are
O(n^2)
– Yassin Hajaj
Mar 21 at 9:22
@VenkataraghavanYanamandram with other solutions yes, but they are
O(n^2)
– Yassin Hajaj
Mar 21 at 9:22
add a comment |
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]
add a comment |
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]
add a comment |
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]
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]
edited Mar 20 at 18:12
answered Mar 20 at 17:54
Samuel PhilippSamuel Philipp
3,5541629
3,5541629
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55265797%2fcumulative-sum-using-java-8-stream-api%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
11
You'll notice from the answers that any solution using streams is going to be inefficient. Streams aren't really intended for this use case. (In general, streams aren't intended to replace all imperative code.)
– Louis Wasserman
Mar 20 at 16:48
@LouisWasserman I agree. But in this case I do not care about efficiency (probably should have mentioned it in the question). I wanted to write the same thing with something other than above mentioned imperative style. I could not do it myself, as I was stuck because the solution is kind of mixture of map and reduce operation
– run_time_error
Mar 20 at 17:17
Man, the lack of tuples really hurts here.
– Alexander
Mar 20 at 22:19
2
An extremely similar question was asked yesterday: stackoverflow.com/questions/55230261/…
– Jacob G.
Mar 21 at 0:41