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

```

• Prev by Date: Re: Position within a list[2]
• Next by Date: RE: Re: irritating little problem
• Previous by thread: complexity of AppendTo
• Next by thread: Re: complexity of AppendTo