Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

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

Search the Archive

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


  • Prev by Date: Re: animation question
  • Next by Date: Re: Slow Integrate[] on standard integral
  • Previous by thread: Re: Efficiency of repeatedly appending to a List
  • Next by thread: Re: Re: Efficiency of repeatedly appending to a List