From: Nikolai Weibull <mailing-lists.ruby-core@...>
Date: 2005-03-22T08:06:26+09:00
Subject: Re: Immutable Ropes

* Mathieu Bouchard (Mar 21, 2005 23:50):
> Personally, the O(log n) element lookup is bugging me a bit, so I'd
> rather have a two-level sqrt(n)-tree that does lookup in O(1) and
> insertion in O(sqrt n), which is not as fast as O(log n) or O(1)
> insertion, but is a damn lot better than O(n) insertion. What do you
> think? (maybe this question is rhetorical because you seem to really
> want to use the original Boehm ropes implementation)

Well, O(lg n) is pretty damn fast.  At that point it becomes more
important to reason about level-1-and-2-cache-optimization and stuff
like that.  Still, I'm flexible.  What I think is important is that
there is an alternative to the long-sequence-of-bytes implementation.
Someone suggested (sorry, can't remember who) on ruby-talk in a similar
discussion that one may see the "Rope" class as an extension to String,
much as Bignum is one for Fixnum,
        nikolai

-- 
::: name: Nikolai Weibull    :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA    :: loc atm: Gothenburg, Sweden    :::
::: page: minimalistic.org   :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}