From: Ruby Quiz <james@...>
Date: 2006-02-10T22:53:06+09:00
Subject: [QUIZ] FasterGenerator (#66)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk 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 Quiz 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.