MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: four approaches to do a simple sum

Hui Fang wrote:
> Here I have a long list, length of 1 million, and I used 4 ways to get 
> the sum of all elements.
> In[1] = longlist=Table[Random[], {1000000}];
> Method 1:
> In[2] = Timing[sum=0; For[i=1,i<=Length[longlist],sum+=longlist[[i]]]; sum]
> Out[2] = {6.219 Second, 500358}
> Method 2:
> In[3] = Sum[longlist[[i]],{i,1,1000000}]
> Out[3] = {1.718 Second, 500358}
> Method 3:
> In[4] = Timing[Plus@@longlist]
> Out[4] = {0.407 Second, 500358}
> Method 4:
> In[5] = Fold[Plus,0,longlist]
> Out[5] = {0.156 Second, 500358}
> The computing time gets shorter and shorter from top to bottom. It's 
> easy to understand why the first two methods are slow because they 
> involved an extra variable i for loop control and basically violates the 
> principle for list manipulation "Never take a list apart".
> What I don't understand is why method 4 is faster than method 3.
> Any explanation?Or do you have an even faster method?
> Thanks a lot!
> Hui Fang

Offhand I do not know why (4) beats (3).

Here are some other fast methods. I'll up the size by a factor of 10 to 
avoid granularity issues at the fast end.

In[26]:= longlist = Table[Random[], {10^7}];

In[27]:= InputForm[Timing[Fold[Plus,0,longlist]]]
Out[27]//InputForm= {1.3499999999999983*Second, 5.000635382218386*^6}

In[28]:= InputForm[Timing[Tr[longlist]]]
Out[28]//InputForm= {0.030000000000000415*Second, 5.00063538221796*^6}

In[29]:= InputForm[Timing[Total[longlist]]]
Out[29]//InputForm= {0.019999999999999275*Second, 5.00063538221796*^6}

In situations where loop indexing is necessary one can frequently get a 
good speed improvement by resorting to Compile. In this example it is 
comparable to the Fold[Plus...] method in regards to speed.

In[30]:= InputForm[Timing[
   csum = Compile[{{ll,_Real,1}}, Module[{sum=0.},
     Do[sum+=ll[[i]], {i,Length[ll]}]; sum]]; csum[longlist]]]
Out[30]//InputForm= {1.2899999999999996*Second, 5.000635382218386*^6}

Note that there are two numeric results, differing in the last four 
digits. Offhand I do not know which is the more desirable (though I 
suspect it's the one from Total and Tr). In any case I'm sure none of 
these is sorting and adding from smallest to largest, because the sort 
process alone takes considerably longer than any of these sums.

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: Nestwhile
  • Next by Date: Re: Re: Re: How to get an answer as a Root object?
  • Previous by thread: Re: four approaches to do a simple sum
  • Next by thread: Re: four approaches to do a simple sum