3. Enumerable#lazy

2013/02/22　シナジーマーケティング(株)　寺岡 佑起

3.1. Enumerable#lazyとは

Enumerable#lazyを一言で表すと、遅延評価を行うEnumeratorを返すメソッドです。
遅延評価とは関数型言語でよく利用される「必要とされるまで実行しない」という考え方です。
Enumerable#lazyを用いると、今まで利用できなかった箇所にselectやmapなどのメソッドを適用することができるようになります。

3.2. lazyが生まれた背景

Enumerable#lazyはどのような場面で必要となってくるのか考えてみたいと思います。

1～20までの数字から、奇数の数字を5個取り出したい場合、以下のようなコードで求めることができます

> (1..20).select{|num| num.odd?}.take(5)
=> [1, 3, 5, 7, 9]

では、対象の数字を1～100000000とした場合はどうでしょう。

> (1..100000000).select{|num| num.odd?}.take(5) 
=> [1, 3, 5, 7, 9] # なかなか結果が帰ってこない

実行結果は同じですが、膨大な実行時間を必要としました。
どこで時間がかかっているのか、メソッド呼び出し単位に分解して考えてみます。

list = (1..100000000)                   # A. 1～100000000のRangeオブジェクトを生成
list_tmp = list.select{|num| num.odd?}  # B. Aから奇数の要素だけの配列を生成
list_tmp.take(5)                        # C. Bから先頭の5個を取得

B.の箇所で1億回ループして5千万要素の配列を生成してしまうことがわかります。
しかし、C.ではこのうちたった5個しか利用されません。
5個の奇数を求めるのに本来必要な計算は9回なので、(1億-9)回の計算と、(5千万-5)の配列要素が無駄になってしまいます。

lazyを利用すると、このような無駄な計算を省くことができます。

> (1..100000000).lazy.select{|num| num.odd?}.take(5).force
=> [1, 3, 5, 7, 9] # すぐに結果が返ってくる

元のコードにlazyとforceをつけただけで、すぐに結果が返るようになりました。
このlazyがどのように動作しているのか、もう少し詳しく調べてみます。

3.3. 怠惰なEnumerator

先ほどのlazyの例をメソッド呼び出し単位に分解して、各呼び出しのメソッドの戻り値を調べてみます。

> (1..100000000).lazy 
=> #<Enumerator::Lazy: 1..100000000>

Enumerator::Lazyクラスのインスタンスだという事がわかりました。
selectを呼び出した後はどうなっているのでしょうか。

> (1..100000000).lazy.select{|num| num.odd?}
=> #<Enumerator::Lazy: #<Enumerator::Lazy: 1..100000000>:select>

先ほどのEnumerator::Lazyのインスタンスを保持したEnumerator::Lazyクラスのインスタンスが新たに生成されているようです。
selectに与えたブロックが実行されるタイミングを調べるため、ブロック内にpメソッドを追加してみます。

※ 余談ですが、ruby1.9からpメソッドの戻り値がnilからpメソッドに与えた引数に変更され、
select {|num| num.odd?} と select {|num| p num.odd?}は同じ結果を返すようになりました。

> (1..100000000).lazy.select{|num| p num.odd?}
=> #<Enumerator::Lazy: #<Enumerator::Lazy: 1..100000000>:select>

まだ何も出力されないことから、selectに与えたブロックが実行されていないことがわかります。
次は、Enumerator::Lazyクラスの親クラスと継承階層を確認してみます。

※ Class#superclassは親クラスを返し、Class#ancestorsはモジュールを含めた継承階層を返します。

> Enumerator::Lazy.superclass
=> Enumerator
> Enumerator::Lazy.ancestors
=> [Enumerator::Lazy, Enumerator, Enumerable, Object, Kernel, BasicObject]

Enumerator::LazyはEnumeratorを継承しており、EnumeratorはEnumerableモジュールをincludeしていることがわかりました。
ということは、eachメソッドが使えそうです。
一億回ループされると困るので、Rangeの数を減らして試してみます。

> (1..5).lazy.select{|num| p num.odd?}.each{|num| p num}
true
1
false
true
3
false
true
5
 => nil

selectのブロックが逐次実行され、trueになった際にeachのブロックが実行されている様子がわかります。
eachのような実際の値を必要とするメソッドが呼び出されるまで、ブロックの実行が遅延されています。
これが「怠惰な(lazy)」Enumeratorとしての機能です。

lazyを使わない例と見比べてみましょう。

> (1..5).select{|num| p num.odd?}.each{|num| p num}
true
false
true
false
true
1
3
5
 => [1, 3, 5]

全部の要素にselectが実行され、その後eachが実行されました。
lazyの例と違って、selectの時点で真面目に実行されている様子がわかります。
また、eachの戻り値がnilと配列の違いがあるようです。

次は、前項で利用したforceメソッドを使ってみます。

> (1..5).lazy.select{|num| p num.odd?}.force
true
false
true
false
true
 => [1, 3, 5]

