MathGroup Archive 2008

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

Search the Archive

Re: Re: List concatenation speed

  • To: mathgroup at smc.vnet.net
  • Subject: [mg87652] Re: [mg87586] Re: List concatenation speed
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Tue, 15 Apr 2008 05:49:30 -0400 (EDT)
  • References: <ftsd1e$bba$1@smc.vnet.net> <200804140940.FAA07894@smc.vnet.net>

Oliver Ruebenkoenig wrote:
> On Sun, 13 Apr 2008, carlos at colorado.edu wrote:
> 
> 
>>I am building mesh plots that require concatenation of thousands of
>>Graphics objects into one list for Show[].  This is done by appending
>>objects as they are created, and there are several ways to do that.
>>Tested 3 of them for speed using a simple object:
>>
>>    p=Table[x,{50}]; n=10000;
>>    ClearAll[poly]; poly={};
>>    Print[Timing[Do[AppendTo[poly,p],{i,1,n}]]];
>>    ClearAll[poly]; poly={};
>>    Print[Timing[Do[poly=Append[poly,p],{i,1,n}]]];
>>    ClearAll[poly]; poly={};
>>    Print[Timing[Do[poly=Join[poly,{p}],{i,1,n}]]];
>>
>>{5.8395 Second,Null}
>>{5.7206 Second,Null}
>>{6.29728 Second,Null}
>>
>>Tests were run on version 5.2 on a G5 desktop Mac. I expected Join to
>>win,
>>but it didnt.  Is there a faster way?
>>
>>
> 
> 
> Carlos,
> 
> use LISP style.
> 
> to append to a list it is always quite fast to build a nested list like 
> poly = {poly,p} in a loop and then post process it. In your case (graphic 
> primitives) you to not even need to post process since Graphics can handle 
> nested lists.
> 
> p = Line[ Table[{ Random[], Random[]}, {nr}] ];
> poly4 = List[];
> Print[Timing[
>        Do[poly4 = {poly4, p}, {i, 1, n}];
>         ]];
> 
> {0.012001 Second, Null}
> 
> Show[Graphics[poly4]]
> 
> The point is the the post processing is done outside of the loop. In case 
> you need to post process remember that Flatten only flattens to up until a 
> specific head. Like:
> 
> p = g[ Table[{ Random[], Random[]}, {nr}] ];
> poly5 = List[];
> Print[Timing[
>        Do[poly5 = {poly5, p}, {i, 1, n}];
>         poly5 = Flatten[ poly5 ];
>        ]];
> 
> 
> {0.020002 Second, Null}
> 
> poly5[[1]]
> 
> Now, the question I have is why does this performance depend on the symbol 
> name of the head?
> 
> like in
> 
> p = h[ Table[{ Random[], Random[]}, {nr}] ];
> poly5 = List[];
> Print[Timing[
>        Do[poly5 = {poly5, p}, {i, 1, n}];
>         poly5 = Flatten[ poly5 ];
>        ]];
> 
> {4.96831 Second, Null}
> 
> The problem with this is that Polygon seems to be a slow "head" and Line a 
> fast one. But perhaps I am missing something obvious here ;-)
> 
> hth,
> 
> Oliver
> 
> Oliver Ruebenkoenig, <ruebenko AT uni-freiburg.de>

No, not particularly obvious. It is an issue that has surfaced in this 
group and in sci.math.symbolic a few times. Here are a few URLs to past 
notes on this topic (apologies if the long ones get split into multiple 
lines).

http://forums.wolfram.com/mathgroup/archive/2002/Sep/msg00324.html

http://groups.google.com/group/sci.math.symbolic/browse_frm/thread/14ff6d92f2255d87/2b780d99a32be35c?lnk=gst&q=Lichtblau+reevaluation#2b780d99a32be35c

http://groups.google.com/group/sci.math.symbolic/browse_frm/thread/8b612f4d278d4602/8aa0ac821b4313d5?lnk=gst&q=Lichtblau+reevaluation#8aa0ac821b4313d5

What happens is that the Mathematica implementation of "infinite 
evaluation" (or, more correctly, evaluation until stabilization) 
requires some way to assess that there is no need to reevalute 
expressions. In some cases collisions in hashing manage to thwart the 
first level of short-circuiting reevaluation, and instead the expression 
under scrutiny must be, at least in part, traversed (to determine 
whether further evaluation is needed). When that expression is growing 
linearly in a loop, we thus can get quadratic complexity due to this 
traversal, even though reevaluation might not be necessary.


Daniel Lichtblau
Wolfram Research



  • Prev by Date: Re: Solving equations and inequalities with Reduce - how?
  • Next by Date: Re: EdgeRenderingFunction to produce edge labels in GraphPlot
  • Previous by thread: Re: List concatenation speed
  • Next by thread: Re: List concatenation speed