The three rules of Ruby Q.:
-
Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message. -
Support Ruby Q. by submitting ideas as often as you can:
- Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Ruby includes a useful Generator library for switching internal
iterators to
external iterators. It is used like this:
require 'generator'
# Generator from an Enumerable object
g = Generator.new(['A', 'B', 'C', 'Z'])
while g.next?
puts g.next
end
I’ve heard complaints in the past that this library is slow. One reason
is that
it was implemented with continuations, which have performance issues in
the
current version of Ruby. “Was” is the keyword there though, because
I’ve just
learned that Generator was recently re-implemented. I learned some good
tricks
reading the new version, so let’s try fixing Generator ourselves. (No
peeking
at the new version!)
This week’s Ruby Q. is to write FasterGenerator, your own
re-implementation of
Generator with an eye towards working faster. (This is a small library.
My
version is 54 lines.) It is possible to go even faster than the new
implementation, with certain trade-offs:
### Construction ###
Rehearsal -----------------------------------------------------------
Current Generator 0.340000 0.480000 0.820000 ( 0.828985)
Old callcc Generator 0.590000 0.840000 1.430000 ( 1.439255)
James's FasterGenerator 0.210000 1.040000 1.250000 ( 1.252359)
-------------------------------------------------- total: 3.500000sec
user system total real
Current Generator 0.750000 0.880000 1.630000 ( 1.630639)
Old callcc Generator 0.190000 1.170000 1.360000 ( 1.375868)
James's FasterGenerator 0.210000 1.230000 1.440000 ( 1.433152)
### next() ###
Rehearsal -----------------------------------------------------------
Current Generator 16.280000 0.100000 16.380000 ( 16.434828)
Old callcc Generator 9.260000 33.490000 42.750000 ( 42.997528)
James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.038645)
------------------------------------------------- total: 59.160000sec
user system total real
Current Generator 15.940000 0.140000 16.080000 ( 16.425068)
Old callcc Generator 6.390000 30.160000 36.550000 ( 36.676838)
James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.036880)
It you want to see the class documentation, you can find it here:
http://www.ruby-doc.org/stdlib/libdoc/generator/rdoc/classes/Generator.html
If you want to make sure your implementation is correct, you can use
these tests
straight out of the current implementation:
require 'test/unit'
class TC_Generator < Test::Unit::TestCase
def test_block1
g = Generator.new { |g|
# no yield's
}
assert_equal(0, g.pos)
assert_raises(EOFError) { g.current }
end
def test_block2
g = Generator.new { |g|
for i in 'A'..'C'
g.yield i
end
g.yield 'Z'
}
assert_equal(0, g.pos)
assert_equal('A', g.current)
assert_equal(true, g.next?)
assert_equal(0, g.pos)
assert_equal('A', g.current)
assert_equal(0, g.pos)
assert_equal('A', g.next)
assert_equal(1, g.pos)
assert_equal(true, g.next?)
assert_equal(1, g.pos)
assert_equal('B', g.current)
assert_equal(1, g.pos)
assert_equal('B', g.next)
assert_equal(g, g.rewind)
assert_equal(0, g.pos)
assert_equal('A', g.current)
assert_equal(true, g.next?)
assert_equal(0, g.pos)
assert_equal('A', g.current)
assert_equal(0, g.pos)
assert_equal('A', g.next)
assert_equal(1, g.pos)
assert_equal(true, g.next?)
assert_equal(1, g.pos)
assert_equal('B', g.current)
assert_equal(1, g.pos)
assert_equal('B', g.next)
assert_equal(2, g.pos)
assert_equal(true, g.next?)
assert_equal(2, g.pos)
assert_equal('C', g.current)
assert_equal(2, g.pos)
assert_equal('C', g.next)
assert_equal(3, g.pos)
assert_equal(true, g.next?)
assert_equal(3, g.pos)
assert_equal('Z', g.current)
assert_equal(3, g.pos)
assert_equal('Z', g.next)
assert_equal(4, g.pos)
assert_equal(false, g.next?)
assert_raises(EOFError) { g.next }
end
def test_each
a = [5, 6, 7, 8, 9]
g = Generator.new(a)
i = 0
g.each { |x|
assert_equal(a[i], x)
i += 1
break if i == 3
}
assert_equal(3, i)
i = 0
g.each { |x|
assert_equal(a[i], x)
i += 1
}
assert_equal(5, i)
end
end
The Generator library also includes a SyncEnumerator class, but it is
written to
use Generator and will work fine with a new version, as long as it is
API-compatible.
This is on a 2Ghz P4 / 1gig RAM.