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

Re: Efficiency of repeatedly appending to a List

• To: mathgroup at smc.vnet.net
• Subject: [mg71262] Re: Efficiency of repeatedly appending to a List
• From: danl at wolfram.com
• Date: Sun, 12 Nov 2006 06:48:02 -0500 (EST)
• References: <200611081107.GAA21892@smc.vnet.net><eiurf1$gct$1@smc.vnet.net>

János wrote:
> On Nov 8, 2006, at 6:07 AM, Andrew Moylan wrote:
>
> > Hi all,http://groups.google.com/group/comp.soft-sys.math.mathematica/post?inreplyto=74763426bdda9b14&_done=%2Fgroup%2Fcomp.soft-sys.math.mathematica%2Fbrowse_frm%2Fthread%2F70af913d196d54dd%2F639d27dd623a22e7%3F
> >
> > 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

Some of this is discussed in

http://library.wolfram.com/infocenter/Conferences/388/

Alternatively, one can view a convenient HTML version at

http://library.wolfram.com/infocenter/Conferences/321/

UFO ("Unfit First Out") is better left to a different venue, perhaps
the Darwin Awards.


Daniel Lichtblau
Wolfram Research

• Follow-Ups:
  • Re: Re: Efficiency of repeatedly appending to a List
    • From: János <janos.lobb@yale.edu>

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