Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Why are AppendTo/PrependTo so slow?

• To: mathgroup at smc.vnet.net
• Subject: [mg40776] Re: [mg40759] Why are AppendTo/PrependTo so slow?
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 17 Apr 2003 03:34:22 -0400 (EDT)
• References: <200304160537.BAA20248@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Uri Zwick wrote:
> 
> Hi,
> 
> If I understand correctly, Append[list,elem] or AppendTo[list,elem]
> cause list to be copied to a new location, with room for one
> extra element, and its running time is thus at least proportional
> to Length[list]+1. (If the elements of list, and not just pointers
> to them, are also copied, then the running time may be even larger.)
> 
> In particular, the running time of something like
> 
> list = {} ; Do[ AppendTo[ list , i ] , {i,1,n} ] ;
> 
> is O(n^2). Is that so?
> 
> (I know of course that Range[n] does the same thing and that
> there are many other alternatives...)
> 
> If this is the case, I have two very basic questions:
> 
> 1) Couldn't Mathematica use, at least in the case of AppendTo
> and PrependTo, a standard amortization technique that
> allocates, say, twice as many locations when the space allocated
> for a list is exhausted? If such a method were employed, the the
> running time of the above Do loop would be only O(n). If this is
> considered too wasteful in terms of space, then why not expand
> the list by a factor of 1.1, or 1.01? This would still have a huge
> effect on the running time. It is also easy to extend this scheme
> to handle shrinkage of lists. (See for example Chapter 17 of
> "Introduction to Algorithms", by Cormen, Leiserson, Rivest and Stein.)
> 
> 2) It is convenient, in many cases, to append or prepend elements
> to a list, and still be able to access arbitrary elements of the
> list in O(1) time. Is there an easy way of doing that in Mathematica?
> 
> (One fast alternative to PrependTo[list,elem] is list={elem,list},
> but then it is not easy to extract the i-th element added
> to the list.)
> 
> Best regards,
> 
> Uri

Yes, your loop is O(n^2).

Some of the issues you raise are addressed at

http://forums.wolfram.com/mathgroup/archive/2002/Feb/msg00359.html

Daniel Lichtblau
Wolfram Research

• References:
  • Why are AppendTo/PrependTo so slow?
    • From: Uri Zwick <zwick@tau.ac.il>