[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
Prev by Date:
**Re: Reduce and Indeterminate**
Next by Date:
**Re: Re: If Integrate returns no result, can we conclude that no closed-form**
Previous by thread:
**Re: List concatenation - two more methods, one truly fast**
Next by thread:
**Re: Re: List concatenation - two more methods, one truly fast**
| |