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
- References:
- Re: List concatenation speed
- From: Oliver Ruebenkoenig <ruebenko@uni-freiburg.de>
- Re: List concatenation speed