MathGroup Archive 2002

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

Search the Archive

Re: complexity of AppendTo

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