MathGroup Archive 2002

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

Search the Archive

Re: complexity of AppendTo

  • To: mathgroup at
  • Subject: [mg32988] Re: complexity of AppendTo
  • From: Gerhard Wesp <gwesp at>
  • Date: Sat, 23 Feb 2002 02:38:06 -0500 (EST)
  • Organization: Department of Computer Science, Salzburg University
  • References: <> <a54qo5$bsn$>
  • Reply-to: gwesp at
  • Sender: owner-wri-mathgroup at

Daniel Lichtblau <danl at> 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

| voice: +43 (0)676 6253725  ***  web:
| Passts auf, seid's vuasichdig, und lossds eich nix gfoin!
|  -- Dr. Kurt Ostbahn

  • Prev by Date: RE: Mean
  • Next by Date: Re: Mean
  • Previous by thread: Re: complexity of AppendTo
  • Next by thread: Re: complexity of AppendTo