From: John Miller Date: 2007-09-07T07:01:15+09:00 Subject: Re: Twisting a Rope (#137) Hi All, I'm very sorry that this quiz ended up coming out over the labor day weekend and the start of my semester, I hardly had a chance to look at it all week, but I'm excited about what I've read. I wanted to add a couple of comments based on trying to use these thing in practice. The example was a good test case because it showed a large difference between strings and ropes. Real situations are not quite as neat and clean. In particular concatenating single characters to a string as it is build and removing them from the front as it is used are very common operations that the test case didn't measure. No one really addressed these two operations because there was not a test case to show them. James Gray wrote: > The rebalancing done here is, as the comment suggests, a textbook AVL > implementation. With an AVL tree, you subtract the left depth from the > right > depth to get a tree's balance factor. Anything in the range of -1 to 1 > is a > balanced tree. If the factor is outside of that range, one or two > rotations are > required to rebalance the tree. 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. This is to take nothing away from the solutions that came out. They were very well written and I am most humbled by them. More this is an address to the comment about "Where is the Gem?" If and when Ropes do become a general use library, these are things that I believe need to be addressed. I also am looking forward to hearing about the presentation at RubyConf. Thanks to everybody who worked on this. I wish I had more time to join in. John Miller -- Posted via http://www.ruby-forum.com/.