forceはto_aのaliasで、selectを適用した結果の配列を得ることができます。
forceは「強制する」という意味で、怠惰なEnumeratorに仕事を強制させるメソッドです。

Enumerator::Lazyはselectだけではなく、rejectやmapなどのメソッドでも利用できます。

> (1..10000000000).lazy.reject{|num| num.even? }.take(5).force
=>  [1, 3, 5, 7, 9]
> (1..10000000000).lazy.map{|num| num * 100}.take(5).force
=>  [100, 200, 300, 400, 500]

この場合もきちんと「怠惰に」動作してくれます。
以下のコードでEnumerator::Lazyで再定義されたEnumerableのメソッドを調べることができます。

> Enumerator::Lazy.instance_methods(false) & Enumerable.instance_methods(false)
 => [:map, :collect, :flat_map, :collect_concat, :select, :find_all, :reject, :grep, :zip, :take, :take_while, :drop, :drop_while, :lazy, :chunk, :slice_before]

3.4. 省メモリ

lazyの一番の利点はメモリ効率が良いことにあります。

下の2つのコードの結果は同じですが、実行時のメモリ消費量は大きく違います。

> (1..1000).select{|n| n.even?}.map{|n| n.to_s}.each{|s| p s}      # normal
> (1..1000).lazy.select{|n| n.even?}.map{|n| n.to_s}.each{|s| p s} # lazy

normalのコードでは、selectを呼び出した段階で1～1000の偶数すべてを要素とした配列がメモリ上に確保され、mapを呼び出した段階ではそれを文字列にした配列がメモリ上に確保されます。
メソッドをチェインしていくと、前のメソッドの実行結果(レシーバ) + 今回の実行結果をメモリ上に確保する必要があることになります。
対してlazyのコードでは、「select」「map」の段階でメモリ上確保されるのは、Enumerator::Lazyのインスタンスだけです。
eachの段階でも、メモリ上に確保されるのは各要素1つに対して「select」「map」のブロックを適用した値だけになります。
繰り返し回数をどれだけ大きくしても常に一定のメモリ効率で処理することができるわけです。

このように、lazyを利用するとメモリ効率を格段に良くすることが出来ます。
省メモリになったなら実行速度も早いのでは？と期待してしまいますが、現在のrubyの実装では、大抵の場合lazyの方が遅くなってしまいます。

3.5. 無限リストに適用

無限リストに対してlazyを適用することで利便性を格段に向上させることができます。

Enumeratorを使って試してみましょう。
まずはフィボナッチ数列を求めるEnumeratorを作ります。

> fib = Enumerator.new {|yielder|
>   func = ->(n) { n < 2 ? n : func.(n-2) + func.(n-1)}
>   i = 0
>   loop {yielder << func.(i);i+=1}
> }
> fib.take(11) # 0～10のフィボナッチ数列
=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

ではこのfibに対してmapを使って加工してみましょう。

> fib.map{|n| "#{n} is Fibonacci!"}.take(11)

上のコードを実行しても、いつまでたっても結果が返って来ません。
fibは無限にフィボナッチ数列を返し続けるので、mapの時点で無限ループになってしまうためです。
この例ではtakeとmapの順序を入れ替えれば望み通りの結果が取得できますが、lazyを使うとこの問題をもっとエレガントに解決することができます。

> fib.lazy.map{|n| "#{n} is Fibonacci!"}.take(11).force
=> ["0 is Fibonacci!", "1 is Fibonacci!", ...]

意図した結果を得ることができました。
無限リストに対してlazyを使うとEnumerableのメソッドを使って自由自在に加工できるようになります。

次は、lazyを使ったもう少し実用的な例をご紹介したいと思います。

3.6. IOに適用

RubyのIOクラスにはEnumerableがincludeされているためlazyの恩恵に預かることができます。
IOのeachはeach_lineのaliasとなっているため、一行ずつイテレートされます。

ファイルの先頭から5行を表示するワンライナーを書いてみます。

open('/path/to/file').lazy.take(5).each{|s| puts s}

折角なので行番号をつけることにします。

open('/path/to/file').lazy.with_index.map{|s,i| "#{i+1}: #{s}"}.take(5).each{|s| puts s}

上のコードのlazyのをeachに置き換えることで遅延評価を行わないようになります。
この場合も同じ結果を得ることができますが、メモリ効率に大きな問題を抱えることになります。
巨大なファイルを対象とした場合、with_indexやmapの対象がファイルの全行になってしまうためメモリを大量に消費してしまいます。

lazyを使うことでファイルの行単位での逐次処理をスッキリと書くことが出来ました。
IOとlazyは非常に相性が良いのため、色々な応用ができそうです。

3.7. まとめ

Enumerable#lazyを使うと巨大なデータに対してのselectやmap処理を効率的に動作させることができます。
今までパフォーマンス上の制約からループ中で行なっていた処理を、ブロックとして括り出すことが出来るため可読性の向上も期待出来ます。
繰り返しが少ない場合はパフォーマンスのデメリットがありますが、巨大なRangeやIOなどを扱う場合には積極的に活用していきたいメソッドです。