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

Re: Efficiency of repeatedly appending to a List

• To: mathgroup at smc.vnet.net
• Subject: [mg71149] Re: [mg71091] Efficiency of repeatedly appending to a List
• From: János <janos.lobb at yale.edu>
• Date: Thu, 9 Nov 2006 03:38:37 -0500 (EST)
• References: <200611081107.GAA21892@smc.vnet.net>

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

• References:
  • Efficiency of repeatedly appending to a List
    • From: "Andrew Moylan" <andrew.j.moylan@gmail.com>