Why are AppendTo/PrependTo so slow?
- To: mathgroup at smc.vnet.net
- Subject: [mg40759] Why are AppendTo/PrependTo so slow?
- From: Uri Zwick <zwick at tau.ac.il>
- Date: Wed, 16 Apr 2003 01:37:36 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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
- Follow-Ups:
- Re: Why are AppendTo/PrependTo so slow?
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Why are AppendTo/PrependTo so slow?
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Why are AppendTo/PrependTo so slow?