Re: List concatenation speed

• To: mathgroup at smc.vnet.net
• Subject: [mg87594] Re: List concatenation speed
• From: "Szabolcs HorvÃt" <szhorvat at gmail.com>
• Date: Mon, 14 Apr 2008 05:41:58 -0400 (EDT)
• References: <4801C556.1060408@gmail.com>

```On Sun, Apr 13, 2008 at 6:32 PM, Carlos Felippa
> Hi,
>
>  The problem with your solution is that the p's are not
>  available synchronously. They are Graphics objects, some quite
>  complicated, computed sequientally and catenated to form the Show[]
>  list. If I knew their number in advance I could use a Table
>  pre-reservation, say Table[0,{numberofobjects}],
>  to speed collocation.  (I guess I could try that with
>  an overestimate and then do a Take)
>

Another thought:

Generally, you do not need to worry if your data structure is not a
flat list while it is being built.  It is always possible to flatten
at the end.  Just try to avoid appending elements to lists if
possible.

For example, here's a recursive function that builds a list of
consecutive numbers:

In[1]:=
fun1[{elems___}, n_] := fun1[{elems, n}, n - 1]
fun1[{elems___}, 0] := {elems}

In[3]:= Block[
{\$IterationLimit = Infinity},
fun1[{}, 10000]; // Timing
]

Out[3]= {3.406, Null}

This is very slow, because it uses something that is equivalent to
append.  It can only count to 10000 in 3.5 seconds.  This algorithm is
effectively O(n^2) because it copies the list with every iteration.

Here's a much faster version, using a "singly linked list" data structure:

In[4]:=
fun2[list_, n_] := fun2[{list, n}, n - 1]
fun2[list_, 0] := list

In[6]:= Block[
{\$IterationLimit = Infinity},
Flatten[fun2[{}, 1200000]]; // Timing
]

Out[6]= {3.485, Null}

This is O(n), and it could count to 1200000 in 3.5 seconds.  The
flattening was very fast at the end.

Here's a Sow/Reap approach, also O(n), and about as fast as fun2:

In[7]:= Reap[Do[Sow[i], {i, 2300000}]][[2, 1]]; // Timing

Out[7]= {3.594, Null}

I hope this helps,
Szabolcs

```

• Prev by Date: Re: Product
• Next by Date: Re: Deleting Integrate[] transformation rule
• Previous by thread: Re: List concatenation speed
• Next by thread: Re: List concatenation speed