MathGroup Archive 2002

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

Search the Archive

Re: complexity of AppendTo


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


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