I've modified my Rope so it runs with the benchmark (and fixed some
bugs).

http://pastie.caboo.se/93256

with the included benchmark:

badcarl@navi> ruby -r lib/rope.rb benchmark.rb String
Build:   0.150000   0.080000   0.230000 (  0.234209)
Sort:   1.700000   1.850000   3.550000 (  3.613295)

badcarl@navi> ruby -r lib/rope.rb benchmark.rb Rope
Build:   0.000000   0.000000   0.000000 (  0.009324)
Sort:   0.280000   0.080000   0.360000 (  0.372736)

I'm getting around 10x speedup on sorting.


On Sep 2, 7:26 am, Carl Porth <badc... / gmail.com> wrote:
> I've done parts one and two so far.  I'll try to add more in the next
> few days.
>
> For simplicity and speed, append and prepend don't modify the
> receiver.
>
> If anyone has any questions about my code, I'll be happy to answer.
>
> Carl
>
> require "rubygems"
> require "facets"
> require "kernel/with"
> require "symbol/to_proc"
>
> class String
>   def shift
>     return nil if empty?
>     returning self[0].chr do
>       self[0] = ""
>     end
>   end
> end
>
> class Rope
>   attr_reader :left, :right, :length
>
>   def Rope.new(*args)
>     if args.size <= 2
>       super
>     else # build balanced tree
>       mid = args.size / 2
>       args[mid,2] = Rope.new(*args[mid,2])
>       Rope.new(*args)
>     end
>   end
>
>   def initialize(left="",right="")
>     @left, @right = left, right
>     @length = @left.length + @right.length
>   end
>
>   def replace(rope)
>     initialize(rope.left,rope.right)
>     self
>   end
>
>   # clean out empty strings and rebuild tree
>   def normalize
>     Rope.new(*flat_strings.reject(&:empty?))
>   end
>
>   def to_s
>     flat_strings.join('')
>   end
>
>   def append(str)
>     Rope.new(self,str)
>   end
>   alias_method :<<, :append
>
>   def prepend(str)
>     Rope.new(str,self)
>   end
>
>   def slice(start,length=@length-start)
>     if start > left.length # right
>       right.slice(start-left.length,length-left.length)
>     elsif left.length < length # left and right
>       left.slice(start,left.length) +
>       right.slice(start-left.length,length-left.length)
>     else # left
>       left.slice(start,length)
>     end
>   end
>
>   def shift
>     if letter = left.shift || right.shift
>       @length -= 1
>       letter
>     else
>       nil
>     end
>   end
>
>   def index(letter,start=0)
>     if start > left.length # right
>       left.length + right.index(letter,start - left.length)
>     else # left
>       left.index(letter,start) || left.length + right.index(letter)
>     end
>   rescue
>     nil
>   end
>
>   # TODO implement rest of methods
>   def method_missing(method, *args, &block)
>     result = to_s.send(method, *args, &block)
>     if result.is_a?(String)
>       if method.to_s =~ /!$/
>         replace(Rope.new(result))
>       else
>         Rope.new(result)
>       end
>     else
>       result
>     end
>   end
>
> protected
>
>   # traverse the tree
>   def traverse(&block)
>     @left.is_a?(Rope) ? @left.traverse(&block) : block.call(@left)
>     @right.is_a?(Rope) ? @right.traverse(&block) : block.call(@right)
>   end
>
>   # collect all the flat strings
>   def flat_strings
>     returning [] do |ary|
>       traverse { |str| ary << str }
>     end
>   end
>
> end
>
> On Aug 31, 6:19 am, Ruby Quiz <ja... / grayproductions.net> wrote:
>
> > The three rules of Ruby Quiz:
>
> > 1.  Please do not post any solutions or spoiler discussion for this quiz until
> > 48 hours have passed from the time on this message.
>
> > 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> >http://www.rubyquiz.com/
>
> > 3.  Enjoy!
>
> > Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> > on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> > if you can.
>
> > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=
>
> > by John Miller
>
> > This week's task is to implement the Rope data structure as a Ruby class.  This
> > topic comes out of the ICFP programming competition
> > (http://www.icfpcontest.com/) which had competitors manipulating a 7.5 million
> > character string this year.
>
> >         What is a Rope:
>
> > You may not realize it, but for many changes the content to a String, Ruby
> > creates a new copy of the original with the modifications applied.  For small
> > strings that are created once and read often this is actually a very efficient
> > way to do thing, but what happens when the string starts to get long, and is
> > undergoing a lot of changes?  First, the program will spend more and more of its
> > processing cycles just copying bits around.  Second, the garbage collector will
> > be called more and more often to pick up the little stringy scraps you've left
> > all over the memory.
>
> > Ropes (the name is a pun for a heavy duty string) are tree structures where a
> > node represents the concatenation of its left branch with its right, and leaves
> > are flat strings. (This is a little sloppy. A rope may contain shared subtrees,
> > and is thus really a directed acyclic graph, where the out-edges of each vertex
> > are ordered. We will continue to be sloppy.)  E.g. To prepend Text A to Text B,
> > one creates a Node (call it N1) with A as its left branch and B as its right.  
> > To further append Text C create a new Node N2 with its left branch pointing to
> > N1 and its right to C.  Easy, right?  To find out more see Boehm, Atkinson and
> > Plass "Ropes: an Alternative to Strings" at:
>
> >        http://rubyurl.com/2FRbO
>
> > The task comes in three parts, each increasing in difficulty:
>
> > Part one:
>
> > Create a Rope class that can do the following:
>
> >         a. 'append' or 'prepend' a String or another Rope
> >            (alias the << operator to the append function)    
> >         b. Return the fully concatenated text with 'to_s'
> >         c. define 'slice' to call to_s.slice  
> >         d. provide a 'length' method
>
> > Part two:
>
> > Add the following:
>
> >         a. Add the ability to 'index' a single character given a 0-based offset
> >            from the beginning of the string.
> >         b. Add the ability to 'shift' a single character from the front of a Rope.
> >            (Remove and return the character)
> >         c. Add your own 'slice' method that returns a String. Implement as many of
> >            the String method's forms as possible.  To run the example code this
> >            function will only need to understand the slice(offset,length) form.
> >            Major Bonus for Regex and Substring forms.
> >         d. "Balance" the tree with a 'normalize' method.
> >            (see Boehm, Atkinson and Plass 1319 Rebalancing)
>
> > Part three: (bonus)
>
> > Add the following:
>
> >         a. Change the 'slice' method to return a Rope. Ideally this method should
> >            do as little string copying as possible. (Doing this will well
> >            dramatically increase the speed of the example code)
> >         b. Allow 'shift' to optionally accept an integer number of characters to
> >            remove and return.
> >         c. modify the '<<' operator so that can efficiently append a few
> >            characters at a time. (see Boehm, Atkinson and Plass 1318 para. 4)
> >         d. *Major Bonus* Add the ability to append and prepend IO classes in a
> >            lazy fashion. (see Boehm, Atkinson and Plass 1318 para. 2)
>
> > The following code may help you explore how efficient your code is and show
> > where Ropes are useful.  `ruby -r /path/to/your/rope/class this_script.rb Rope`
> > will run the test with your code.  Run the script without arguments to see how
> > well String does.  Also play around with the SIZE and CHUNKS constants to get a
> > feel for how they affect performance.
>
> >         require 'benchmark'
>
> >         #This code make a String/Rope of  CHUNCKS chunks of text
> >         #each chunck is SIZE bytes long.  Each chunck starts with
> >         #an 8 byte number.  Initially the chuncks are shuffled the
> >         #qsort method sorts them into ascending order.
> >         #
> >         #pass the name of the class to use as a parameter
> >         #ruby -r rope.rb this_file Rope
>
> >         puts 'preparing data...'
> >         TextClass = Object.const_get(ARGV.shift || :String)
>
> >         def qsort(text)
> >           return TextClass.new if text.length == 0
> >           pivot = text.slice(0,8).to_s.to_i
> >           less = TextClass.new
> >           more = TextClass.new
> >           offset = 8+SIZE
> >           while (offset < text.length)
> >             i = text.slice(offset,8).to_s.to_i
> >             (i < pivot ? less : more) << text.slice(offset,8+SIZE)
> >             offset = offset + 8+SIZE
> >           end
> >           print "*"
> >           return qsort(less) << text.slice(0,8+SIZE) << qsort(more)
> >         end
>
> >         SIZE  = 512 * 1024
> >         CHUNCKS = 128
> >         CHARS = %w[R O P E]
> >         data = TextClass.new
> >         bulk_string =
> >           TextClass.new(Array.new(SIZE) { CHARS[rand(4)] }.join)
> >         puts 'Building Text...'
> >         build = Benchmark.measure do
> >           (0..CHUNCKS).sort_by { rand }.each do |n|
> >             data<< sprintf("%08i",n) << bulk_string
> >           end
> >           data.normalize  if data.respond_to? :normalize
> >         end
> >         GC.start
> >         sort = Benchmark.measure do
> >           puts "Sorting Text..."
> >           qsort(data)
> >           puts"\nEND"
> >         end
>
> >         puts "Build: #{build}Sort: #{sort}"