James Gray
12/20/2007 1:37:00 PM
This quiz was definitely more about the process than what we produced. For the
record though, I do feel what we produced was quite successful. We have built a
full AVL Tree implementation in under a week. It may still have a bug or two we
haven't eliminated, but it's certainly usable. Let me prove that to you.
Here is the start of an ordered Hash implementation I said would be possible
with a working AVL tree. Unlike Ruby 1.9's built-in Hash ordering, this class
orders pairs by their key instead of their insertion order:
#!/usr/bin/env ruby -wKU
require "avl_tree"
class KeyOrderedHash
Pair = Struct.new(:key, :value) do
def <=>(other)
key <=> other.key
end
end
include Enumerable
def initialize
@pairs = AVLTree.new
end
def [](key)
@pairs[Pair.new(key)].value
end
def []=(key, value)
@pairs << Pair.new(key, value)
end
def each
@pairs.each { |pair| yield pair.to_a }
end
end
if __FILE__ == $PROGRAM_NAME
require "pp"
names = KeyOrderedHash.new
%w[ Rob\ Biedenharn
Adam\ Shelly
James\ Koppel ].each_with_index do |name, i|
names[name] = i
end
pp names.to_a
# >> [["Adam Shelly", 1], ["James Koppel", 2], ["Rob Biedenharn", 0]]
end
Note how the pairs here come out in key order, instead of the insertion order
shown by their values.
The process was also pretty successful. Some felt email was a poor medium to
conduct this kind of experiment and they were probably right. Rob Biedenharn
came to our rescue though with two simple tools for embedding and extracting the
code from an email. Together these two tools were under 40 lines of code and
they helped a lot. Nice problem solving, Rob.
We did see quite a bit of forking early on, but in the end a single branch of
the code seemed to dominate. Solvers were good about incorporating the changes
of others though, so I didn't really feel like this aspect affected the results
much.
As of James Koppel's first response, the code has gone through 15 rounds of
revision, not counting forks. In that time, we generated right around 500 lines
of code including the tests. I was pretty impressed by all of that.
Obviously, the largest aspect of this quiz was the game of Test Driven
Development. That too was interesting to watch unfold. Tests were edited,
commented out, and reinstated all at various times during the exercise. This
happens all the time in normal development of course, but it's different when
you are doing these things to someone else's tests.
It's my opinion that the testing got off track a bit early on when we tried to
do height testing before we really had a height to test. A few early height
tests eventually caused this method to crop up inside AVLTree:
# ...
def height
(Math.log(@contents.size + 1) / Math.log(2)).round
end
# ...
While that does reflect accurate results for what we were trying to accomplish,
it really doesn't have anything to do with our tree. It just proves that we
figured out the math. This is one place where I feel the concept of
only-do-what's-needed-to-pass-the-tests breaks down. This code just has to be
rewritten at some point, so there's not much benefit to bypassing a test with
it, in my opinion.
Another area where we had trouble with the tests was in trying to measure the
speed of something. None of us could come up with a great way to test for
whether and insert operation was O(n) or O(log n) or something else entirely.
One poster suggested that test driving algorithms wasn't very effective and,
while I'm not sure I fully agree with that, this is definitely one of the
problem cases.
All in all though, the process was a big success and we produced great results.
I encourage everyone to read through the quiz thread and see how our work
evolved. Thanks for indulging me in my desires to try something a little
different.
There will be no Ruby Quiz this week in celebration of the Christmas holiday. I
wish you all a Merry Christmas and I'll talk to you again next week.