一昔前は関数型プログラミングには無頓着だったが、Scala を使うようになってその楽しさを覚えた。
Ruby 自体は関数型言語ではないが、関数型言語のテクニックは有効な武器になる。副作用のないプログラミングを意識しつつ、遅延評価、メモ化、無限リストなど活用できる場面ではドンドン使っていければと思う。
ActiveRecord の named_scope を見た時には、なるほど、遅延評価とはこう使うのか、と感心させられたし、また、最近ちょっと見た Rails3 の ActiveRecord の Arel などは、関数型言語の発想が相当盛り込まれているように感じた。
今回は、以前、Scala での無限リスト(遅延 Stream)について書いた内容を Ruby でやってみることにした。
Ruby の標準ライブラリには、Stream の実装はない。一から書いてはみていたのだが、なかなかうまく書けなかった。その途中で James Gray 氏の実装を見つけてしまった。やりたいことが実装されているので、これを使わせて頂くことにする。
ここでは、上記の lazy_stream.rb を使用する。
ちなみに、lazy_stream.rb は gem などでの公開はされておらず、完全なソースの正式版がどこにあるのかよくわからなかった。上記のサイトの記載を使うことにする。
(上記のサイトの lazy_stream.rb の全文を lazy_stream.rb に置いておく。)
やることは、前回と同様、「指定した範囲で、最初の 2 つの素数を取り出す」ケース。
まずは、素数の判定を行う関数を用意する。
Scala では、関数をそのまま引数に渡していたが、Ruby 版では、Proc オブジェクトを使うことにする。
>> is_prime = lambda do |n|
?> if n <= 1
>> false
>> else
?> (2...n).all? { |e| n % e != 0 }
>> end
>> end
#<Proc:0xb7068a44@(irb):14>確認してみる。
>> is_prime[1]
false
>> is_prime[2]
true
>> is_prime[3]
true
>> is_prime[4]
falseOK だ。Proc#[] を使って、Proc オブジェクトを実行しているが、これは、Proc#call と同義になる。
次に、Stream 版のレンジオブジェクトを返すメソッドを用意する。ここから lazy_stream.rb を使う。
>> require 'lazy_stream'
true
>> def s_range(from, to)
>> return if from > to
>>
?> lazy_stream(from) { s_range(from + 1, to) }
>> endlazy_stream メソッドは、Kernel レベルで再定義したメソッドで以下のような内容になる。
module Kernel
def lazy_stream(*args, &block)
LazyStream::Node.new(*args, &block)
end
endStream を実現しているのは、LazyStream::Node クラスで、@head に最初の要素の値をもち、@tail に次の要素を計算するための手続き(Proc オブジェクト)を持つ構造となっている。
先のレンジオブジェクトを返す s_range メソッドの中では、lazy_stream メソッドを、1 つ目の引数として開始位置の数値を与え、2 つ目の引数に再帰呼び出しを行うブロックを与えて呼び出している。
そのブロックに渡した s_range の引数の中で、次の要素を取得するための方法(from + 1)を教えてあげている。
次の要素が必要になった時には、このブロックが評価され、この教えてあげた方法で次の要素が取得され、またその次の要素を取得するための手続きは必要とされるまで保管されることになる。これが順に繰り返される。
この次の要素を取得するための手続きが必要な時になるまで評価されない(遅延評価)、というところが Stream のミソになる。
module LazyStream
class Node
include Enumerable
def initialize(head, &promise)
@head, @tail = head, promise
end
end
end最初の要素は、@head にそのまま代入され、次の要素を取得するために与えたブロックは、& で Proc オブジェクトに変換され、@tail に保管される。
確認してみる。
>> s_range(1000, 10000)
#<LazyStream::Node:0x94c00c8 @head=1000, @tail=#<Proc:0x94c00f0@(irb):16>>インスタンス変数 @head にスタート値の 1000 が入っており、@tail には、Proc オブジェクトが入っている。
必要な時に遅延評価される @tail の Proc オブジェクトはこの時点では実行されていない。
では、値を取り出しみる。指定した範囲の最初の 2 つの数値を取得する。
>> s_range(1000, 10000).take(2)
[
[0] 1000,
[1] 1001
]ちなみに、LazyStream::Node は、Enumerable モジュールをインクルードしているので、Enumerable#take が使用できる。
LazyStream::Node にはナント filter メソッドも既に実装されているので、先ほど作成した素数を判定する Proc オブジェクトを引数に預ける。
>> s_range(1000, 10000).filter(&is_prime)
#<LazyStream::Node:0x94b82c4 @head=1009, @tail=#<Proc:0x94b7c5c@(irb):16>, @filter=#<Proc:0x929fde8@(irb):19 (lambda)>>LazyStream::Node#filter を呼び出したことで、1 つめの要素 @head は filter の条件の最初の要素(1009)まで進んでいる。@tail は次の要素を計算するための Proc オブジェクトになる。
では、実際に「指定した範囲」(1000 から 10000)で、「最初の 2 つの素数」を取り出してみる。
>> s_range(1000, 10000).filter(&is_prime).take(2)
[
[0] 1009,
[1] 1013
]OK だ。
Stream を使う場合と使わない場合でどれだけの速度差がでるのか確かめてみる。
以下のスクリプトを lazy_stream_bench.rb というファイル名で保存して実行する。
# -*- coding: utf-8-unix;
require 'lazy_stream'
def s_range(from, to)
return if from > to
lazy_stream(from) { s_range(from + 1, to) }
end
is_prime = lambda do |n|
if n <= 1
false
else
(2...n).all?{ |e| n % e != 0 }
end
end
require 'benchmark'
Benchmark.bmbm do |x|
x.report("Stream を使わないバージョン") do
(1000..10000).select(&is_prime).take(2)
end
x.report("Stream を使ったバージョン") do
s_range(1000, 10000).filter(&is_prime).take(2)
end
endlazy_stream.rb も同じディレクトリにあるものとする。
$ ruby1.9.2 -I. lazy_stream_bench.rb
Rehearsal -----------------------------------------------------
Stream を使わないバージョン 0.920000 0.000000 0.920000 ( 0.921671)
Stream を使ったバージョン 0.000000 0.000000 0.000000 ( 0.003363)
-------------------------------------------- total: 0.920000sec
user system total real
Stream を使わないバージョン 0.910000 0.000000 0.910000 ( 0.920455)
Stream を使ったバージョン 0.010000 0.000000 0.010000 ( 0.003485)余計な計算処理を行っていないので、今回のような要件であれば、Stream を使った場合が圧倒的に速い。。
遅延 Stream が有効な場面ではドンドン使っていきたい。