Rope: An Alternative to Ruby's String
Presented November 2, 2007
This talk was given at RubyConf 2007 in Charlotte, NC.
I had a number of somewhat disparate goals for this talk:
- Provide a basic understanding of the Rope data structure to those who'd not seen it before.
- Show how some of the nice elements of Ruby made some implementation details trivial.
- Emphasize the benefit to the Ruby community of having a large number of “drop-in” data structures available.
- Remind Rubyists that data structures (and the computational complexity associated with them) often trump the inherent speed of any given language.
- Encourage the Ruby community to participate in the annual International Conference on Functional Programming (ICFP) Programming Contest.
You can view this presentation as either a QuickTime movie or as a Flash movie:
- QuickTime version (7.9 MB, low resolution, full animations)
- Flash version (3.3 MB, high resolution, reduced animations)
There are a number of links that go with the talk:
The Rope project on RubyForge
Ropes: an Alternative to Strings
by Hans-Juergen Boehm, Russ Atkinson, and Michael Plass
The original paper on ropes.
Documentation for SGI's C++ rope library
ICFP Programming Contest
I particularly recommend the report (PDF file) linked from that page that describes the process of creating the contest. It's impressive!
The Ruby Quiz