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

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

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