Mathematica 9 is now available
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

Efficiency of repeatedly appending to a List

  • To: mathgroup at smc.vnet.net
  • Subject: [mg71091] Efficiency of repeatedly appending to a List
  • From: "Andrew Moylan" <andrew.j.moylan at gmail.com>
  • Date: Wed, 8 Nov 2006 06:14:25 -0500 (EST)

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


  • Prev by Date: Re: building a list containing elements f(i,j)
  • Next by Date: Re: Insertion into sorted list
  • Previous by thread: Re: Possible bug concerning a limit computation
  • Next by thread: Re: Efficiency of repeatedly appending to a List