Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: List concatenation - two more methods, one truly fast

• To: mathgroup at smc.vnet.net
• Subject: [mg87805] Re: List concatenation - two more methods, one truly fast
• From: David Bailey <dave at Remove_Thisdbailey.co.uk>
• Date: Thu, 17 Apr 2008 06:58:45 -0400 (EDT)
• References: <ftv8ro$7o1$1@smc.vnet.net>

carlos at colorado.edu wrote:
> As follow up, the  following tests are more realistic in that p
> is similar to the Graphics objects produced during a mesh
> plot.  The last method (table entry substitution) is about 2 orders
> of magnitude faster. Unfortunately in actual plot generation I
> dont known n (number of objects) in advance, so that one is out.
> 
> ClearAll[poly,p,n]; poly={}; n=5000; SetRandom[1234];
> p[arg_]:= {Graphics[RGBColor[Random[],Random[],Random[]]],
>                Graphics[Polygon[{{Random[],Random[]},
>               {Random[],Random[]},{Random[],Random[]}}]]};
> Print[Timing[Do[AppendTo[poly,p[i]],{i,1,n}]][[1]]];
> ClearAll[poly]; poly={};
> Print[Timing[Do[poly=Append[poly,p[i]],{i,1,n}]][[1]]];
> ClearAll[poly]; poly={};
> Print[Timing[Do[poly=Join[poly,{p[i]}],{i,1,n}]][[1]]];
> ClearAll[poly]; poly={};
> Print[Timing[Do[poly={poly,p[i]},{i,1,n}];poly=Flatten[poly]][[1]]];
> ClearAll[poly]; poly=Table[0,{n}];
> Print[Timing[Do[poly[[i]]=p[i],{i,1,n}]][[1]];
> 
> 
> 11.3361 Second
> 11.3306 Second
> 11.7123 Second
> 7.24559 Second
> 0.061505 Second
> 
> Observation:   timing of the first 4 methods is roughly O(n^2).
> That would suggest that Mathematica does not implement a true
>  list processor in the kernel, since building a list should be O(n).
> 
> 
This result is fascinating - it is reasonable that all the solutions 
based on appending lists work O(n^2), but the nested list approach 
should not behave this way. If you repeat the timing, but without 
defining p:

n = 5000; poly = Table[0, {n}];
Print[Timing[Do[poly = {poly, p[i]}, {i, 1, n}];
     poly = Flatten[poly]][[1]]];

I get 0.02 seconds rather than 11 seconds (I obviously have a slightly 
slower machine. This means that the time depends crucially on what you 
are accumulating.

Consider the semantics of the operation:

poly = {poly, p[i]}

This will only be efficient if Mathematica 'knows' that the old value of 
poly is already fully evaluated. As I understand it, Mathematica does 
this using a hashing method, and my guess is that in this case the hash 
table overflows and the ever growing expression gets repeatedly 
evaluated - hence O(n^2).

It would be nice if someone from Wolfram could comment on these timing 
results.

Incidentally, the following method works efficiently without requiring 
the array size to be known in advance:

n = 5000; poly = Table[0, {n}];
Print[Timing[poly = Reap[Do[Sow[p[i]], {i, 1, n}]][[2, 1]]][[1]]];


David Bailey
http://www.dbaileyconsultancy.co.uk

• Follow-Ups:
  • Re: Re: List concatenation - two more methods, one truly fast
    • From: "W_Craig Carter" <ccarter@mit.edu>