Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: List concatenation speed

• To: mathgroup at smc.vnet.net
• Subject: [mg87586] Re: List concatenation speed
• From: Oliver Ruebenkoenig <ruebenko at uni-freiburg.de>
• Date: Mon, 14 Apr 2008 05:40:28 -0400 (EDT)
• References: <ftsd1e$bba$1@smc.vnet.net>

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>

• Follow-Ups:
  • Re: Re: List concatenation speed
    • From: Daniel Lichtblau <danl@wolfram.com>