Mentioned on Ruby Quiz. It was an IFCP contest, before that. What about using a linked list to solve this? Appending to the end is O(1), but inserting a string into the middle is O(n), and the problem states that this should be achievable in better than linear time. People using C++ had an easy out: http://www.sgi.com/tech/stl/Rope.html. Also, Haskell
Data.Sequence.Mapping a Rope to a File. Not the first time that this term was used today, but build the tree lazily and read the file lazily.
LazyNodes contain closures to maintain the reference to where the string came from.
The project on rubyforge was just created this morning: http://rubyforge.org/projects/rope. There is a lot of work that needs to be done on Rope, most of which is optimization. There is no regex support.
"Rope is a RubyGem that implements the rope data structure. Rope is an alternative to String, optimized for time & memory under certain operations. Essentially in a Rope the data is broken up into blocks, and those blocks are stored in a binary tree."
Ropes are more useful than String when you are performing string concatenation and slicing, rather than accessing or in-place replacement.
Someone brought up the piece table data structure.
How does this compare to skip lists? They act as a binary tree. They can probably have the same lazy evaluation. He couldn't find any reason ropes were better than skip lists, on the spot.
Another talk where I wish he went more in depth on guts of it.
No comments:
Post a Comment