MathGroup Archive 2006

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

Search the Archive

Re: Efficiency of repeatedly appending to a List


On Nov 8, 2006, at 6:07 AM, Andrew Moylan wrote:

> Hi all,
>
> Recently I asked about efficient ways to insert items into a sorted
> List such that the new list was also sorted [1]. I received  
> suggestions
> to linearly search through the list and find the right place to insert
> the new time (search time = O(N), where N is the size of the list),  
> and
> also suggestions to use a faster binary search to locate the right
> place to insert the new time (search time = O(Log[N])).
>
> This caused me to wonder about the efficiency of appending items to
> Lists in Mathematica in general. Is it an O(N) operation (i.e.,
> something akin to a realloc in C)? Or does Mathematica employ some  
> sort
> of anticipatory memory allocation scheme to make adding new  
> elements to
> lists usually faster than O(N)?
>
> Cheers,
> Andrew
>
> [1]
> http://groups-beta.google.com/group/comp.soft-sys.math.mathematica/ 
> browse_thread/thread/0c329c83dec5a1b1

Appending to large lists are very expensive.  I wish Mathemetica has  
had other constructs handy like LIFO, FIFO,  and UFO :)

János


  • Prev by Date: Re: Simplifying in Mathematica
  • Next by Date: Re: Plotting multi-column data
  • Previous by thread: Efficiency of repeatedly appending to a List
  • Next by thread: Re: Efficiency of repeatedly appending to a List