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>
- complexity of AppendTo