Re: Speeding up a list construction
- To: mathgroup at smc.vnet.net
- Subject: [mg92966] Re: Speeding up a list construction
- From: Raffy <raffy at mac.com>
- Date: Tue, 21 Oct 2008 06:23:41 -0400 (EDT)
- References: <gdja5g$ief$1@smc.vnet.net>
On Oct 20, 6:10 pm, car... at colorado.edu wrote: > 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. If machine precision is acceptable (ie. much faster) Prepend[Accumulate[asum], 0] Otherwise: FoldList[Plus, 0, asum]