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

Re: Efficiency of repeatedly appending to a List

  • To: mathgroup at smc.vnet.net
  • Subject: [mg71132] Re: [mg71091] Efficiency of repeatedly appending to a List
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Thu, 9 Nov 2006 03:37:41 -0500 (EST)
  • References: <200611081114.GAA22363@smc.vnet.net>

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

Append and Prepend are O(n) operations.

The mechanism underlying Sow involves the sort of anticipatory 
allocation scheme you may have in mind; it is on average O(1). But 
unlike ordinary Mathematica expressions, Sow builds something it in 
effect "knows" is only going to grow (until it is Reap'd), and only in 
one direction.

Of course if you want fast(er than O(n)) searching AND insertion, you 
need a different data structure anyway; perhaps a tree of some, er, sort.


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Plotting multi-column data
  • Next by Date: RE: Question about trig simplify
  • Previous by thread: Efficiency of repeatedly appending to a List
  • Next by thread: Re: Efficiency of repeatedly appending to a List