From: Eugene Kalenkovich Date: 2007-09-08T01:35:05+09:00 Subject: Re: Twisting a Rope (#137) "Eric Mahurin" wrote in message news:29256ea00709070604p65b34a6ex8cf147e8844e74cd@mail.gmail.com... > On 9/7/07, Eugene Kalenkovich wrote: >> "John Miller" 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 > ... In reality all in-time short-cut rebalancings will perform worse than the full one. For now I do not see any algorithm better than in original article, though it is also not ideal (but good on memory usage) > > 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. > Everything is about probability of access to particular symbol. You can optimize for particular scenario (in this one - you do not want any rebalancing at all), but these optimizations will behave miserably in any other cases --EK