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 S.", 1], ["James K.", 2], ["Rob B.",
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 K.'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 Q. this week in celebration of the Christmas
holiday. I
wish you all a Merry Christmas and I’ll talk to you again next week.