Group Abstract Group Abstract

Message Boards Message Boards

0
|
14.9K Views
|
48 Replies
|
27 Total Likes
View groups...
Share
Share this post:

Sum positive elements of a list efficiently?

There are many ways to sum positive elements of a list such as, e.g.,

In[1]:= list = RandomReal[{-10, 10}, 1000000];

In[2]:= tList = {
  Plus @@ Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming
  }

Out[2]= {{2.51129, 2.49923*10^6}, {1.93032, 2.49923*10^6}, {1.6144, 2.49923*10^6}}

In[3]:= BarChart@tList[[All, 1]]

enter image description here

Can you recommend a code better than above ones?
POSTED BY: Valeriu Ungureanu
48 Replies
Sort By:
POSTED BY: Valeriu Ungureanu
Douglas Kubler
Douglas Kubler
Posted 9 years ago

Readability is subject to Mathematica syntax, but if one understands the plan it seems clear. (and doesn't require M11)

shows lists aligned

Testing on HP5820, Windows 7 -

In[72]:= list = RandomReal[{-10, 10}, 1000000];
Total@Ramp@list // RepeatedTiming
(Total[Abs[list]] + Total[list])/2 // RepeatedTiming

Out[73]= {0.0026, 2.49858*10^6}

Out[74]= {0.00248, 2.49858*10^6}
POSTED BY: Douglas Kubler

Dear Douglas, Thank you for an impressive code, both very clever and simple. ItÂ’s amazing to discover once again that nice things may be done on the basis of very simple and known functions, like these Total[] and Abs[].

Your code together with the above codes are as a challenge for the new fastest code proposal. It will be very amazing if such code or codes will be find.

I am doing now the new tests which include your code too. I will display the results as soon as possible .
POSTED BY: Valeriu Ungureanu
Douglas Kubler
Douglas Kubler
Posted 9 years ago 
(Total[Abs[list]] + Total[list])/2

This seems to beat all other timings on my machine (M 11).

POSTED BY: Douglas Kubler

Smart! Very nice find! Though compromises readability...
POSTED BY: Sander Huisman

For 10^6 items, the Ramp method is faster on my machine (Mac OSX V11) (using RepeatedTiming to get an accurate timing):

list = RandomReal[{-10, 10}, 1000000];
Total@Ramp@list // RepeatedTiming
(Total[Abs[list]] + Total[list])/2 // RepeatedTiming

{0.0014, 2.50381*10^6}
{0.0019, 2.50381*10^6}
POSTED BY: Sander Huisman
POSTED BY: Valeriu Ungureanu

Thanks for sharing!
POSTED BY: Sander Huisman

Thank you all for your contributions!
POSTED BY: Valeriu Ungureanu

This code doesn't work.

In[12]:= list = {-1, 2, 1, 2, -1};
Total[list /. Negative[b] -> 0]
Out[13]= 3

But, I have such code with replacement in my test list of codes and it works. It's somewhat strange in my opinion that Repeatedly is not optimized to recognize such simple problems.

Thanks, J.M. May be I will return with mixed list formed both of numerical and other types of elements.
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

Sorry 'bout that; I've edited the post. I seem to have pasted the wrong snippet.
POSTED BY: J. M.

Dear J.M., any response of yours produces improvement of the entire list of codes. I entered your code in the list after the number 7 marked by ' sign. I have changed verification of the expressions like ">0" or "<0" by checking ?Positive or ?Negative in 2 of codes. So, I have obtained two new modified pieces of code after numbers 4 and 5.

First, I have done tests on a list with 1 mln list elements and with AbsoluteTiming 48 repetitions.

tList = {
  (*  1 *) Total[Clip[list, {0, \[Infinity]}]] // AbsoluteTiming,
  (*  2 *) Plus @@ Clip[list, {0, \[Infinity]}] // AbsoluteTiming,
  (*  3 *) Total[Select[list, Positive]] // AbsoluteTiming,
  (*  4 *) Total[Cases[list, x_ /; x > 0]] // AbsoluteTiming,
  (*   '*) Total[Cases[list, _?Positive]] // AbsoluteTiming,
  (*  5 *) Plus @@ Cases[list, x_ /; x > 0] // AbsoluteTiming,
  (*   '*) Plus @@ Cases[list, _?Positive] // AbsoluteTiming,
  (*  6 *) Plus @@ Select[list, # > 0 &] // AbsoluteTiming,
  (*  7 *) Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming,
  (*   '*) Total[list /. b_?Negative -> 0] // AbsoluteTiming,
  (*  8 *) Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  (*  9 *) Plus @@ Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  (* 10 *)(s = 0; l = Length[list]; 
    Do[If[list[[i]] > 0, s += list[[i]], s], {i, l}]; s) // 
   AbsoluteTiming,
  (* 11 *)(s = 0; l = Length[list]; 
    Table[If[list[[i]] > 0, s += list[[i]], s], {i, l}][[l]]) // 
   AbsoluteTiming,
  (* 12 *)(pcf = Function[x, Piecewise[{{x, x > 0}}, 0], Listable]; 
    Total[pcf[list]]) // AbsoluteTiming,
  (* 13 *)(s = 0; l = Length[list]; 
    For[i = 0, i <= l, i++, If[list[[i]] > 0, s += list[[i]], s]]; 
    s) // AbsoluteTiming,
  (* 14 *)(s = 0; i = 1; l = Length[list]; 
    While[i <= l, If[list[[i]] > 0, s += list[[i]], s]; i++]; s) // 
   AbsoluteTiming
  }

Animated results are in the following GIF

enter image description here

For the same list with 1 mln elements, the 24 tests with RepeatedTiming are reflected by the following GIF

enter image description here

For a list with 20 elements, the results of the 120 tests with AbsoluteTiming are reflected by the GIF:

enter image description here

For the same list with 20 elements, the results of the 120 tests with RepeatedTiming are reflected by the GIF:

enter image description here

Conclusion: making an efficient code needs to know some small and very important details. Some of them are inserted in the above list of codes.
POSTED BY: Valeriu Ungureanu

Bingo?

I found that for small lists the code Total[Clip[list, {0, [Infinity]}]] is not more the fastest. The fastest is a new piece of code

Plus @@ Clip[list, {0, \[Infinity]}]

but only for lists with small dimensions ( = 20). I have done experiments with the following pieces of code

In[428]:= tList = {
  (* 1*) Total[Clip[list, {0, \[Infinity]}]] // AbsoluteTiming,
  (* 2*) Plus @@ Clip[list, {0, \[Infinity]}] // AbsoluteTiming,
  (* 3*) Total[Select[list, Positive]] // AbsoluteTiming,
  (* 4*) Total[Cases[list, x_ /; x > 0]] // AbsoluteTiming,
  (* 5*) Plus @@ Cases[list, x_ /; x > 0] // AbsoluteTiming,
  (* 6*) Plus @@ Select[list, # > 0 &] // AbsoluteTiming,
  (* 7*) Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming,
  (* 8*) Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  (* 9*) Plus @@ Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  (*10*)(s = 0; l = Length[list]; 
    Do[If[list[[i]] > 0, s += list[[i]], s], {i, l}]; s) // 
   AbsoluteTiming,
  (*11*)(s = 0; l = Length[list]; 
    Table[If[list[[i]] > 0, s += list[[i]], s], {i, l}][[l]]) // 
   AbsoluteTiming,
  (*12*)(pcf = Function[x, Piecewise[{{x, x > 0}}, 0], Listable]; 
    Total[pcf[list]]) // AbsoluteTiming,
  (*13*)(s = 0; l = Length[list]; 
    For[i = 0, i <= l, i++, If[list[[i]] > 0, s += list[[i]], s]]; 
    s) // AbsoluteTiming,
  (*14*)(s = 0; i = 1; l = Length[list]; 
    While[i <= l, If[list[[i]] > 0, s += list[[i]], s]; i++]; s) // 
   AbsoluteTiming
  }

Out[428]= {{0.0000371432, 64.4051}, {0.0000244363, 
  64.4051}, {0.0000288349, 64.4051}, {0.0000483839, 
  64.4051}, {0.0000317672, 64.4051}, {0.0000288349, 
  64.4051}, {0.0000562036, 64.4051}, {0.0000498501, 
  64.4051}, {0.0000381207, 64.4051}, {0.0000659781, 
  64.4051}, {0.0000596246, 64.4051}, {0.0000850384, 
  64.4051}, {0.0000762413, 64.4051}, {0.0000772188, 64.4051}}

I observed that if the experiments are repeated, the time results are not the same. You can view this fact in the following animation, which includes 120 repetitions of the same summations on the same list.

enter image description here

A question appears: why the times are different if the code and the list remain unchanged?

I have done the same experiment on the list with 1 mln elements, but providing repetitions only 32 times. The results may be seen in the following GIF

enter image description here

For the large lists, the time behavior of the pieces of code are more stable.

Nevertheless, one more question appears: what is the worst correct piece of code?

May be the following code a pretender to such denomination?

Total[list //. {a___, b_, c___} /; b < 0 -> {a, 0, 
     c}] // AbsoluteTiming

For small lists it works perfect! But for lists with length more than 1000 it requires very long time.
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

"I observed that if the experiments are repeated, the time results are not the same." - that's precisely why Sander was telling you to use RepeatedTiming[] instead, upthread. It should average out any time differences across different runs.

Also, you might consider using a fixed PlotRange on your charts, so that the resulting animation does not look jittery.
POSTED BY: J. M.

I have used RepeatedTiming[] instead of AbsoluteTiming[] and I have repeated summations 120 times for a list with 20 elements. A have used a fixed PlotRange[]. So, the results are these

enter image description here

With RepeatedTiming[] the fastest is still Total[Clip[list, {0, [Infinity]}]], but the difference is not so essential.

For the list with 1 mln elements, I have done 10 summations

enter image description here
POSTED BY: Valeriu Ungureanu

Nevertheless, J.M., why is so slow the following code?

Total[list //. {a___, b_, c___} /; b < 0 -> {a, 0, c}]

Must it be so slow because of its essence?

Does the expression

{a___, b_, c___} /; b < 0 -> {a, 0, c}

mean simply a substitution of negative elements by 0 or the expression has some other meaning?
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

Repeatedly matching the entire list is indeed very likely to be slow, so why do that here? You could do Total[list /. b_?Negative -> 0] if you wish to take the replacement route.
POSTED BY: J. M.

I had used formerly Procedural Programming a lot. So, I decided to test that approach and added 4 pieces of code based on the functions: Do, For, While and Table. The results are beneath.

In[55]:= list = RandomReal[{-10, 10}, 1000000];

In[56]:= tList = {
  (* 1*) Total[Clip[list, {0, \[Infinity]}]] // AbsoluteTiming,
  (* 2*) Total[Select[list, Positive]] // AbsoluteTiming,
  (* 3*) Total[Cases[list, x_ /; x > 0]] // AbsoluteTiming,
  (* 4*) Plus @@ Select[list, # > 0 &] // AbsoluteTiming,
  (* 5*) Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming,
  (* 6*) Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  (* 7*) Plus @@ Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  (* 8*)(s = 0; l = Length[list]; 
    Do[If[list[[i]] > 0, s += list[[i]], s], {i, l}]; s) // 
   AbsoluteTiming,
  (* 9*)(s = 0; l = Length[list]; 
    Table[If[list[[i]] > 0, s += list[[i]], s], {i, l}][[l]]) // 
   AbsoluteTiming,
  (*10*)(pcf = Function[x, Piecewise[{{x, x > 0}}, 0], Listable]; 
    Total[pcf[list]]) // AbsoluteTiming,
  (*11*)(s = 0; l = Length[list]; 
    For[i = 0, i <= l, i++, If[list[[i]] > 0, s += list[[i]], s]]; s) //
    AbsoluteTiming,
  (*12*)(s = 0; i = 1; l = Length[list]; 
    While[i <= l, If[list[[i]] > 0, s += list[[i]], s]; i++]; s) // 
   AbsoluteTiming
  }

Out[56]= {{0.0173669, 2.50005*10^6}, {0.627804, 
  2.50005*10^6}, {0.953728, 2.50005*10^6}, {1.16986, 
  2.50005*10^6}, {1.51738, 2.50005*10^6}, {1.7455, 
  2.50005*10^6}, {1.74073, 2.50005*10^6}, {2.89995, 
  2.50005*10^6}, {2.91044, 2.50005*10^6}, {3.53485, 
  2.50005*10^6}, {3.74655, 2.50004*10^6}, {3.80228, 2.50004*10^6}}

In[57]:= BarChart@tList[[All, 1]]

enter image description here

The code with While[] is 219 slower than the fastest code! Comments are superfluous!
POSTED BY: Valeriu Ungureanu
POSTED BY: Valeriu Ungureanu

You may want to use RepeatedTiming at least for the first one, because it is so fast! On my machine just 2.8 milliseconds!
POSTED BY: Sander Huisman

Sure, I can do it, but for our goals it's not so important! It's just for principles and ideas.
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

In short: use the thing with Select[] if you are expecting anything that isn't a real number in your list (which you can test with FreeQ[]). Otherwise, use the one with Clip[].
POSTED BY: J. M.

Yes! Simple and Clear!
POSTED BY: Valeriu Ungureanu

Another approach is:

AbsoluteTiming[pcf = Piecewise[{{x, x > 0}, {0, True}}]; Total[pcf /@ list];]

But it is slower (at least on my computer).
POSTED BY: Sander Huisman
J. M.
J. M.
Posted 9 years ago

I'd have done it this way: pcf = Function[x, Piecewise[{{x, x > 0}}, 0], Listable]; Total[pcf[tst]]
POSTED BY: J. M.

@Sander The code contains errors! Try it on a small list!

After J.M. improvement

In[32]:= list = RandomReal[{-10, 10}, 1000000];

In[33]:= tList = {
  Plus @@ Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
  Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming,
  Plus @@ Select[list, # > 0 &] // AbsoluteTiming,
  Total[Clip[list, {0, \[Infinity]}]] // AbsoluteTiming,
  AbsoluteTiming[
   pcf = Function[x, Piecewise[{{x, x > 0}}, 0], Listable]; 
   Total[pcf[list]]]
  }

Out[33]= {{1.71495, 2.50376*10^6}, {1.70818, 2.50376*10^6}, {1.3847, 
  2.50376*10^6}, {1.03566, 2.50376*10^6}, {0.0151026, 
  2.50376*10^6}, {3.1214, 2.50376*10^6}}

In[34]:= BarChart@tList[[All, 1]]

enter image description here
POSTED BY: Valeriu Ungureanu

You are right, I copied the wrong stuff from my test-notebook... But fixed by JM.. thanks
POSTED BY: Sander Huisman

The function Clip[] is useful for multiplication, too...

In[1]:= list = RandomReal[{-10, 10}, 1000000];

In[6]:= tList = {
  Times @@ Map[If[# <= 0, 1, #] &, list] // AbsoluteTiming,
  Times @@ Select[list, # > 0 &] // AbsoluteTiming,
  Times @@ Clip[list, {0, \[Infinity]}, {1, \[Infinity]}] // AbsoluteTiming
  }

Out[6]= {{1.75065, 5.286174502515*10^282473}, {1.06879, 
  5.286174502515*10^282473}, {0.268463, 5.286174502515*10^282473}}

enter image description here

But, what about the case when the list contains not only numerical elements? Can be Clip[] used?
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

Then how do you know if they're positive? How do you wish them to be dealt with?
POSTED BY: J. M.

It was a generic question, meaning that we need another approach... May be based on piece-wise functions...
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

That wasn't an answer to my question. :) If you have a list like {1, 2, x, -1, -4}, should x be added to the sum, or removed from the list before summing? Same question for {1, 2, I, -1, -4}.
POSTED BY: J. M.

Removed! List may contains elements of different types: chars, images and so on. But we want to sum only numbers. Ok. Positive ones! List may not contains numbers! In such case the result must be clear - that list doesn't contain numbers!
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

And what about the second list I gave? Complex numbers like I are neither positive nor negative.
POSTED BY: J. M.
POSTED BY: Valeriu Ungureanu

As you asked me, J.M., about the summation, we can imagine an improvement of the function Total[] that will include the criterion according to which the summation is done, i.e. 

Total[list, crit, {Subscript[n, 1],Subscript[n, 2]}]

crit means criterion and it may be, e.g., Reals, Complex, Integers, and so on...
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

Then the use of Select[]/Cases[]/Pick[] can prolly not be avoided. Use e.g. Total[Select[list, Positive]].
POSTED BY: J. M.

Thanks a lot, J.M.
POSTED BY: Valeriu Ungureanu

How about

Total[Clip[list, {0, Infinity}]]
POSTED BY: John Doty

Yes, it is the fastest! It is the lowest bar in the precedent BarChart!
POSTED BY: Valeriu Ungureanu 
In[4]:= tList = {Plus @@ Map[If[# < 0, 0, #] &, list] // 
   AbsoluteTiming, 
  Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming, 
  Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming,
  Plus @@ Select[list, # > 0 &] // AbsoluteTiming }

Out[4]= {{0.942527, 2.49442*10^6}, {0.977524, 
  2.49442*10^6}, {0.778662, 2.49442*10^6}, {0.595495, 2.49442*10^6}}
POSTED BY: Frank Kampas

Thanks!

In[6]:= list = RandomReal[{-10, 10}, 1000000];

In[10]:= tList = {
Plus @@ Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
Total@Map[If[# < 0, 0, #] &, list] // AbsoluteTiming,
Total[list /. x_ /; x < 0 -> 0] // AbsoluteTiming,
Plus @@ Select[list, # > 0 &] // AbsoluteTiming,
Total[Clip[list, {0, \[Infinity]}]] // AbsoluteTiming
}

Out[10]= {{1.76125, 2.49895*10^6}, {1.78087, 2.49895*10^6}, {1.42525,  2.49895*10^6},
{1.07893, 2.49895*10^6}, {0.0146056, 2.49895*10^6}}

In[11]:= BarChart@tList[[All, 1]]

enter image description here

Unbelievable fast!
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

Total[Clip[list, {0, ?}]] is pretty quick.
POSTED BY: J. M.

Fantastic! Thanks a lot! You are magician!
POSTED BY: Valeriu Ungureanu

I just wanted to reply this, Clip is the way to do this!

In the next release a new function will arrive that will cut this time in half (compared to Clip).

POSTED BY: Sander Huisman

It's very impressive for me!
POSTED BY: Valeriu Ungureanu
J. M.
J. M.
Posted 9 years ago

I believe I've seen that, and I have to agree. But let's not spoil things for other people. ;)
POSTED BY: J. M.

To be more specific:

Version 11 will feature Ramp that slices the timings of Clip in half:

http://reference.wolfram.com/language/ref/Ramp.html
POSTED BY: Sander Huisman

Thanks, Sander, for the information about function Ramp[]! We just have to wait for version 11 of Mma!
POSTED BY: Valeriu Ungureanu
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard