MathGroup Archive 2005

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

Search the Archive

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/


  • Prev by Date: Re: Re: Errors from FindFit
  • Next by Date: Re: Nestwhile
  • Previous by thread: four approaches to do a simple sum
  • Next by thread: Re: four approaches to do a simple sum