Eric Mahurin
9/7/2007 1:05:00 PM
On 9/7/07, Eugene Kalenkovich <rubify@softover.com> wrote:
> "John Miller" <jfmiller28@yahoo.com> wrote in message
> news:bc100c94508cad46e34a0d22e95334f8@ruby-forum.com...
> > Hi All,
> >
> > This was the other interesting part of the quiz. Every answer I saw
> > balanced the tree giving each leaf the same weight. The leaves on the
> > other hand varied in length between 8 characters and 512k. The
> > suggested way to balance a Rope was based on the length of the leaves in
> > such a way that longer leaves were nearer the root because presumably
> > they will be accessed more often.
> >
>
> At least two implementations did this (James Koppel's and mine). OTOH this
> added a lot of mess to the code, and a simple change on e.g. Eric's
> implementation (to use length instead of depth) will achieve practically the
> same.
>
> --EK
I'd think you'd treat depth as log2(length) and do something similar.
Instead of this for concatenation:
balance = other.depth-@depth
if balance>+1
...
elsif balance<-1
...
You could do something like this (using depth=log2(length) and a little math):
if other.length>2*@length
...
elsif @length>2*other.length
...
Maybe you'd also need some info about the smallest, largest, leftmost,
and/or rightmost leaf lengths so that you aren't trying to balance
something that can't be. I haven't thought this all the way through.
I think this is a good idea. It increases the max run-time for
slicing (but still O(log(n)), but hopefully reduces the average.
On the other hand, I don't know that it is a good assumption that
you'll be accessing longer leaves more often than shorter leaves.
This assumes random access of the elements in the rope. For example,
if you are using a rope for a text editor buffer, there will be a
you'll only be accessing a small part of the rope you'll be accessing
while typing stuff in. And at that point, you'll probably be dealing
with short leaves since things are changing around where you are
editing. You may want the most recently used closer to the root of
the tree.