Lazy Plus Enumerable Begats Denumerable
October 4, 2011
Lazy + Enumerable = Denumerable
All Rubyists know and love Enumerable. It’s the really the showcase of Ruby’s mixin system. Some Rubyists also know and appreciate lazy.rb MenTaLguY’s excellent lazy evaluation library. But did you know there is library that essentially cross-breeds the ideas of both? It’s called Denumerable and is included in Ruby Facets (require 'facets/denumerable').
According to Webster’s The term denumerable is just a synonym for enumerable. In Ruby parlance, it takes a more useful distinction of “deferred enumerable”. In other words Denumerable defers actual calculations of a chain of enumerable method calls until the results are actually needed. That’s where the “laziness” comes in. By deferring calculation Ruby is able to optimize the algorithm, in many cases greatly improving performance. It’s even possible to enumerate infinite ranges if the end result itself is finite.
To make it even more convenient there is Enumerable#defer (require 'facets/enumerable/defer') which delegates an Enumerable object through a Denumerator, just like Ruby’s core Enumerator class.
So, enough talk, right? How about an example.
a = (1..1_000_000_000).defer.select{ |i| i % 2 == 0 }.
map{ |i| i + 100 }.
take(10).to_a
=> [102, 104, 106, 108, 110, 112, 114, 116, 118, 120]
The performance gains of Denumerable cannot be understated. The above example takes 1/10000th of a second to run on my system. I wanted to provide the time it takes to run without defer, but after an hour of waiting and listening to it eat my hard drive for breakfast, I gave up.