MathGroup Archive 2008

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

Search the Archive

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]


  • Prev by Date: Re: Is it possible to reverse "Color Schames" function ?
  • Next by Date: How to run/call a Mathematica Notebook from another Notebook?
  • Previous by thread: Re: Speeding up a list construction
  • Next by thread: Re: Speeding up a list construction