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
<Carlos.Felippa at colorado.edu> wrote:
> 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