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

Re: four approaches to do a simple sum

• To: mathgroup at smc.vnet.net
• Subject: [mg57222] Re: [mg57171] four approaches to do a simple sum
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sat, 21 May 2005 02:39:40 -0400 (EDT)
• References: <200505200843.EAA00474@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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

• References:
  • four approaches to do a simple sum
    • From: Hui Fang <fangh73@xmu.edu.cn>