Re: Speeding up a list construction
- To: mathgroup at smc.vnet.net
- Subject: [mg93002] Re: Speeding up a list construction
- From: Albert Retey <awnl at gmx-topmail.de>
- Date: Wed, 22 Oct 2008 05:40:33 -0400 (EDT)
- References: <gdja5g$ief$1@smc.vnet.net>
Hi,
> In the innermost loop of a complicated module I have a
> list of integers
> a = {a1,a2,a3, ... an}
> The length n can be fairly large, say 10^7.
>
> I need to quickly generate
> asum = {0,a1,a1+a2,a1+a2+a3, ... }; (* n terms *)
> Two obvious solutions are
>
> n=Length[a]; asum=Table[0,{n}];
> For [i=1,i<=n-1,i++,asum[[i+1]]=asum[[i]]+a[[i]]];
>
> asum=Table[Sum[a[[i]],{i,1,k-1}],{k,1,n}];
>
> The second is compact but at O(n^2) ops is way too slow.
> The first takes O(n) ops but still somewhat slow. Question:
> can a O(n)-ops process be coded without the loop?
>
> Constraint: any solution must work in versions >=4.1.
As others have pointed out, Accumulate is hard to beat, but not
available for Versions < 6, I think. It also seems to need more memory
than e.g. FoldList, which is your best bet if the code needs to run on
Version 4, too. For machine precision numbers you can gain a little if
you Compile the FoldList, but the gain is marginal. Another issue I
found is that with your example code the last item in the list a will
not be accumulated. Is that intended or one of those index errors which
I think are the strongest argument to use something like FoldList
instead of Loops. To really get the same result as your code above you
would need:
FoldList[Plus,0,Most[a]]
or, for version 4.2:
FoldList[Plus,0,Take[a,{1,-2}]]
Also you should note that when a contains machine precision numbers only
you can further speed up by using:
FoldList[Plus,0.,Take[a,{1,-2}]]
the Dot gives a speedup of about a factor 2 on my machine...
hth,
albert