Re: four approaches to do a simple sum

*To*: mathgroup at smc.vnet.net*Subject*: [mg57209] Re: [mg57171] four approaches to do a simple sum*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sat, 21 May 2005 02:39:22 -0400 (EDT)*References*: <200505200843.EAA00474@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On 20 May 2005, at 17:43, 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 It is all due to the PackedArray technology. To see what happens we set the system option UnpackMessage to True: Developer`SetSystemOptions[UnpackMessage -> True]; Next we create your longlist: longlist = Table[Random[], {1000000}]; We check that we indeed got a PackedArray: In[3]:= Developer`PackedArrayQ[longlist] Out[3]= True Let's try first your slow approach: In[4]:= Timing[Plus@@longlist] Developer`FromPackedArray:: "punpack1" : Unpacking array to level 1 Out[4]= {1.43 Second,499979.} The message tells us that the packed array had to be unpacked before the addition was performed. That does not happen with your faster functions: In[5]:= Fold[Plus,0,longlist]//Timing Out[5]= {0.57 Second,499979.} However, this is far from the fastest way to accomplish this: In[6]:= Timing[Tr[longlist]] Out[6]= {0.03 Second,499979.} is much faster but In[9]:= Total[longlist]//Timing Out[9]= {0.02 Second,499979.} seems to beat it slightly. However, on repeating this I have found that Total and Tr seem to be about equally fast sometimes wiht one and sometimes with the other coming ahead. All my timing are on a 1 GHZ PowerBook. Andrzej Kozlowski Chiba, Japan http://www.akikoz.net/andrzej/index.html http://www.mimuw.edu.pl/~akoz/

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