Re: Why are AppendTo/PrependTo so slow?
- To: mathgroup at smc.vnet.net
- Subject: [mg40777] Re: [mg40759] Why are AppendTo/PrependTo so slow?
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 17 Apr 2003 03:34:27 -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
I forgot to mention in my prior response but much of this can be
emulated using hash lookup (that is, "indexing" with one bracket). For
example, you can do along the lines of
Do[list[i]=i, {i,n}]
I show some ways to obtain data structures such as queues in a notebook
from our 1999 Developer Conference. It can be found at:
http://library.wolfram.com/conferences/devconf99/lichtblau/
This could be readily adapted to handle adding elements at both ends of
a growing (bidirectional) list.
It is not as efficient as the method you outline insofar as hash lookup
is involved, but at least one typically obtains the correct asymptotic
complexity.
Daniel Lichtblau
Wolfram Research
- References:
- Why are AppendTo/PrependTo so slow?
- From: Uri Zwick <zwick@tau.ac.il>
- Why are AppendTo/PrependTo so slow?