MathGroup Archive 2002

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

Search the Archive

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


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