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: [mg92988] Re: Speeding up a list construction
  • From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
  • Date: Wed, 22 Oct 2008 05:37:55 -0400 (EDT)
  • Organization: The Open University, Milton Keynes, UK
  • References: <gdja5g$ief$1@smc.vnet.net>

carlos 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 *)

So you do not add the last component of the vector.

> 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.

     FoldList[Plus, 0, Drop[a, -1]]

works from 4.0 onwards, is O(n), and an order of magnitude faster than 
the fastest above solution.

In[8]:= Table[
  a = RandomReal[10, {10^n}];
  Timing[asum = FoldList[Plus, 0, Drop[a, -1]];][[1]], {n, 2, 7}]

Out[8]= {0.000075, 0.000759, 0.004779, 0.048831, 0.488871, 5.07134}

In[9]:= Table[
  {m, a = RandomReal[10, {10^m}];
   Timing[asum = FoldList[Plus, 0, Drop[a, -1]];][[1]],
   Timing[le = Length[a];
     asum = Table[Sum[a[[i]], {i, 1, k - 1}], {k, 1, le}];][[1]],
   Timing[len = Length[a]; asum = Table[0, {len}];
     For[i = 1, i <= len - 1, i++,
      asum[[i + 1]] = asum[[i]] + a[[i]]];][[1]]}, {m, 2, 4}]

Out[9]= {{2, 0.43905, 0.00444, 0.000616}, {3, 0.000795, 0.068962,
   0.005712}, {4, 0.004796, 6.87331, 0.056541}}

Regards,
-- Jean-Marc


  • Prev by Date: Re: FindMinimum constraints
  • Next by Date: Re: Is there a simple way to transform 1.1 to 11/10?
  • Previous by thread: Re: Speeding up a list construction
  • Next by thread: Re: Speeding up a list construction