Re: complexity of AppendTo

*To*: mathgroup at smc.vnet.net*Subject*: [mg32988] Re: complexity of AppendTo*From*: Gerhard Wesp <gwesp at cosy.sbg.ac.at>*Date*: Sat, 23 Feb 2002 02:38:06 -0500 (EST)*Organization*: Department of Computer Science, Salzburg University*References*: <200202210706.CAA02136@smc.vnet.net> <a54qo5$bsn$1@smc.vnet.net>*Reply-to*: gwesp at cosy.sbg.ac.at*Sender*: owner-wri-mathgroup at wolfram.com

Daniel Lichtblau <danl at wolfram.com> wrote: > (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 i'm not sure. the penalty is _very_ small. it would be interesting to compare the average performance of typical applications, including the standard packages, given a amortized constant time AppendTo. > (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. and while you're at it you could also add things like Deque[], LinkedList[], or even Rope[] (cf. the related c++ data structures). this would give the user the choice, which would be the best solution IMHO. 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

**References**:**complexity of AppendTo***From:*Gerhard Wesp <gwesp@cosy.sbg.ac.at>