Re: complexity of AppendTo
- To: mathgroup at smc.vnet.net
- Subject: [mg32979] Re: [mg32943] complexity of AppendTo
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Fri, 22 Feb 2002 01:49:09 -0500 (EST)
- References: <200202210706.CAA02136@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Gerhard Wesp wrote:
>
> % math
> Mathematica 4.1 for Linux
> Copyright 1988-2000 Wolfram Research, Inc.
> -- Motif graphics initialized --
>
> In[1]:= Table[ l = Table[ {} , { n } ] ;
> Timing[ AppendTo[ l , {} ] ][[1]] , { n , 10^6 , 4*10^6 , 10^6 } ]
>
> Out[1]= {0.5 Second, 1. Second, 1.49 Second, 2. Second}
>
> In[2]:= % / %[[1]]
>
> Out[2]= {1., 2., 2.98, 4.}
>
> obviously, AppendTo takes O(n) time. why is this? if List[] is
> implemented as a linked list, the complexity should be constant. and
> even for vectors, it is trivial to implement amortized constant time
> append.
>
> (for c++ programmers: compare this to std::list<> and std::vector<>, or
> std::deque<>)
>
> regards,
> -gerhard
> --
> | voice: +43 (0)676 6253725 *** web: http://www.cosy.sbg.ac.at/~gwesp
> |
> | Passts auf, seid's vuasichdig, und lossds eich nix gfoin!
> | -- Dr. Kurt Ostbahn
(1) Append/AppendTo indeed take linear time. This is documented in the
reference quide entries for those functions. I quote from the notes to
Append (AppendTo has something similar):
"In iteratively building a structure, it is usually more efficient to
use {list, new} at each step, followed by Flatten at the end, than to
use Append[list, new] at each step."
(2) List[elems] is a fixed-size array, not a linked list. This is indeed
true of EVERY expression within Mathematica. One advantage is constant
time element access (modulo evaluation semantics issues that I am not
prepared to discuss right here).
(3) Your remark regarding amortized constant-time is of course correct.
But then one incurs a small but nonnegligeable constant factor penalty
for using a more complicated data structure. And this would be born by
everyone, when it is only helpful for the relatively uncommon task of
building a list element-wise in cases where e.g. Table cannot be used.
(4) Some of this sort of stuff is discussed in:
http://library.wolfram.com/conferences/devconf99/lichtblau/
with corresponding Mathematica notebook at
http://library.wolfram.com/conferences/devconf99/#programming
(5) We have an internal structure capable of amortized constant time
appends. I am hopeful that we will promote it to documented
functionality in a future release.
Daniel Lichtblau
Wolfram Research
- References:
- complexity of AppendTo
- From: Gerhard Wesp <gwesp@cosy.sbg.ac.at>
- complexity of AppendTo