From: John Miller Date: 2007-08-23T11:59:23+09:00 Subject: Re: Rope Data Structures James Gray wrote: > On Aug 22, 2007, at 2:03 PM, John Miller wrote: > >> Most teems who have put up there reviews >> have talked about having to switch programming languages to something >> faster. Most did this before trying to change algorithms. > > We used Ruby and didn't switch, but the code was slow. > >> >> I tried writing a rope library in ruby and got an order of magnitude >> better performance when compared to a String implementation (6.5 to >> 48.5 >> iterations per second -- to successfully solve the problem I >> estimated I >> would need ~2000 iterations per second) > > I debated for some time about making this task, building a rope for > Ruby, a Ruby Quiz. Can I ask how long it took you? Also, just as a > rough metric, how many lines of code did you write? > > James Edward Gray II It took about a week of causal programming to get a String version running with no RNA output. To write writing a Rope class was another three days of sloppy programming. Replacing String with Rope took about 2 hours. I then spent more time then I can recall fixing edge cases in the Rope class. There are still a few loose ends, and the code has become so full of edge case checks that it really isn't as fast as it should be. Looking only at the first 10,000 iterations, the fast majority of instructions were copying huge swaths of the original dna. I decided that a node should be able to represent a 'slice' of another node without copying when these slices start having to span concatenations life gets messy. When I added a pop command that could make the left branch unused things got even more messy. When I wanted a << operator that would add characters directly to the end of 'short' node things became atrocious. And when finally I required the Environment DNA from matchreplace(where my code spent 94.2% of it's time) not create new copies of the Ropes it was holding when it was perpended to the dna the code pretty much buckled under its own weight. At the moment there is a bug in the normalization code that is introducing errors. Without being able to renormalizes the data structure on th rope gets too deep and everything grinds to a halt. Lesson: Keep you data structures simple and elegant. My rope implementation was initially ~120 (source file) lines. Now that it is doing all this stuff it is 366. 44 of that is for a kmp_search algorithm. I would love to see Ropes as a Ruby quiz. John Miller -- Posted via http://www.ruby-forum.com/.