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>