Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

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

Search the Archive

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


  • 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