[QUIZ] Twisting a Rope (#137)

Discussion in 'Ruby' started by Ruby Quiz, Aug 31, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    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}"
     
    Ruby Quiz, Aug 31, 2007
    #1
    1. Advertising

  2. Ruby Quiz

    John Miller Guest

    Re: Twisting a Rope (#137)

    My apologies,

    The first line of the quiz should read:
    "You may not realize it, but for many changes to the content of a
    String,"

    I am really looking forward to seeing some ingenious solutions to this
    problem. The concept seemed very simple to me but my first attempt kept
    becoming mired down in edge cases. I hope everyone has a good weekend
    and a good Labor Day weekend to those in the US (plenty of time to work
    on this weeks quiz ;)

    John Miller


    --
    Posted via http://www.ruby-forum.com/.
     
    John Miller, Sep 1, 2007
    #2
    1. Advertising

  3. Re: Twisting a Rope (#137)

    On Sep 1, 2007, at 12:20 AM, John Miller wrote:

    > The first line of the quiz should read:
    > "You may not realize it, but for many changes to the content of a
    > String,"


    I've fixed this on the web site. Thanks for pointing it out.

    James Edward Gray II
     
    James Edward Gray II, Sep 1, 2007
    #3
  4. Ruby Quiz

    Carl Porth Guest

    Re: Twisting a Rope (#137)

    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 <> 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}"
     
    Carl Porth, Sep 2, 2007
    #4
  5. Ruby Quiz

    Carl Porth Guest

    Re: Twisting a Rope (#137)

    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 <> 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 <> 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}"
     
    Carl Porth, Sep 2, 2007
    #5
  6. Ruby Quiz

    Eric Mahurin Guest

    ------=_Part_17535_22666276.1188802265486
    Content-Type: text/plain; charset=ISO-8859-1
    Content-Transfer-Encoding: 7bit
    Content-Disposition: inline

    On 8/31/07, Ruby Quiz <> wrote:
    > This week's task is to implement the Rope data structure as a Ruby class.


    My implementation is attached along with a modified test. I made a
    few changes to what was asked, but this also gave more flexibility.
    Here is what I did:

    * Just as the implementation in the paper referenced in this quiz, my
    implementation gives immutable ropes. #<< is non-destructive, so I
    had to change the test to do <<= instead of just <<. Also, I didn't
    implement #shift, because it must be destructive. The same
    functionality can be achieved with 2 calls to #slice (one could be #at
    if you only need to shift one element). There are very good reasons
    to make ropes immutable. I'd imagine almost every other
    implementation with modifiable ropes will fail when someone starts
    modifying a sub-rope that is shared. You'd really need a good COW
    (copy-on-write) scheme to allow both transparent sharing and
    modification. I didn't see that it was worth the
    effort/complexity/risk. I chose the simple functional programming
    approach (immutable objects).

    * I chose to automatically balance the ropes during concatenation (no
    normalize). I used the same tree rotations that are used with AVL
    trees. Another option could be to treat these as red-black trees
    which might save on some rotations. One reason I automatically
    balanced is that it simplifies the interface. The user of the API
    doesn't have to worry about when to normalize. A second reason is
    that every other rope operation is O(log(n)), so there probably isn't
    much benefit in making only concatenation O(1).

    * I don't allow ropes to directly use Strings. Instead, a StringRope
    is used as a proxy for a String. To use a String directly, I would
    have had to check the class, use respond_to, modify String to look
    like a rope, etc. Instead, I just went with the pure duck-typing
    approach and made multiple Rope-like classes that use different types
    of data. My basis for these is the class ArrayRope. There is no
    reason why a rope data-structure can't be used with any sequence of
    objects instead of just characters. ArrayRope takes an Array-like
    object. An rope built out of these is to Array as a conventional rope
    is to String. I also added an IORope class to lazily work with files.
    Using IORope you could make a text editor that didn't have to read
    the whole file in at once. There is no reason you can't mix and match
    any of these leaf rope classes (depth 0) within a rope tree.

    * #each iterates through elements (i.e. characters) in the rope. It
    annoys me that String#each (and IO#each for that matter) iterates over
    lines - it should be characters (not necessarily bytes). All of the
    Enumerable methods are accessible too.

    * I used #at instead of #index because #index is used for searching in
    String/Array. Array#at is an exact match.

    The main thing I didn't do was implement any regex stuff. I don't see
    how this is doable since all of the regex methods are completely tied
    to String (not duck-typed). You'd have to convert the whole rope to
    string to do anything (which defeats the purpose of the rope).

    ------=_Part_17535_22666276.1188802265486
    Content-Type: application/x-ruby; name=quiz137.rb
    Content-Transfer-Encoding: base64
    X-Attachment-Id: f_f64jpfn2
    Content-Disposition: attachment; filename="quiz137.rb"

    CmNsYXNzIFJvcGUKICAgIGluY2x1ZGUgRW51bWVyYWJsZQogICAgIyBmb3JtIGEgYmluYXJ5IHRy
    ZWUgZnJvbSB0d28gcm9wZXMgKHBvc3NpYmx5IHN1Yi10cmVlcykKICAgIGRlZiBpbml0aWFsaXpl
    KGxlZnQscmlnaHQpCiAgICAgICAgQGxlZnQgPSBsZWZ0CiAgICAgICAgQHJpZ2h0ID0gcmlnaHQK
    ICAgICAgICBAbGxlbmd0aCA9IEBsZWZ0Lmxlbmd0aAogICAgICAgIEBsZW5ndGggPSBAbGxlbmd0
    aCtAcmlnaHQubGVuZ3RoCiAgICAgICAgQGRlcHRoID0gW2xlZnQuZGVwdGgsIHJpZ2h0LmRlcHRo
    XS5tYXgrMQogICAgZW5kCiAgICAjIG51bWJlciBvZiBlbGVtZW50cyBpbiB0aGlzIHJvcGUKICAg
    IGRlZiBsZW5ndGgKICAgICAgICBAbGVuZ3RoCiAgICBlbmQKICAgICMgZGVwdGggb2YgdGhlIHRy
    ZWUgKHRvIGhlbHAga2VlcCB0aGUgdHJlZSBiYWxhbmNlZCkKICAgIGRlZiBkZXB0aAogICAgICAg
    IEBkZXB0aAogICAgZW5kCiAgICAjIGxlZnQgcm9wZSAobm90IG5lZWRlZCB3aGVuIGRlcHRoPT0w
    KQogICAgZGVmIGxlZnQKICAgICAgICBAbGVmdAogICAgZW5kCiAgICAjIHJpZ2h0IHJvcGUgKG5v
    dCBuZWVkZWQgd2hlbiBkZXB0aD09MCkKICAgIGRlZiByaWdodAogICAgICAgIEByaWdodAogICAg
    ZW5kCiAgICAjIGFwcGVuZGVkIHJvcGUgKG5vbi1tb2RpZnlpbmcpCiAgICBkZWYgPDwob3RoZXIp
    CiAgICAgICAgIyBiYWxhbmNlIGFzIGFuIEFWTCB0cmVlCiAgICAgICAgYmFsYW5jZSA9IG90aGVy
    LmRlcHRoLUBkZXB0aAogICAgICAgIGlmIGJhbGFuY2U+KzEKICAgICAgICAgICAgbGVmdCA9IG90
    aGVyLmxlZnQKICAgICAgICAgICAgcmlnaHQgPSBvdGhlci5yaWdodAogICAgICAgICAgICBpZiBs
    ZWZ0LmRlcHRoPnJpZ2h0LmRlcHRoCiAgICAgICAgICAgICAgICAjIHJvdGF0ZSBvdGhlciB0byBy
    aWdodCBiZWZvcmUgcm90YXRpbmcgc2VsZitvdGhlciB0byBsZWZ0CiAgICAgICAgICAgICAgICAo
    c2VsZiA8PCBsZWZ0LmxlZnQpIDw8IChsZWZ0LnJpZ2h0IDw8IHJpZ2h0KQogICAgICAgICAgICBl
    bHNlCiAgICAgICAgICAgICAgICAjIHJvdGF0ZSBzZWxmK290aGVyIHRvIGxlZnQKICAgICAgICAg
    ICAgICAgIChzZWxmIDw8IGxlZnQpIDw8IHJpZ2h0CiAgICAgICAgICAgIGVuZAogICAgICAgIGVs
    c2lmIGJhbGFuY2U8LTEKICAgICAgICAgICAgaWYgQHJpZ2h0LmRlcHRoPkBsZWZ0LmRlcHRoCiAg
    ICAgICAgICAgICAgICAjIHJvdGF0ZSBzZWxmIHRvIGxlZnQgYmVmb3JlIHJvdGF0aW5nIHNlbGYr
    b3RoZXIgdG8gcmlnaHQKICAgICAgICAgICAgICAgIChAbGVmdCA8PCBAcmlnaHQubGVmdCkgPDwg
    KEByaWdodC5yaWdodCA8PCBvdGhlcikKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAg
    IyByb3RhdGUgc2VsZitvdGhlciB0byByaWdodAogICAgICAgICAgICAgICAgQGxlZnQgPDwgKEBy
    aWdodCA8PCBvdGhlcikKICAgICAgICAgICAgZW5kCiAgICAgICAgIyB1bmNvbW1lbnQgdGhpcyB0
    byBhbGxvdyBzaG9ydCBzdHJpbmdzIHRvIGNvbmNhdCBmbGF0CiAgICAgICAgI2Vsc2lmIG90aGVy
    LmRlcHRoLnplcm8/CiAgICAgICAgIyAgICAjIGFsbG93IEByaWdodCBhbmQgb3RoZXIgdG8gYmUg
    bWVyZ2VkICh3aGVuIHRoZSBsZW5ndGggaXMgc2hvcnQpCiAgICAgICAgIyAgICBAbGVmdCA8PCAo
    QHJpZ2h0IDw8IG90aGVyKQogICAgICAgIGVsc2UKICAgICAgICAgICAgc2VsZi5jbGFzcy5uZXco
    c2VsZiwgb3RoZXIpCiAgICAgICAgZW5kCiAgICBlbmQKICAgICMgc2xpY2Ugb2YgdGhlIHJvcGUK
    ICAgIGRlZiBzbGljZShzdGFydCwgbGVuKQogICAgICAgIHJldHVybiBzZWxmIGlmIHN0YXJ0Lnpl
    cm8/IGFuZCBsZW49PUBsZW5ndGgKICAgICAgICByc3RhcnQgPSBzdGFydC1AbGxlbmd0aAogICAg
    ICAgIHJldHVybiBAcmlnaHQuc2xpY2UocnN0YXJ0LCBsZW4pIGlmIHJzdGFydD4wCiAgICAgICAg
    bGxlbiA9IEBsbGVuZ3RoLXN0YXJ0CiAgICAgICAgcmxlbiA9IGxlbi1sbGVuCiAgICAgICAgaWYg
    cmxlbj4wCiAgICAgICAgICAgIEBsZWZ0LnNsaWNlKHN0YXJ0LCBsbGVuKSA8PCBAcmlnaHQuc2xp
    Y2UoMCwgcmxlbikKICAgICAgICBlbHNlCiAgICAgICAgICAgIEBsZWZ0LnNsaWNlKHN0YXJ0LCBs
    ZW4pCiAgICAgICAgZW5kCiAgICBlbmQKICAgICMgZWxlbWVudCBhdCBhIGNlcnRhaW4gcG9zaXRp
    b24gaW4gdGhlIHJvcGUKICAgIGRlZiBhdChzdGFydCkKICAgICAgICByc3RhcnQgPSBzdGFydC1A
    bGxlbmd0aAogICAgICAgIGlmIHJzdGFydDwwCiAgICAgICAgICAgIEBsZWZ0LmF0KHN0YXJ0KQog
    ICAgICAgIGVsc2UKICAgICAgICAgICAgQHJpZ2h0LmF0KHJzdGFydCkKICAgICAgICBlbmQKICAg
    IGVuZAogICAgIyBpdGVyYXRlIHRocm91Z2ggdGhlIGVsZW1lbnRzIGluIHRoZSByb3BlCiAgICBk
    ZWYgZWFjaAogICAgICAgIEBsZWZ0LmVhY2ggeyB8eHwgeWllbGQgeCB9CiAgICAgICAgQHJpZ2h0
    LmVhY2ggeyB8eHwgeWllbGQgeCB9CiAgICBlbmQKICAgICMgZmxhdHRlbiB0aGUgcm9wZSBpbnRv
    IGEgc3RyaW5nIChvcHRpb25hbGx5IHN0YXJ0aW5nIHdpdGggYSBwcmVmaXgpCiAgICBkZWYgdG9f
    cyhzPSIiKQogICAgICAgIEByaWdodC50b19zKEBsZWZ0LnRvX3MocykpCiAgICBlbmQKZW5kCgpF
    bXB0eVJvcGUgPSBPYmplY3QubmV3CmNsYXNzIDw8IEVtcHR5Um9wZQogICAgaW5jbHVkZSBFbnVt
    ZXJhYmxlCiAgICBkZWYgbGVuZ3RoCiAgICAgICAgMAogICAgZW5kCiAgICBkZWYgZGVwdGgKICAg
    ICAgICAwCiAgICBlbmQKICAgIGRlZiA8PChvdGhlcikKICAgICAgICBvdGhlcgogICAgZW5kCiAg
    ICBkZWYgPj4ob3RoZXIpCiAgICAgICAgb3RoZXIKICAgIGVuZAogICAgZGVmIHNsaWNlKHN0YXJ0
    LCBsZW4pCiAgICAgICAgc2VsZgogICAgZW5kCiAgICBkZWYgZWFjaAogICAgZW5kCiAgICBkZWYg
    dG9fcwogICAgICAgICIiCiAgICBlbmQKZW5kCgpjbGFzcyBBcnJheVJvcGUKICAgIGluY2x1ZGUg
    RW51bWVyYWJsZQogICAgZGVmIHNlbGYubmV3KCphcmdzKQogICAgICAgIGlmIGFyZ3MuZW1wdHk/
    CiAgICAgICAgICAgIEVtcHR5Um9wZQogICAgICAgIGVsc2UKICAgICAgICAgICAgc3VwZXIKICAg
    ICAgICBlbmQKICAgIGVuZAogICAgZGVmIGluaXRpYWxpemUoZGF0YSkKICAgICAgICBAZGF0YSA9
    IGRhdGEKICAgIGVuZAogICAgZGVmIGxlbmd0aAogICAgICAgIEBkYXRhLmxlbmd0aAogICAgZW5k
    CiAgICBkZWYgZGVwdGgKICAgICAgICAwCiAgICBlbmQKICAgIGRlZiA8PChvdGhlcikKICAgICAg
    ICBiYWxhbmNlID0gb3RoZXIuZGVwdGgKICAgICAgICBpZiBiYWxhbmNlPjEKICAgICAgICAgICAg
    bGVmdCA9IG90aGVyLmxlZnQKICAgICAgICAgICAgcmlnaHQgPSBvdGhlci5yaWdodAogICAgICAg
    ICAgICBpZiBsZWZ0LmRlcHRoPnJpZ2h0LmRlcHRoCiAgICAgICAgICAgICAgICAjIHJvdGF0ZSBv
    dGhlciB0byByaWdodCBiZWZvcmUgcm90YXRpbmcgc2VsZitvdGhlciB0byBsZWZ0CiAgICAgICAg
    ICAgICAgICAoc2VsZiA8PCBsZWZ0LmxlZnQpIDw8IChsZWZ0LnJpZ2h0IDw8IHJpZ2h0KQogICAg
    ICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAjIHJvdGF0ZSBzZWxmK290aGVyIHRvIGxlZnQK
    ICAgICAgICAgICAgICAgIChzZWxmIDw8IGxlZnQpIDw8IHJpZ2h0CiAgICAgICAgICAgIGVuZAog
    ICAgICAgIGVsc2lmIG90aGVyLmxlbmd0aD09MAogICAgICAgICAgICAjIG5vdGhpbmcgdG8gYXBw
    ZW5kLCBzZWxmIHdpbGwgZG8KICAgICAgICAgICAgc2VsZgogICAgICAgIGVsc2UKICAgICAgICAg
    ICAgUm9wZS5uZXcoc2VsZiwgb3RoZXIpCiAgICAgICAgZW5kCiAgICBlbmQKICAgIGRlZiBzbGlj
    ZShzdGFydCwgbGVuKQogICAgICAgIHJldHVybiBzZWxmIGlmIHN0YXJ0Lnplcm8/IGFuZCBsZW49
    PUBkYXRhLmxlbmd0aAogICAgICAgICMgZGVwZW5kIG9uIHJ1YnkncyBDT1cgbWVjaGFuaXNtIHRv
    IGp1c3QgcmVmZXJlbmNlIHRoZSBzbGljZSBkYXRhCiAgICAgICAgc2VsZi5jbGFzcy5uZXcoQGRh
    dGEuc2xpY2Uoc3RhcnQsIGxlbikpCiAgICBlbmQKICAgIGRlZiBhdChzdGFydCkKICAgICAgICBA
    ZGF0YS5hdChzdGFydCkKICAgIGVuZAogICAgZGVmIGVhY2gKICAgICAgICBAZGF0YS5lYWNoIHsg
    fHh8IHlpZWxkIHggfQogICAgZW5kCiAgICBkZWYgdG9fcyhzPSIiKQogICAgICAgIHMuY29uY2F0
    KEBkYXRhLnRvX3MpCiAgICBlbmQKZW5kCgpjbGFzcyBTdHJpbmdSb3BlIDwgQXJyYXlSb3BlCiAg
    ICAjIHVuY29tbWVudCB0aGlzIHRvIGFsbG93IHNob3J0IHN0cmluZ3MgdG8gY29uY2F0IGZsYXQK
    ICAgICNTSE9SVCA9IDY0CiAgICAjZGVmIDw8KG90aGVyKQogICAgIyAgICBpZiBvdGhlci5sZW5n
    dGg9PTAKICAgICMgICAgICAgIHNlbGYKICAgICMgICAgZWxzaWYgQGRhdGEubGVuZ3RoK290aGVy
    Lmxlbmd0aDw9U0hPUlQKICAgICMgICAgICAgICMganVzdCBtZXJnZSB0aGUgc3RyaW5ncyBpZiB0
    aGUgdG90YWwgbGVuZ3RoIGlzIHNob3J0CiAgICAjICAgICAgICBzZWxmLmNsYXNzLm5ldyhAZGF0
    YStvdGhlci50b19zKQogICAgIyAgICBlbHNlCiAgICAjICAgICAgICBzdXBlcgogICAgIyAgICBl
    bmQKICAgICNlbmQKICAgIGRlZiBhdChzdGFydCkKICAgICAgICBAZGF0YVtzdGFydF0KICAgIGVu
    ZAogICAgZGVmIGVhY2gKICAgICAgICBAZGF0YS5lYWNoX2NoYXIgeyB8eHwgeWllbGQgeCB9CiAg
    ICBlbmQKZW5kCgpjbGFzcyBJT1JvcGUgPCBBcnJheVJvcGUKICAgIGluY2x1ZGUgRW51bWVyYWJs
    ZQogICAgZGVmIGluaXRpYWxpemUoaW8sIHN0YXJ0PTAsIGxlbmd0aD0oaW8uc2VlaygwLElPOjpT
    RUVLX0VORCk7aW8ucG9zLXN0YXJ0KSkKICAgICAgICBAaW8gPSBpbwogICAgICAgIEBzdGFydCA9
    IHN0YXJ0CiAgICAgICAgQGxlbmd0aCA9IGxlbmd0aAogICAgZW5kCiAgICBkZWYgbGVuZ3RoCiAg
    ICAgICAgQGxlbmd0aAogICAgZW5kCiAgICBkZWYgc2xpY2Uoc3RhcnQsIGxlbikKICAgICAgICBy
    ZXR1cm4gc2VsZiBpZiBzdGFydC56ZXJvPyBhbmQgbGVuPT1AbGVuZ3RoCiAgICAgICAgIyBqdXN0
    IHJlZmVyZW5jZSBhIGRpZmZlcmVudCBwYXJ0IG9mIHRoZSBJTwogICAgICAgIHNlbGYuY2xhc3Mu
    bmV3KEBpbywgQHN0YXJ0K3N0YXJ0LCBsZW4pCiAgICBlbmQKICAgIGRlZiBhdChzdGFydCkKICAg
    ICAgICBAaW8ucG9zID0gQHN0YXJ0K3N0YXJ0CiAgICAgICAgQGlvLmdldGMKICAgIGVuZAogICAg
    ZGVmIGVhY2gKICAgICAgICBAaW8ucG9zID0gQHN0YXJ0CiAgICAgICAgQGxlbmd0aC50aW1lcyB7
    IHlpZWxkIEBpby5nZXRjIH0KICAgIGVuZAogICAgZGVmIHRvX3Mocz0iIikKICAgICAgICBAaW8u
    cG9zID0gQHN0YXJ0CiAgICAgICAgcy5jb25jYXQoQGlvLnJlYWQoQGxlbmd0aCkpCiAgICBlbmQK
    ZW5kCgoKcmVxdWlyZSAnYmVuY2htYXJrJwoKI1RoaXMgY29kZSBtYWtlIGEgU3RyaW5nL1JvcGUg
    b2YgIENIVU5LUyBjaHVua3Mgb2YgdGV4dAojZWFjaCBjaHVuayBpcyBTSVpFIGJ5dGVzIGxvbmcu
    ICBFYWNoIGNodW5rIHN0YXJ0cyB3aXRoCiNhbiA4IGJ5dGUgbnVtYmVyLiAgSW5pdGlhbGx5IHRo
    ZSBjaHVua3MgYXJlIHNodWZmbGVkIHRoZQojcXNvcnQgbWV0aG9kIHNvcnRzIHRoZW0gaW50byBh
    c2NlbmRpbmcgb3JkZXIuCiMKI3Bhc3MgdGhlIG5hbWUgb2YgdGhlIGNsYXNzIHRvIHVzZSBhcyBh
    IHBhcmFtZXRlcgojcnVieSAtciByb3BlLnJiIHRoaXNfZmlsZSBSb3BlCgpwdXRzICdwcmVwYXJp
    bmcgZGF0YS4uLicKVGV4dENsYXNzID0gT2JqZWN0LmNvbnN0X2dldChBUkdWLnNoaWZ0IHx8IDpT
    dHJpbmcpCgpkZWYgcXNvcnQodGV4dCkKIHJldHVybiBUZXh0Q2xhc3MubmV3IGlmIHRleHQubGVu
    Z3RoID09IDAKIHBpdm90ID0gdGV4dC5zbGljZSgwLDgpLnRvX3MudG9faQogbGVzcyA9IFRleHRD
    bGFzcy5uZXcKIG1vcmUgPSBUZXh0Q2xhc3MubmV3CiBvZmZzZXQgPSA4K1NJWkUKIHdoaWxlIChv
    ZmZzZXQgPCB0ZXh0Lmxlbmd0aCkKICAgaSA9IHRleHQuc2xpY2Uob2Zmc2V0LDgpLnRvX3MudG9f
    aQogICBpZiBpIDwgcGl2b3QKICAgICAgIGxlc3MgPDw9IHRleHQuc2xpY2Uob2Zmc2V0LDgrU0la
    RSkKICAgZWxzZQogICAgICAgbW9yZSA8PD0gdGV4dC5zbGljZShvZmZzZXQsOCtTSVpFKQogICBl
    bmQKICAgb2Zmc2V0ID0gb2Zmc2V0ICsgOCtTSVpFCiBlbmQKIHByaW50ICIqIgogcmV0dXJuIHFz
    b3J0KGxlc3MpIDw8IHRleHQuc2xpY2UoMCw4K1NJWkUpIDw8IHFzb3J0KG1vcmUpCmVuZAoKc3Jh
    bmQoMTIzNDU2Nzg5KQpTSVpFICA9IDUxMiAqIDEwMjQKQ0hVTktTID0gMTI4CkNIQVJTID0gJXdb
    UiBPIFAgRV0KYnVsa19zdHJpbmcgPSBBcnJheS5uZXcoU0laRSkgeyBDSEFSU1tyYW5kKDQpXSB9
    LmpvaW4KYnVsa190ZXh0ID0gVGV4dENsYXNzLm5ldyhidWxrX3N0cmluZykKYnVpbGQgPSBbXQpk
    YXRhID0gbmlsCjgudGltZXMgewpwdXRzICdCdWlsZGluZyBUZXh0Li4uJwpHQy5zdGFydApidWls
    ZCA8PCBCZW5jaG1hcmsubWVhc3VyZSBkbwogZGF0YSA9IFRleHRDbGFzcy5uZXcKICgwLi5DSFVO
    S1MpLnNvcnRfYnkgeyByYW5kIH0uZWFjaCBkbyB8bnwKICAgZGF0YSA8PD0gVGV4dENsYXNzLm5l
    dyhzcHJpbnRmKCIlMDhpIixuKSkgPDwgYnVsa190ZXh0CiBlbmQKIGRhdGEubm9ybWFsaXplICBp
    ZiBkYXRhLnJlc3BvbmRfdG8/IDpub3JtYWxpemUKZW5kCn0KYnVpbGQgPSBidWlsZC5pbmplY3Qg
    eyB8bWluLGN1cnwgY3VyLnRvdGFsPG1pbi50b3RhbCA/IGN1ciA6IG1pbiB9CgoKIyBzZWxmLWNo
    ZWNrIHRoYXQgdGhlIGluZGljZXMgYWRkIHVwCnN1bSA9IDAKMC5zdGVwKGRhdGEubGVuZ3RoLTEs
    IDgrU0laRSkgeyB8b2Zmc2V0fAogICAgc3VtICs9IGRhdGEuc2xpY2Uob2Zmc2V0LDgpLnRvX3Mu
    dG9faQogICAgYnVsa19kYXRhID0gZGF0YS5zbGljZShvZmZzZXQrOCxTSVpFKS50b19zCiAgICBy
    YWlzZSgiI3tidWxrX2RhdGFbMCwxMF19Li4uLiAhPSAje2J1bGtfc3RyaW5nWzAsMTBdfS4uLi4i
    KSBpZiBidWxrX2RhdGEhPWJ1bGtfc3RyaW5nCn0KZXhwZWN0ZWRfc3VtID0gKENIVU5LUyooQ0hV
    TktTKzEpKS8yCnJhaXNlKCIje3N1bX0hPSN7ZXhwZWN0ZWRfc3VtfSIpIGlmIHN1bSE9ZXhwZWN0
    ZWRfc3VtCgpzb3J0ID0gW10Kc29ydGVkX2RhdGEgPSBuaWwKOC50aW1lcyB7CkdDLnN0YXJ0CnNv
    cnQgPDwgQmVuY2htYXJrLm1lYXN1cmUgZG8KIHB1dHMgIlNvcnRpbmcgVGV4dC4uLiIKIHNvcnRl
    ZF9kYXRhID0gcXNvcnQoZGF0YSkKIHB1dHMiXG4iCmVuZAp9CnNvcnQgPSBzb3J0LmluamVjdCB7
    IHxtaW4sY3VyfCBjdXIudG90YWw8bWluLnRvdGFsID8gY3VyIDogbWluIH0KCnB1dHMgIkJ1aWxk
    OiAje2J1aWxkfVNvcnQ6ICN7c29ydH0iCgojIHNlbGYtY2hlY2sgdGhhdCB0aGUgaW5kaWNlcyBh
    cmUgc29ydGVkCmkgPSAwCjAuc3RlcChzb3J0ZWRfZGF0YS5sZW5ndGgtMSwgOCtTSVpFKSB7IHxv
    ZmZzZXR8CiAgICBkYXRhaSA9IHNvcnRlZF9kYXRhLnNsaWNlKG9mZnNldCw4KS50b19zCiAgICBy
    YWlzZSgiI3tkYXRhaX0hPSN7aX0iKSBpZiBkYXRhaS50b19pIT1pCiAgICBidWxrX2RhdGEgPSBz
    b3J0ZWRfZGF0YS5zbGljZShvZmZzZXQrOCxTSVpFKS50b19zCiAgICByYWlzZSgiI3tidWxrX2Rh
    dGFbMCwxMF19Li4uLiAhPSAje2J1bGtfc3RyaW5nWzAsMTBdfS4uLi4iKSBpZiBidWxrX2RhdGEh
    PWJ1bGtfc3RyaW5nCiAgICBpICs9IDEKfQoKCg==
    ------=_Part_17535_22666276.1188802265486--
     
    Eric Mahurin, Sep 3, 2007
    #6
  7. Ruby Quiz

    Eric Mahurin Guest

    On 9/3/07, Eric Mahurin <> wrote:
    > On 8/31/07, Ruby Quiz <> wrote:
    > > This week's task is to implement the Rope data structure as a Ruby class.

    >
    > My implementation is attached along with a modified test. I made a
    > few changes to what was asked, but this also gave more flexibility.


    Forgot about the results. Here's what I found on my machine:

    String
    Build: 0.120000 0.080000 0.200000 ( 0.206264)
    Sort: 1.680000 0.420000 2.100000 ( 2.112934)
    VmPeak: 1192112 kB
    VmSize: 493708 kB

    StringRope
    Build: 0.010000 0.000000 0.010000 ( 0.014414)
    Sort: 0.150000 0.020000 0.170000 ( 0.176734)
    VmPeak: 38940 kB
    VmSize: 37920 kB

    so, 20X faster for build and 12.4X faster for sort. Memory looks to
    be 10-30X smaller. I ran the build and sort 8 times during the
    benchmark and took the min. The memory kept increasing for the String
    runs for each of these 8 iterations which doesn't make sense.
     
    Eric Mahurin, Sep 3, 2007
    #7
  8. --eJnRUKwClWJh1Khz
    Content-Type: text/plain; charset=us-ascii
    Content-Disposition: inline

    On Fri, Aug 31, 2007 at 10:19:54PM +0900, Ruby Quiz wrote:
    > 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.


    I happened to have implemented ropes in OCaml recently, so I generated a Ruby
    extension using rocaml to see how well it would perform.

    Without further ado, here are the results I'm getting for SIZE = 512 * 1024,
    CHUNKS = 512:

    $ time ruby -r himadri_choudhury.rb bm.rb Rope
    Build: 0.130000 0.000000 0.130000 ( 0.129476)
    Sort: 10.340000 0.050000 10.390000 ( 10.648223)

    $ time ruby -rocaml_rope bm.rb OCaml::Rope
    Build: 0.020000 0.000000 0.020000 ( 0.018946)
    Sort: 0.100000 0.000000 0.100000 ( 0.108499)

    $ ruby eric_mahurin.rb StringRope
    [...]
    Build: 0.060000 0.000000 0.060000 ( 0.057299)
    Sort: 0.870000 0.000000 0.870000 ( 0.896493)

    For SIZE = 1024, CHUNKS = 16384:

    $ ruby eric_mahurin.rb StringRope
    [...]
    Build: 3.470000 0.040000 3.510000 ( 3.588875)
    Sort: 89.110000 0.700000 89.810000 ( 92.179962)

    $ time ruby -rocaml_rope bm.rb OCaml::Rope
    [...]
    Build: 0.360000 0.000000 0.360000 ( 0.378352)
    Sort: 3.940000 0.040000 3.980000 ( 4.079140)

    At that point the pure Ruby rope is taking over 6 times more memory than
    the OCaml one. I ascribe this to iv_tbls being very heavy and to memory
    fragmentation.

    I benchmarked Himadri's implementation first and was surprised by the
    exceedingly large speed difference --- I expected one, not two orders of
    magnitude for this code, as there's enough Ruby code in common in qsort to
    mask the speed gains in the rope operations. However, Eric's solution proved
    that it was just due to a slow Ruby implementation.

    Here's the interface definition (extconf.rb):


    EXT_NAME = "ocaml_rope"
    OCAML_PACKAGES = %w[]
    CAML_LIBS = %w[]
    CAML_OBJS = %w[]
    CAML_FLAGS = ""
    CAML_INCLUDES = []

    require 'rocaml'

    Interface.generate("ocaml_rope") do |iface|
    def_class("Rope", :under => "OCaml") do |c|
    rope = c.abstract_type

    fun "empty", UNIT => rope, :as => "new_empty"
    fun "of_string", STRING => rope, :as => "new_from_string"

    method "sub", [rope, INT, INT] => rope, :as => "slice"
    method "concat", [rope, rope] => rope
    method "length", rope => INT
    method "get", [rope, INT] => INT
    method "to_string", rope => STRING, :as => "to_s"
    end
    end

    require 'rocaml_extconf'


    As you can see, OCaml::Rope is purely functional, and the interface differs a
    bit from that expected by bm.rb (a modified version that works with immutable
    ropes is attached), so I adapted it with the following ocaml_rope.rb, which
    also loads the extension:


    module OCaml # Rope will be placed in this module
    end

    require "ocaml_rope.so"

    module OCaml
    class Rope
    def self.new(str = "")
    case str
    when String; new_from_string str
    when Rope; str
    when ""; new_empty
    else new_from_string(str.to_str) rescue new_from_string(str.to_s)
    end
    end

    def prepend(rope)
    rope.append(self)
    end

    alias_method :append, :concat
    alias_method :<<, :append
    end
    end


    The OCaml code is attached, in case anybody wants to look at it.
    Incidentally, it weighs a bit under 220 lines, which is also the amount taken
    by Himadri's and Eric's solutions. Unlike them, rope.ml features O(1)
    concatenation for small elements; this accounts for a large part of the code
    and the complexity of some patterns. O(1) concatenation doesn't really affect
    performance in the use case exerted by bm.rb anyway.

    --
    Mauricio Fernandez - http://eigenclass.org

    --eJnRUKwClWJh1Khz
    Content-Type: text/plain; charset=us-ascii
    Content-Disposition: attachment; filename="bm.rb"

    require 'benchmark'

    #This code make a String/Rope of CHUNKS chunks of text
    #each chunck is SIZE bytes long. Each chunk starts with
    #an 8 byte number. Initially the chunks 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 = (ARGV.shift || "String").split(/::/).inject(Object){|s,x| s.const_get(x)}

    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
    if i < pivot
    less <<= text.slice(offset,8+SIZE)
    else
    more <<= text.slice(offset,8+SIZE)
    end
    offset = offset + 8+SIZE
    end
    #print "*"
    return qsort(less) << text.slice(0,8+SIZE) << qsort(more)
    end

    SIZE = 1 * 1024
    CHUNKS = 32768
    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..CHUNKS).sort_by { rand }.each do |n|
    data = data << TextClass.new(sprintf("%08i",n)) << bulk_string
    end
    data = 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}"


    --eJnRUKwClWJh1Khz
    Content-Type: text/plain; charset=us-ascii
    Content-Disposition: attachment; filename="rope.ml"

    type t =
    Empty
    (* left, left size, right, right size, height *)
    | Concat of t * int * t * int * int
    | Leaf of string

    type forest_element = { mutable c : t; mutable len : int }

    let str_append = (^)
    let empty_str = ""
    let string_of_string_list l = String.concat "" l

    let max_height = 48

    let leaf_size = 256

    exception Out_of_bounds

    let empty = Empty

    (* by construction, there cannot be Empty or Leaf "" leaves *)
    let is_empty = function Empty -> true | _ -> false

    let height = function
    Empty | Leaf _ -> 0
    | Concat(_,_,_,_,h) -> h

    let rec length = function
    Empty -> 0
    | Leaf s -> String.length s
    | Concat(_,cl,_,cr,_) -> cl + cr

    let make_concat l r =
    let hl = height l and hr = height r in
    let cl = length l and cr = length r in
    Concat(l, cl, r, cr, if hl >= hr then hl + 1 else hr + 1)

    let min_len =
    let fib_tbl = Array.make max_height 0 in
    let rec fib n = match fib_tbl.(n) with
    0 ->
    let last = fib (n - 1) and prev = fib (n - 2) in
    let r = last + prev in
    let r = if r > last then r else last in (* check overflow *)
    fib_tbl.(n) <- r; r
    | n -> n
    in
    fib_tbl.(0) <- leaf_size + 1; fib_tbl.(1) <- 3 * leaf_size / 2 + 1;
    Array.init max_height (fun i -> if i = 0 then 1 else fib (i - 1))

    let max_length = min_len.(Array.length min_len - 1)

    let concat_fast l r = match l with
    Empty -> r
    | Leaf _ | Concat(_,_,_,_,_) ->
    match r with
    Empty -> l
    | Leaf _ | Concat(_,_,_,_,_) -> make_concat l r

    (* based on Hans-J. Boehm's *)
    let add_forest forest rope len =
    let i = ref 0 in
    let sum = ref empty in
    while len > min_len.(!i+1) do
    if forest.(!i).c <> Empty then begin
    sum := concat_fast forest.(!i).c !sum;
    forest.(!i).c <- Empty
    end;
    incr i
    done;
    sum := concat_fast !sum rope;
    let sum_len = ref (length !sum) in
    while !sum_len >= min_len.(!i) do
    if forest.(!i).c <> Empty then begin
    sum := concat_fast forest.(!i).c !sum;
    sum_len := !sum_len + forest.(!i).len;
    forest.(!i).c <- Empty;
    end;
    incr i
    done;
    decr i;
    forest.(!i).c <- !sum;
    forest.(!i).len <- !sum_len

    let concat_forest forest =
    Array.fold_left (fun s x -> concat_fast x.c s) Empty forest

    let rec balance_insert rope len forest = match rope with
    Empty -> ()
    | Leaf _ -> add_forest forest rope len
    | Concat(l,cl,r,cr,h) when h >= max_height || len < min_len.(h) ->
    balance_insert l cl forest;
    balance_insert r cr forest
    | x -> add_forest forest x len (* function or balanced *)

    let balance r =
    match r with
    Empty -> Empty
    | Leaf _ -> r
    | _ ->
    let forest = Array.init max_height (fun _ -> {c = Empty; len = 0}) in
    balance_insert r (length r) forest;
    concat_forest forest

    let bal_if_needed l r =
    let r = make_concat l r in
    if height r < max_height then r else balance r

    let concat_str l = function
    Empty | Concat(_,_,_,_,_) -> invalid_arg "concat_str"
    | Leaf rs as r ->
    let lenr = String.length rs in
    match l with
    | Empty -> r
    | Leaf ls ->
    let slen = lenr + String.length ls in
    if slen <= leaf_size then Leaf (str_append ls rs)
    else make_concat l r (* height = 1 *)
    | Concat(ll, cll, Leaf lrs, clr, h) ->
    let slen = clr + lenr in
    if clr + lenr <= leaf_size then
    Concat(ll, cll, Leaf (str_append lrs rs), slen, h)
    else
    bal_if_needed l r
    | _ -> bal_if_needed l r

    let append_char c r = concat_str r (Leaf (String.make 1 c))

    let concat l = function
    Empty -> l
    | Leaf _ as r -> concat_str l r
    | Concat(Leaf rls,rlc,rr,rc,h) as r ->
    (match l with
    Empty -> r
    | Concat(_,_,_,_,_) -> bal_if_needed l r
    | Leaf ls ->
    let slen = rlc + String.length ls in
    if slen <= leaf_size then
    Concat(Leaf(str_append ls rls), slen, rr, rc, h)
    else
    bal_if_needed l r)
    | r -> (match l with Empty -> r | _ -> bal_if_needed l r)

    let prepend_char c r = concat (Leaf (String.make 1 c)) r

    let rec get i = function
    Empty -> raise Out_of_bounds
    | Leaf s ->
    if i >= 0 && i < String.length s then String.unsafe_get s i
    else raise Out_of_bounds
    | Concat (l, cl, r, cr, _) ->
    if i < cl then get i l
    else get (i - cl) r

    let of_string = function
    s when String.length s = 0 -> Empty
    | s ->
    let min (x:int) (y:int) = if x <= y then x else y in
    let rec loop r s len i =
    if i < len then (* len - i > 0, thus Leaf "" can't happen *)
    loop (concat r (Leaf (String.sub s i (min (len - i) leaf_size))))
    s len (i + leaf_size)
    else
    r
    in loop Empty s (String.length s) 0

    let rec sub start len = function
    Empty -> if start <> 0 || len <> 0 then raise Out_of_bounds else Empty
    | Leaf s ->
    if len > 0 then (* Leaf "" cannot happen *)
    (try Leaf (String.sub s start len) with _ -> raise Out_of_bounds)
    else if len < 0 || start < 0 || start > String.length s then
    raise Out_of_bounds
    else Empty
    | Concat(l,cl,r,cr,_) ->
    if start < 0 || len < 0 || start + len > cl + cr then raise Out_of_bounds;
    let left =
    if start = 0 then
    if len >= cl then
    l
    else sub 0 len l
    else if start > cl then Empty
    else if start + len >= cl then
    sub start (cl - start) l
    else sub start len l in
    let right =
    if start <= cl then
    let upto = start + len in
    if upto = cl + cr then r
    else if upto < cl then Empty
    else sub 0 (upto - cl) r
    else sub (start - cl) len r
    in
    concat left right

    let to_string r =
    let rec strings l = function
    Empty -> l
    | Leaf s -> s :: l
    | Concat(left,_,right,_,_) -> strings (strings l right) left
    in
    string_of_string_list (strings [] r)

    let insert start rope r =
    concat (concat (sub 0 start r) rope) (sub start (length r - start) r)

    let remove start len r =
    concat (sub 0 start r) (sub (start + len) (length r - start - len) r)

    let () =
    let r name v = Callback.register ("Rope." ^ name) v in
    r "empty" (fun () -> empty);
    r "of_string" of_string;
    r "sub" (fun r n m -> sub n m r);
    r "concat" concat;
    r "length" length;
    r "get" (fun r i -> get i r);
    r "to_string" to_string

    --eJnRUKwClWJh1Khz--
     
    Mauricio Fernandez, Sep 3, 2007
    #8
  9. ------=_Part_17604_4118040.1188812565770
    Content-Type: text/plain; charset=ISO-8859-1
    Content-Transfer-Encoding: 7bit
    Content-Disposition: inline

    On 8/31/07, Ruby Quiz <> wrote:
    > 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.


    My solution deviates slightly from the problem specification.
    The most important difference is that instead of implementing
    a binary tree to store the strings, they are all stored in an
    array instead.

    The class itself is quite long, since I wanted to implement
    many of the methods of the built-in String class. Some of the
    methods will require significant work to actually implement.
    Most notably the Regexp-related methods, since there is no
    way to instruct the Regexp matcher to ask for more characters
    once it has reached the end of a string.

    Actually, all String methods are implemented, by implementing
    method missing and delegating to the composed string if the
    string class can handle the method. After delegating to the
    string class, we convert any String result to a new rope and
    we also make sure to replace our content by the string we
    delegated to, to make sure that destructive methods works as
    expected.

    In fact, we replace the content of our rope as soon as to_s
    is called. since the reason for lazy concatenation is to
    avoid the concatenation cost, we can just as well keep the
    concatenated string when we already had to pay the price.

    The benchmark results are:

    # String
    Build: 0.170000 0.150000 0.320000 ( 0.324341)
    Sort: 3.470000 3.630000 7.100000 ( 7.126741)

    # ArrayRope
    Build: 0.010000 0.010000 0.020000 ( 0.009744)
    Sort: 0.130000 0.000000 0.130000 ( 0.138330)

    # ArrayRope (with dup)
    Build: 0.240000 0.160000 0.400000 ( 0.402201)
    Sort: 0.160000 0.000000 0.160000 ( 0.163022)

    For the unprotected case, sorting was ~52 times faster,
    and building was ~33 times faster.

    However, since the string class is not immutable, there is a
    slight problem with this approach. The strings could added
    to the rope could be modified "under the hood". We can easily
    protect against that by making copies of the strings when we
    add them to the rope. Since the built-in String shares the
    actual data between the two instances (until they change),
    this is not so much of a memory issue as one could expect.

    By adding dup (in initialize/append/prepend) we end up with
    the following times, which trades of some of our speed/memory
    for a bit of safety. (This is actually the submitted solution)

    Compared with the string approach, building is now (for obvious
    reasons) slower than the String, but only about 25%.
    Sorting is still much faster than the String case, namely ~44
    times as fast.

    !g

    ------=_Part_17604_4118040.1188812565770
    Content-Type: application/octet-stream; name=array_rope.rb
    Content-Transfer-Encoding: base64
    X-Attachment-Id: f_f64rore4
    Content-Disposition: attachment; filename="array_rope.rb"

    Y2xhc3MgQXJyYXkKICBkZWYgdXBwZXJfYm91bmQodmFsdWUpCiAgICBsbywgaGkgPSAwLCBzaXpl
    LTEKICAgIHdoaWxlIGxvIDw9IGhpCiAgCSAgbWlkID0gKGxvICsgaGkpIC8gMgogIAkgIGlmIHZh
    bHVlID49IGF0KG1pZCkKCSAgICAgIGxvID0gbWlkICsgMQogIAkgIGVsc2UKCSAgICAgIGhpID0g
    bWlkIC0gMQogIAkgIGVuZAogIAllbmQKICAgIGxvCiAgZW5kCmVuZAoKY2xhc3MgQXJyYXlSb3Bl
    CiAgYXR0cl9yZWFkZXIgOnNlZ21lbnRzCiAgZGVmIGluaXRpYWxpemUoKnNlZ21lbnRzKQogICAg
    cmFpc2Ugc2VnbWVudHMuaW5zcGVjdCBpZiBzZWdtZW50cy5hbnk/IHsgfHN8IHMubmlsPyB9CiAg
    ICBAc2VnbWVudHMgPSBzZWdtZW50cy5tYXAgeyB8c3wgcy5kdXAgfQogICAgY29tcHV0ZV9vZmZz
    ZXRzCiAgZW5kCgogIGRlZiBjb21wdXRlX29mZnNldHMKICAgIGwgPSAwCiAgICBAb2Zmc2V0cyA9
    IEBzZWdtZW50cy5tYXAgeyB8c3wgbCArPSBzLmxlbmd0aCB9CiAgICBAb2Zmc2V0cy51bnNoaWZ0
    IDAgICAgCiAgZW5kCgogIGRlZiBsZW5ndGgKICAgIEBvZmZzZXRzLmxhc3QKICBlbmQKICBhbGlh
    cyA6c2l6ZSA6bGVuZ3RoCiAgZGVmIGVtcHR5PwogICAgQHNlZ21lbnRzLmVtcHR5PwogIGVuZAoK
    ICBkZWYgdG9fcwogICAgY2FzZSBAc2VnbWVudHMuc2l6ZQogICAgd2hlbiAwOyAiIgogICAgd2hl
    biAxOyBAc2VnbWVudHMuZmlyc3QuZHVwCiAgICBlbHNlCiAgICAgICMgV2hlbiBjb252ZXJ0aW5n
    IHRvIGEgc3RyaW5nLCB3ZSBtdXN0IGRvIHRoZSBleHBlbnNpdmUKICAgICAgIyBjb25jYXRlbmF0
    aW9uLCBzbyBsZXRzIGhpamFjayB0aGF0IGluZm9ybWF0aW9uIGFuZCB1c2UgdGhlCiAgICAgICMg
    bmV3IHN0cmluZyBpbnRlcm5hbGx5IGFzIHdlbGwuCiAgICAgIHMgPSAoQHNlZ21lbnRzICogIiIp
    CiAgICAgIEBzZWdtZW50cywgQG9mZnNldHMgPSBbc10sIFswLHMubGVuZ3RoXQogICAgICBzLmR1
    cAogICAgZW5kCiAgZW5kCiAgCiAgZGVmIG1ldGhvZF9taXNzaW5nKG0sICphcmdzLCAmYmxvY2sp
    CiAgICAjIE1ha2Ugc3VyZSB3ZSBoYW5kbGUgcmVtYWluaW5nIHN0cmluZyBtZXRob2RzIGFjY29y
    ZGluZ2x5CiAgICBpZiAiIi5yZXNwb25kX3RvPyhtKQogICAgICBzID0gdG9fcwogICAgICByID0g
    cy5fX3NlbmRfXyhtLCAqYXJncywgJmJsb2NrKQoKICAgICAgIyBHdWVzcyB0aGF0IHRoaXMgaXMg
    dGhlIHJpZ2h0IHRoaW5nIHRvIGRvCiAgICAgIGlmIHIuZXF1YWw/IHMKICAgICAgICByID0gc2Vs
    ZiAKICAgICAgZWxzaWYgci5pc19hPyBTdHJpbmcKICAgICAgICByID0gQXJyYXlSb3BlLm5ldyBy
    CiAgICAgIGVuZAoKICAgICAgIyBUaGUgbWV0aG9kIG1pZ2h0IGNoYW5nZSB0aGUgY29udGVudHMg
    b2YgdGhlIHN0cmluZwogICAgICByZXBsYWNlIHMKCiAgICAgIHIKICAgIGVsc2UKICAgICAgc3Vw
    ZXIobSwgKmFyZ3MsICZibG9jaykKICAgIGVuZAogIGVuZAogIAogIGRlZiByZXNwb25kc190bz8o
    bSkKICAgICMgTWFrZSBzdXJlIHdlIGhhbmRsZSByZW1haW5pbmcgc3RyaW5nIG1ldGhvZHMgYWNj
    b3JkaW5nbHkKICAgIHN1cGVyIHx8ICIiLnJlc3BvbmRzX3RvPyhtKQogIGVuZAogIAogIGRlZiBh
    cHBlbmQoKnNlZ21lbnRzKQogICAgc2VnbWVudHMuZWFjaCBkbyB8c3wKICAgICAgaWYgcy5pc19h
    PyBBcnJheVJvcGUKICAgICAgICBhcHBlbmQgKnMuc2VnbWVudHMKICAgICAgZWxzaWYgIXMuZW1w
    dHk/CiAgICAgICAgQHNlZ21lbnRzIDw8IHMuZHVwCiAgICAgICAgQG9mZnNldHMgPDwgQG9mZnNl
    dHMubGFzdCArIHMubGVuZ3RoCiAgICAgIGVuZAogICAgZW5kCiAgICBzZWxmCiAgZW5kCiAgYWxp
    YXMgOjw8IDphcHBlbmQKICBkZWYgcHJlcGVuZCgqc2VnbWVudHMpCiAgICBzZWdtZW50cy5lYWNo
    IGRvIHxzfAogICAgICBpZiBzLmlzX2E/IEFycmF5Um9wZQogICAgICAgIHByZXBlbmQgKnMuc2Vn
    bWVudHMKICAgICAgZWxzaWYgIXMuZW1wdHk/CiAgICAgICAgQHNlZ21lbnRzLnVuc2hpZnQgcy5k
    dXAKICAgICAgICBjb21wdXRlX29mZnNldHMKICAgICAgZW5kCiAgICBlbmQKICAgIHNlbGYKICBl
    bmQKICAKICBkZWYgc2xpY2Uoc3RhcnQsbGVuZ3RoPW5pbCkKICAgIHJldHVybiB0b19zLnNsaWNl
    KHN0YXJ0LCBsZW5ndGh8fDApIGlmIHN0YXJ0LmlzX2E/IFJlZ2V4cAogICAgcmV0dXJuIGluZGV4
    KHN0YXJ0KSBpZiBzdGFydC5pc19hPyBTdHJpbmcKICAgIGlmICFsZW5ndGggJiYgc3RhcnQuaXNf
    YT8oUmFuZ2UpCiAgICAgIGxlbmd0aCA9IHN0YXJ0Lmxhc3QgLSBzdGFydC5maXJzdCAtIChleGNs
    dWRlX2VuZD8gPyAxIDogMCkKICAgICAgc3RhcnQgPSBzdGFydC5maXJzdAogICAgZW5kCiAgICBz
    dGFydCA9IHNlbGYubGVuZ3RoICsgc3RhcnQgaWYgc3RhcnQgPCAwCiAgICBpZiBzdGFydCA8IDAg
    fHwgc3RhcnQgPiBzZWxmLmxlbmd0aAogICAgICBuaWwKICAgIGVsc2lmICFsZW5ndGgKICAgICAg
    QHNlZ21lbnRzLmRldGVjdCB7IHxzfCAoc3RhcnQgLT0gcy5sZW5ndGgpIDwgMCB9LnNsaWNlKHN0
    YXJ0KQogICAgZWxzZQogICAgICBpbmRleCA9IEBvZmZzZXRzLnVwcGVyX2JvdW5kKHN0YXJ0KSAt
    IDEKICAgICAgcm9wZSA9IEFycmF5Um9wZS5uZXcoCiAgICAgICAgQHNlZ21lbnRzLmF0KGluZGV4
    KS5zbGljZShzdGFydCAtIEBvZmZzZXRzLmF0KGluZGV4KSwgbGVuZ3RoKSkKICAgICAgcmVtYWlu
    ID0gbGVuZ3RoIC0gcm9wZS5sZW5ndGgKICAgICAgd2hpbGUgcmVtYWluID4gMCAmJiAoaW5kZXgg
    Kz0gMSkgPCBAc2VnbWVudHMubGVuZ3RoCiAgICAgICAgcm9wZSA8PCBAc2VnbWVudHMuYXQoaW5k
    ZXgpLnNsaWNlKDAsIHJlbWFpbikKICAgICAgICByZW1haW4gPSBsZW5ndGggLSByb3BlLmxlbmd0
    aAogICAgICBlbmQKICAgICAgcm9wZQogICAgZW5kCiAgZW5kCiAgYWxpYXMgOltdIDpzbGljZQog
    IAogIGRlZiBkdXA7IEFycmF5Um9wZS5uZXcoKkBzZWdtZW50cyk7IGVuZAogIGFsaWFzIDpjbG9u
    ZSA6ZHVwCiAgCiAgZGVmICsob3RoZXIpOyBkdXAgPDwgb3RoZXI7IGVuZAoKICBpbmNsdWRlIEVu
    dW1lcmFibGUKICBkZWYgZWFjaCAmYmxvY2sKICAgIGxhc3QgPSBuaWwKICAgIEBzZWdtZW50cy5l
    YWNoIGRvIHxzfAogICAgICBzLmVhY2ggZG8gfGx8CiAgICAgICAgaWYgbFstMV0gPT0gP1xuCiAg
    ICAgICAgICB5aWVsZChsYXN0ID8gIiN7bGFzdH0je2x9IiA6IGwpCiAgICAgICAgICBsYXN0ID0g
    bmlsCiAgICAgICAgZWxzZQogICAgICAgICAgbGFzdCA9ICIje2xhc3R9I3tsfSIKICAgICAgICBl
    bmQKICAgICAgZW5kCiAgICBlbmQKICAgIHlpZWxkIGxhc3QgaWYgbGFzdAogICAgc2VsZgogIGVu
    ZAogIGRlZiBlYWNoX2J5dGUgJmJsb2NrCiAgICBAc2VnbWVudHMuZWFjaCB7IHxzfCBzLmVhY2hf
    Ynl0ZSAmYmxvY2sgfQogICAgc2VsZgogIGVuZAoKICBpbmNsdWRlIENvbXBhcmFibGUKICAld1s8
    PT4gY2FzZWNtcF0uZWFjaCBkbyB8bXwKICAgIG1vZHVsZV9ldmFsIDw8LUVPTQogICAgICBkZWYg
    I3ttfShvdGhlcikKICAgICAgICByZXN1bHQgPSAwCiAgICAgICAgQHNlZ21lbnRzLnppcChAb2Zm
    c2V0cykgZG8gfHNlZ21lbnQsb2Zmc2V0fAogICAgICAgICAgcmVzdWx0ID0gb3RoZXIuc2xpY2Uo
    b2Zmc2V0LCBzZWdtZW50Lmxlbmd0aCkuI3ttfShzZWdtZW50KQogICAgICAgICAgYnJlYWsgaWYg
    cmVzdWx0ICE9IDAKICAgICAgICBlbmQKICAgICAgICAtcmVzdWx0CiAgICAgIGVuZAogICAgRU9N
    CiAgZW5kCiAgZGVmID09KG90aGVyKQogICAgQG9mZnNldHMubGFzdCA9PSBvdGhlci5sZW5ndGgg
    JiYgKHNlbGYgPD0+IG90aGVyKSA9PSAwCiAgZW5kCiAgYWxpYXMgOmVxbD8gOj09CiAgCiAgZGVm
    IGhhc2g7IEBzZWdtZW50cy5pbmplY3QoMCkgeyB8aCwgc3wgaCArIHMuaGFzaCB9OyBlbmQKCiAg
    ZGVmIHJlcGxhY2Ugc3RyCiAgICBAc2VnbWVudHMsIEBvZmZzZXRzID0gW10sIFswXQogICAgYXBw
    ZW5kIHN0cgogIGVuZAoKICAld1tkb3duY2FzZSB1cGNhc2UgY2FwaXRhbGl6ZSBzd2FwY2FzZV0u
    ZWFjaCBkbyB8bXwKICAgIG1vZHVsZV9ldmFsIDw8LUVPTQogICAgICBkZWYgI3ttfSEKICAgICAg
    ICBAc2VnbWVudHMuaW5qZWN0KG5pbCkgZG8gfHIsc3wKICAgICAgICAgIHMuI3sgbSB9ISA/IHNl
    bGYgOiByCiAgICAgICAgZW5kCiAgICAgIGVuZAogICAgRU9NCiAgZW5kCiAgCiAgZGVmIHJzdHJp
    cCEKICAgIHdoaWxlIEBzZWdtZW50cy5sYXN0LnJzdHJpcCEKICAgICAgaWYgQHNlZ21lbnRzLmxh
    c3QuZW1wdHk/CiAgICAgICAgQHNlZ21lbnRzLnBvcAogICAgICAgIEBvZmZzZXRzLnBvcAogICAg
    ICBlbHNlCiAgICAgICAgQG9mZnNldHNbLTFdID0gQG9mZnNldHNbLTJdICsgQHNlZ21lbnRzWy0x
    XS5sZW5ndGgKICAgICAgICByZXR1cm4gc2VsZgogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICBk
    ZWYgbHN0cmlwIQogICAgd2hpbGUgQHNlZ21lbnRzLmZpcnN0LmxzdHJpcCEKICAgICAgaWYgQHNl
    Z21lbnRzLmZpcnN0LmVtcHR5PwogICAgICAgIEBzZWdtZW50cy5zaGlmdAogICAgICBlbHNlCiAg
    ICAgICAgY29tcHV0ZV9vZmZzZXRzCiAgICAgICAgcmV0dXJuIHNlbGYKICAgICAgZW5kCiAgICBl
    bmQKICBlbmQKCiAgZGVmIHN0cmlwIQogICAgcnN0cmlwISA/IGxzdHJpcCEgfHwgc2VsZiA6IGxz
    dHJpcCEKICBlbmQKCiAgZGVmIGNob3AhCiAgICB1bmxlc3MgQHNlZ21lbnRzLmVtcHR5PwogICAg
    ICBpZiBAc2VnbWVudHMubGFzdC5jaG9wIQogICAgICAgIGlmIEBzZWdtZW50cy5sYXN0LmVtcHR5
    PwogICAgICAgICAgQHNlZ21lbnRzLnBvcAogICAgICAgICAgQG9mZnNldHMucG9wCiAgICAgICAg
    ZWxzZQogICAgICAgICAgQG9mZnNldHNbLTFdIC09IDEKICAgICAgICBlbmQKICAgICAgICByZXR1
    cm4gc2VsZgogICAgICBlbmQKICAgIGVuZAogIGVuZAogIAogIGRlZiBjaG9tcCEoc2VwPSQvKQog
    ICAgdW5sZXNzIEBzZWdtZW50cy5lbXB0eT8KICAgICAgaWYgQHNlZ21lbnRzLmxhc3QuY2hvbXAh
    KHNlcCkKICAgICAgICBpZiBAc2VnbWVudHMubGFzdC5lbXB0eT8KICAgICAgICAgIEBzZWdtZW50
    cy5wb3AKICAgICAgICAgIEBvZmZzZXRzLnBvcAogICAgICAgIGVsc2UKICAgICAgICAgIEBvZmZz
    ZXRzWy0xXSAtPSAxCiAgICAgICAgZW5kCiAgICAgICAgcmV0dXJuIHNlbGYKICAgICAgZW5kCiAg
    ICBlbmQKICBlbmQKICAKICBkZWYgbmV4dCEKICAgIChAc2VnbWVudHMubGVuZ3RoLTEpLmRvd250
    bygwKSBkbyB8aXwKICAgICAgcyA9IEBzZWdtZW50cy5hdChpKQogICAgICBuID0gcy5uZXh0CiAg
    ICAgIHIgPSBuLmxlbmd0aCA+IHMubGVuZ3RoCiAgICAgIHMucmVwbGFjZSBuCiAgICAgIHMuc2xp
    Y2UhKC0xKSBpZiByICYmIGkgPiAwCiAgICAgIGJyZWFrIHVubGVzcyByCiAgICBlbmQKICAgIHNl
    bGYKICBlbmQKCiAgJXdbZG93bmNhc2UgdXBjYXNlIGNhcGl0YWxpemUgc3dhcGNhc2UgbHN0cmlw
    IHJzdHJpcCBzdHJpcCBjaG9wIGNob21wIG5leHRdLmVhY2ggZG8gfG18CiAgICBtb2R1bGVfZXZh
    bCA8PC1FT00KICAgICAgZGVmICN7bX1zdHJpcAogICAgICAgIGQgPSBkdXAKICAgICAgICBkLiN7
    bX1zdHJpcCEKICAgICAgICBkCiAgICAgIGVuZAogICAgRU9NCiAgZW5kCmVuZAo=
    ------=_Part_17604_4118040.1188812565770--
     
    Gustav Munkby, Sep 3, 2007
    #9
  10. On Mon, Sep 03, 2007 at 05:52:31PM +0900, Mauricio Fernandez wrote:
    > I happened to have implemented ropes in OCaml recently, so I generated a Ruby
    > extension using rocaml to see how well it would perform.
    >

    [...]
    > For SIZE = 1024, CHUNKS = 16384:
    >
    > $ ruby eric_mahurin.rb StringRope
    > [...]
    > Build: 3.470000 0.040000 3.510000 ( 3.588875)
    > Sort: 89.110000 0.700000 89.810000 ( 92.179962)
    >
    > $ time ruby -rocaml_rope bm.rb OCaml::Rope
    > [...]
    > Build: 0.360000 0.000000 0.360000 ( 0.378352)
    > Sort: 3.940000 0.040000 3.980000 ( 4.079140)


    Also for laughs, playing with the GC parameters and with a qsort implemented
    in OCaml:

    $ OCAMLRUNPARAM=s=512k ruby -rocaml_rope bm.rb OCaml::Rope
    [...]
    Build: 0.290000 0.000000 0.290000 ( 0.290908)
    Sort: 3.410000 0.040000 3.450000 ( 3.547792)
    Sort': 0.830000 0.000000 0.830000 ( 0.845180)

    Yielding the expected >100x gain over Ruby.

    The interface part:

    method "qsort", [rope, INT] => rope
    method "qsort2", [rope, INT] => rope


    I implemented the qsort function both in functional and imperative style, for
    the sake of those who prefer something that reads similarly to the Ruby
    version. The two variants are equally fast.


    let (<<) = concat (* OCaml allows you to define new operators *)
    let to_i = int_of_string
    let to_s = to_string

    let rec qsort' size = function
    Empty -> Empty
    | rope ->
    let pivot = to_i (to_s (sub 0 8 rope)) in
    let len = 8 + size in
    let less = ref Empty in
    let more = ref Empty in
    let off = ref len in
    while !off < length rope do
    let slice = sub !off len rope in
    if to_i (to_s (sub !off 8 rope)) < pivot then
    less := !less << slice
    else
    more := !more << slice;
    off := !off + len
    done;
    qsort' size !less << sub 0 len rope << qsort' size !more


    let rec qsort size = function
    Empty -> Empty
    | rope ->
    let rec loop r pivot off len max less more =
    if off < max then begin
    if to_i (to_s (sub off 8 r)) < pivot then
    loop r pivot (off+len) len max (less << (sub off len r)) more
    else
    loop r pivot (off+len) len max less (more << (sub off len r))
    end else (less, more) in

    let pivot = to_i (to_s (sub 0 8 rope)) in
    let len = 8 + size in
    let less, more = loop rope pivot len len (length rope) Empty Empty in
    qsort size less << sub 0 len rope << qsort size more


    --
    Mauricio Fernandez - http://eigenclass.org
     
    Mauricio Fernandez, Sep 3, 2007
    #10
  11. Ruby Quiz

    Ari Brown Guest

    Ok, So I'm still trying to figure out what stores the characters in a
    Rope. A string or an array?

    Judging from the fact that you have ArrayRope, I'm thinking it might
    be an Array.

    On Sep 3, 2007, at 5:42 AM, Gustav Munkby wrote:


    > # ArrayRope
    > Build: 0.010000 0.010000 0.020000 ( 0.009744)
    > Sort: 0.130000 0.000000 0.130000 ( 0.138330)
    >
    > # ArrayRope (with dup)
    > Build: 0.240000 0.160000 0.400000 ( 0.402201)
    > Sort: 0.160000 0.000000 0.160000 ( 0.163022)


    Help!
    Ari
    --------------------------------------------|
    If you're not living on the edge,
    then you're just wasting space.
     
    Ari Brown, Sep 3, 2007
    #11
  12. On 9/3/07, Ari Brown <> wrote:
    >
    > Ok, So I'm still trying to figure out what stores the characters in a
    > Rope. A string or an array?
    >
    > Judging from the fact that you have ArrayRope, I'm thinking it might
    > be an Array.
    >


    The actual characters are stored in strings. The rope is an array of strings,
    stored in the @segments instance variable.

    !g
     
    Gustav Munkby, Sep 3, 2007
    #12
  13. Here is my solution. As a side note, it was probably not the best idea to
    stick to the benchmarking code in the quiz, as it forced not the best design
    decisions (I'd rather not have default constructor for Rope, and for sure -
    no normalizing 'in place'). But - what's done is done.
    For slice variants I've decided to have two argument ones in #slice, and one
    arg - in #[]

    Results:
    String

    Build: 0.188000 0.032000 0.220000 ( 0.219000)
    Sort: 1.578000 0.843000 2.421000 ( 2.422000)

    Rope

    Build: 0.031000 0.000000 0.031000 ( 0.031000)
    Sort: 0.203000 0.000000 0.203000 ( 0.234000)

    Code:
    -------------------------------------------------------------------------------------------------------------------------
    class NilClass
    def length; 0; end
    end

    class String
    def shift
    return nil if empty?
    res=self[0]
    self[0]=""
    res
    end
    end

    class Rope
    attr_reader :length, :left, :right

    def initialize(left=nil,right=nil)
    @left=left if left
    @right=right if right
    @length=left.length+right.length
    end

    def append(what)
    len=what.length
    if (len>0)
    @left=self.dup if @right.length>0
    @right=what
    @length+=len
    end
    self
    end

    alias << append

    def prepend(what)
    len=what.length
    if (len>0)
    @right=self.dup if @left.length>0
    @left=what
    @length+=len
    end
    self
    end

    def to_s
    @_s
    end

    def [](i)
    return i.match(self.to_s)[0] if i.kind_of? Regexp
    if i.kind_of? Range
    pos,last=i.first,i.last
    pos=@length+pos if pos<0
    last=@length+last if last<0
    return nil if pos<0 || last<0
    return slice(pos,last-pos+1)
    end
    i=@length+i if i<0
    return nil if i<0 || i>@length-1
    llen=@left.length
    i<llen ? @left : @right[i-llen]
    end

    def []=(i,val)
    #fixnum only
    i=@length+i if i<0
    ""=0 if i<0 || i>@length-1
    @length+=val.length-1
    llen=@left.length
    i<llen ? @left=val : @right[i-llen]=val
    end

    def slice(pos,len)
    return pos.match(self.to_s)[len] if pos.kind_of? Regexp
    pos=@length+pos if pos<0
    return nil if pos<0 || len<0 || pos>@length-1
    llen=@left.length
    return @left.slice(pos,len) if pos+len<=llen
    return @right.slice(pos-llen, len) if pos>=llen
    Rope.new(@left.slice(pos,len),@right.slice(0,len+pos-llen))
    end

    def shift
    return nil if @length==0
    @length-=1
    res=@left.length>0 ? @left.shift : @right.shift
    @left=nil if @left.length==0
    @right=nil if @right.length==0
    res
    end

    def normalize
    r=Rebalancer.new(@length)
    self.traverse { |str| r.append(str) }
    @left,@right=r.get_ropes
    end

    def traverse(&blck)
    @left.kind_of?(String) ? yield(@left) : @left.traverse(&blck) if @left
    @right.kind_of?(String) ? yield(@right) : @right.traverse(&blck) if
    @right
    end

    end

    class Rebalancer
    def initialize len
    @limits=[1,2]
    @slots=[]
    n=2
    @limits<<n=@limits[-2]+@limits[-1] while n<len
    end

    def append str
    @slots[0]=@slots[0] ? Rope.new(@slots[0],str) : str
    i=0
    while @slots.length>@limits
    @slots[i+1]=@slots[i+1] ? Rope.new(@slots[i+1],@slots) : @slots
    @slots=nil
    i+=1
    end
    end

    def get_ropes
    @slots.compact!
    (@slots.length-1).times { |i|
    @slots[i+1]=@slots[i+1] ? Rope.new(@slots[i+1],@slots) : @slots
    @slots=nil
    i+=1
    }
    [@slots[-1].left,@slots[-1].right]
    end
    end
     
    Eugene Kalenkovich, Sep 3, 2007
    #13
  14. Ruby Quiz

    ara.t.howard Guest

    On Sep 3, 2007, at 7:48 PM, Eric Mahurin wrote:

    >
    > CPU(user+sys,sec) mem(peak,MB)
    > ------------------- ------------
    > build sort total build sort class
    > ----- ---- ----- ----- ---- -----
    > 0.10 1.70 1.80 287 1327 String
    > 0.01 0.27 0.28 22 153 Porth::Rope
    > 0.02 0.83 0.85 22 34 Choudhury::Rope *
    > 0.02 0.06 0.08 22 29 Mahurin::StringRope +
    > 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    > 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    > 0.07 0.10 0.17 151 151 Munkby::ArrayRope
    > 0.02 0.73 0.75 22 655 Kalenkovich::Rope *
    >
    > CPU : minimum from 40 iterations
    > mem : peak over the 40 iterations
    >



    enough of this nonsense already! where is the gem! ;)


    a @ http://drawohara.com/
    --
    we can deny everything, except that we have the possibility of being
    better. simply reflect on that.
    h.h. the 14th dalai lama
     
    ara.t.howard, Sep 4, 2007
    #14
  15. Ruby Quiz

    Carl Porth Guest

    Re: Twisting a Rope (#137)

    Eric, thanks for taking the time to run benchmarks for everyone's
    solutions. It clears things up when they're run all on the same
    machine.

    Carl

    On Sep 3, 6:48 pm, "Eric Mahurin" <> wrote:
    > On 8/31/07, Ruby Quiz <> wrote:
    >
    > > This week's task is to implement the Rope data structure as a Ruby class.

    >
    > I modified my implementation a bit more and provided results along
    > with the other ruby implementations (sorry Mauricio) submitted. The
    > benchmark test I used is attached. It can run the original build/sort
    > that assumes mutable ropes and a build/sort that can also be used with
    > immutable ropes (in addition to mutable ropes). These tests assume
    > that << can only take another rope. I included some testing to ensure
    > the results are correct. I also used the linux /proc/$$/status to get
    > the memory.
    >
    > Mahurin::StringRope is almost the same as my previous submission. The
    > main change was handling a boundary case better so I don't
    > unecessarily concat an empty rope (a < should have been a <=) - this
    > almost doubled the performance.
    >
    > I added the class Mahurin::MutableStringRope which is a wrapper around
    > an immutable rope. I just reassign the instance variable (@rope) to
    > make changes. I implemented a bunch of String/Array mutable methods
    > in this class. This wrapper class hurt performance much more than I
    > expected (double the run-time).
    >
    > I also tried out not auto-balancing and using an explicit normalize
    > (Mahurin::DenormalStringRope). This gave much faster build time as
    > expected, but the sort time slowed down just as much. I guess for
    > this random data set (I use a fixed seed), qsort doesn't keep the tree
    > balanced (pivot doesn't necessarily partition equally). The larger
    > depth for the non-auto-balanced rope hurts the slice time. I think
    > biting the bullet for auto-balancing is the better way to go.
    >
    > I added a subclass for handling flattening concatenations of short
    > strings (Mahurin::ShortStringRope) just to be complete. It isn't
    > useful in this benchmark, but also doesn't hurt much (within the 0.01
    > second error margin).
    >
    > CPU(user+sys,sec) mem(peak,MB)
    > ------------------- ------------
    > build sort total build sort class
    > ----- ---- ----- ----- ---- -----
    > 0.10 1.70 1.80 287 1327 String
    > 0.01 0.27 0.28 22 153 Porth::Rope
    > 0.02 0.83 0.85 22 34 Choudhury::Rope *
    > 0.02 0.06 0.08 22 29 Mahurin::StringRope +
    > 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    > 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    > 0.07 0.10 0.17 151 151 Munkby::ArrayRope
    > 0.02 0.73 0.75 22 655 Kalenkovich::Rope *
    >
    > CPU : minimum from 40 iterations
    > mem : peak over the 40 iterations
    >
    > * : self-checking failed
    > + : immutable benchmark needed
    >
    > test2.rb
    > 4KDownload
    >
    > mahurin.rb
    > 11KDownload
     
    Carl Porth, Sep 4, 2007
    #15
  16. "Eric Mahurin" wrote in message
    news:...

    > CPU(user+sys,sec) mem(peak,MB)
    > ------------------- ------------
    > build sort total build sort class
    > ----- ---- ----- ----- ---- -----
    > 0.10 1.70 1.80 287 1327 String
    > 0.01 0.27 0.28 22 153 Porth::Rope
    > 0.02 0.83 0.85 22 34 Choudhury::Rope *
    > 0.02 0.06 0.08 22 29 Mahurin::StringRope +
    > 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    > 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    > 0.07 0.10 0.17 151 151 Munkby::ArrayRope
    > 0.02 0.73 0.75 22 655 Kalenkovich::Rope *
    >
    > CPU : minimum from 40 iterations
    > mem : peak over the 40 iterations
    >
    > * : self-checking failed
    > + : immutable benchmark needed


    Eric, thanks a lot for your test, it helped me to find a bug in my solution.
    The only thing I do not understand - you've changed the game rules on flight
    by making "data = data.normalize" instead of "data.normalize". I'm wondering
    how could you get sorting time > 0 for my solution (as it played by old
    rules and would give you nothing for such assignment)? :)

    Anyway, I'm posting a fixed solution (for the bug and for your test) in the
    next message, and I'd appreciate if you can re-run it

    -- EK
     
    Eugene Kalenkovich, Sep 4, 2007
    #16
  17. Fixes for previously posted solution:
    - empty node guard in slice
    - normalize returning self for Eric's test

    >------------------------------------------------------------------------------


    class NilClass
    def length; 0; end
    end

    class String
    def shift
    return nil if empty?
    res=self[0]
    self[0]=""
    res
    end
    end

    class Rope
    attr_reader :length, :left, :right

    def initialize(left=nil,right=nil)
    @left=left if left
    @right=right if right
    @length=left.length+right.length
    end

    def append(what)
    len=what.length
    if (len>0)
    @left=self.dup if @right.length>0
    @right=what
    @length+=len
    end
    self
    end

    alias << append

    def prepend(what)
    len=what.length
    if (len>0)
    @right=self.dup if @left.length>0
    @left=what
    @length+=len
    end
    self
    end

    def to_s
    @left.to_s + @right.to_s
    end

    def [](i)
    return i.match(self.to_s)[0] if i.kind_of? Regexp
    if i.kind_of? Range
    pos,last=i.first,i.last
    pos = @length+pos if pos<0
    last = @length+last if last<0
    return nil if pos<0 || last<0
    return slice(pos,last-pos+1)
    end
    i = @length+i if i<0
    return nil if i<0 || i>@length-1
    llen = @left.length
    i<llen ? @left : @right[i-llen]
    end

    def []=(i,val)
    #fixnum only
    i = @length+i if i<0
    ""=0 if i<0 || i> @length-1
    @length+=val.length-1
    llen = @left.length
    i<llen ? @left=val : @right[i-llen]=val
    end

    def slice(pos,len)
    return pos.match(self.to_s)[len] if pos.kind_of? Regexp
    pos = @length+pos if pos<0
    return nil if pos<0 || len<0 || pos>@length-1
    llen = @left.length
    return @left.slice(pos,len) if pos+len<=llen || ! @right
    return @right.slice(pos-llen, len) if pos>=llen
    Rope.new(@left.slice(pos,llen-pos),@right.slice(0,len+pos-llen))
    end

    def shift
    return nil if @length==0
    @length-=1
    res = @left.length>0 ? @left.shift : @right.shift
    @left=nil if @left.length==0
    @right=nil if @right.length==0
    res
    end

    def normalize
    r=Rebalancer.new(@length)
    self.traverse { |str| r.append(str) }
    @left, @right=r.get_ropes
    self
    end

    def traverse(&blck)
    @left.kind_of?(String) ? yield( @left) : @left.traverse(&blck) if @left
    @right.kind_of?(String) ? yield( @right) : @right.traverse(&blck) if
    @right
    end

    end

    class Rebalancer
    def initialize len
    @limits=[1,2]
    @slots=[]
    n=2
    @limits<< n = @limits[-2] + @limits[-1] while n<len
    end

    def append str
    @slots[0] = @slots[0] ? Rope.new( @slots[0],str) : str
    i=0
    while @slots.length>@limits
    @slots[i+1] = @slots[i+1] ? Rope.new( @slots[i+1],@slots) :
    @slots
    @slots = nil
    i+=1
    end
    end

    def get_ropes
    @slots.compact!
    (@slots.length-1).times { |i|
    @slots[i+1]=@slots[i+1] ? Rope.new(@slots[i+1],@slots) : @slots
    @slots=nil
    i+=1
    }
    [@slots[-1].left,@slots[-1].right]
    end
    end
     
    Eugene Kalenkovich, Sep 4, 2007
    #17
  18. > CPU(user+sys,sec) mem(peak,MB)
    > ------------------- ------------
    > build sort total build sort class
    > ----- ---- ----- ----- ---- -----
    > 0.10 1.70 1.80 287 1327 String
    > 0.01 0.27 0.28 22 153 Porth::Rope
    > 0.02 0.83 0.85 22 34 Choudhury::Rope *
    > 0.02 0.06 0.08 22 29 Mahurin::StringRope +
    > 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    > 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    > 0.07 0.10 0.17 151 151 Munkby::ArrayRope
    > 0.02 0.73 0.75 22 655 Kalenkovich::Rope *


    Thanks for running the tests! I do think it is a shame, however,
    that the table does not include the notion of safety that I mentioned
    in my submission. If any of these classes should every go into a
    gem as ara mentioned, the user of that gem at least ought to be
    able to choose the safe version.

    Here is a very simple scenario where such a problem is introduced.
    One could probably do worse changes to the source strings, but this
    was the first example I came up with.

    ss = %w[test append]
    r1, r2 = ss.map {|x| Mahurin::StringRope.new(x) }
    r1 <<= r2
    ss.first << "ing"
    r1.length # => 10
    r1.to_s.length # => 13

    I have only tested Mahurin::StringRope, but would like to know for
    which other classes I need to be extra careful when adding strings
    to the rope. I did find, however, that by removing my "safety dups",
    the combined running time (on my machine) is about the same for
    my solution as for Mahurin::StringRope.

    !g
     
    Gustav Munkby, Sep 4, 2007
    #18
  19. Ruby Quiz

    Eric Mahurin Guest

    On 9/4/07, Gustav Munkby <> wrote:
    > > CPU(user+sys,sec) mem(peak,MB)
    > > ------------------- ------------
    > > build sort total build sort class
    > > ----- ---- ----- ----- ---- -----
    > > 0.10 1.70 1.80 287 1327 String
    > > 0.01 0.27 0.28 22 153 Porth::Rope
    > > 0.02 0.83 0.85 22 34 Choudhury::Rope *
    > > 0.02 0.06 0.08 22 29 Mahurin::StringRope +
    > > 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    > > 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    > > 0.07 0.10 0.17 151 151 Munkby::ArrayRope
    > > 0.02 0.73 0.75 22 655 Kalenkovich::Rope *

    >
    > Thanks for running the tests! I do think it is a shame, however,
    > that the table does not include the notion of safety that I mentioned
    > in my submission. If any of these classes should every go into a
    > gem as ara mentioned, the user of that gem at least ought to be
    > able to choose the safe version.
    >
    > Here is a very simple scenario where such a problem is introduced.
    > One could probably do worse changes to the source strings, but this
    > was the first example I came up with.
    >
    > ss = %w[test append]
    > r1, r2 = ss.map {|x| Mahurin::StringRope.new(x) }
    > r1 <<= r2
    > ss.first << "ing"
    > r1.length # => 10
    > r1.to_s.length # => 13
    >
    > I have only tested Mahurin::StringRope, but would like to know for
    > which other classes I need to be extra careful when adding strings
    > to the rope. I did find, however, that by removing my "safety dups",
    > the combined running time (on my machine) is about the same for
    > my solution as for Mahurin::StringRope.


    My classes that do the work are are immutable (there is a wrapper
    class that makes a mutable rope). I assumed that original data you
    give (strings) won't change. The caller should know whether the input
    data will change or not and dup if necessary.

    Some of the methods in your ArrayRope do modify the underlying
    strings. Because of that, you really need to dup the input. But, you
    could easily fix those few methods to dup when you want to make a
    change. I made a version of your code that doesn't do the dups up
    front and benchmarked it.

    I assume most of the other mutable rope solutions have similar
    problems and need to implement a proper COW (copy-on-write) solution.

    At first I thought your solution was linear to do a slice, but then I
    noticed that you do a binary search. I applaud your solution. I
    think many C++ STL deque implementations use this same scheme (two
    level array). Maybe that is why a rope isn't officially in STL -
    because deque is good enough.

    Here are the new results along with your non-dup solution and
    Kalenkovich's fixes:

    CPU(user+sys,sec) mem(peak,MB)
    ------------------- ------------
    build sort total build sort class
    ----- ---- ----- ----- ---- -----
    0.10 1.70 1.80 287 1327 String
    0.01 0.27 0.28 22 153 Porth::Rope
    0.02 0.83 0.85 22 34 Choudhury::Rope *
    0.02 0.06 0.08 22 29 Mahurin::StringRope +
    0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    0.07 0.10 0.17 151 151 Munkby::ArrayRope
    0.00 0.09 0.09 22 22 Munkby::ArrayRope (no dup)
    0.01 0.12 0.13 22 22 Kalenkovich::Rope (fixed)

    CPU : minimum from 40 iterations
    mem : peak over the 40 iterations

    * : self-checking failed
    + : immutable benchmark needed


    As Eugene Kalenkovich mentioned my benchmark test shouldn't have
    excepted self to be returned from normalize for mutable ropes. I
    fixed this in my test.
     
    Eric Mahurin, Sep 4, 2007
    #19
  20. "Eric Mahurin" <> wrote in message
    news:...

    > 0.02 0.06 0.08 22 29 Mahurin::StringRope +
    > 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope +
    > 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope
    > 0.07 0.10 0.17 151 151 Munkby::ArrayRope
    > 0.00 0.09 0.09 22 22 Munkby::ArrayRope (no dup)
    > 0.01 0.12 0.13 22 22 Kalenkovich::Rope (fixed)
    >


    Eric, may I ask you to test one more thing: your #slice does not have any
    input checks. To make a fair comparison, could you please comment first 3
    lines of my #slice, making it:

    def slice(pos,len)
    #1 return pos.match(self.to_s)[len] if pos.kind_of? Regexp
    #2 pos = @length+pos if pos<0
    #3 return nil if pos<0 || len<0 || pos>@length-1
    llen = @left.length
    return @left.slice(pos,len) if pos+len<=llen || ! @right
    return @right.slice(pos-llen, len) if pos>=llen
    Rope.new(@left.slice(pos,llen-pos),@right.slice(0,len+pos-llen))
    end

    This code still satisfies your test, and I believe it will beat performance
    of yours (BTW, lines 2,3 show problems in your code)

    Thank you,
    -- EK
     
    Eugene Kalenkovich, Sep 4, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Manish Hatwalne

    Understanding error - Java returned: 137

    Manish Hatwalne, Sep 3, 2004, in forum: Java
    Replies:
    1
    Views:
    7,323
    Thomas Fritsch
    Sep 3, 2004
  2. Rajesh.Rapaka

    8+8 = 137 ??

    Rajesh.Rapaka, Aug 10, 2005, in forum: Java
    Replies:
    14
    Views:
    956
    Chris Uppal
    Aug 15, 2005
  3. =?ISO-8859-1?Q?S=F6ren?=

    sgi rope experiences?

    =?ISO-8859-1?Q?S=F6ren?=, Jul 29, 2003, in forum: C++
    Replies:
    0
    Views:
    591
    =?ISO-8859-1?Q?S=F6ren?=
    Jul 29, 2003
  4. Ruby Quiz

    [SUMMARY] Twisting a Rope (#137)

    Ruby Quiz, Sep 6, 2007, in forum: Ruby
    Replies:
    5
    Views:
    379
    Eugene Kalenkovich
    Sep 7, 2007
  5. Braulio Lima

    Getting machine name by port 137

    Braulio Lima, Jan 18, 2011, in forum: Ruby
    Replies:
    0
    Views:
    89
    Braulio Lima
    Jan 18, 2011
Loading...

Share This Page