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>