[Date Index] [Thread Index] [Author Index]

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>