Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2009-11-11

[] enumerabler.rb: Enumerable の遅延評価版メソッドライブラリ

たとえば整数配列から、条件に合う要素のうち、最初に現れる 10 個だけ拾いたいとき、どうしますか?

ary.select {|x| x.even? }.take(10)

↑これは非常に明瞭なプログラムです。しかし select は、最初の 10 個だけでなく全要素をチェックしてしまうため、ary が大きいと無駄にループします。また、select の戻り値となる中間配列も無駄です。

ret = []
ary.each do |x|
  ret << x if x.even?
  break if ret.size == 10
end

↑これなら 10 個見つかった時点で終了してくれるし、無駄な配列確保もありません。しかし非常に強引で原始的で煩雑なプログラムであり、Ruby 1.9 の時代を迎えた新人類である我々には、可読性やメンテナンス性に問題があると言わざるを得ない。一言で言うと品がないのです。


Ruby 1.9 には Enumerator と to_enum があるから何とかなる?」

発想はいいですが、残念なお知らせです。

(1..50).to_enum(:select) {|x| x.even? }.take(10)
  #=> [1,2,3,4,5,6,7,8,9,10] # 全然 select できていない

なんでこれでうまくいかないかは、説明が難しいので自分で考えてください。to_enum は難しいんですよね。

結論だけ言うと、Enumerable#select をどんな風に to_enum しても、目標の挙動は達成できません。できないはずです。たぶん。

どうすればいいかというと、以下のように Enumerable#select を使わず Enumerable.new で書けばいい (書くしかない) です。

module Enumerable
  def selector(&blk)
    Enumerator.new do |e|
      each do |x|
        e << x if blk[x]
      end
    end
  end
end

しかし、いちいちこんなのを定義するのは面倒ですよね。


enumerabler.rb

そこで、上記のような定義を集めたライブラリ enumerabler.rb を作りました。

require "enumerabler"

ary.selector {|x| x.even? }.take(10)

select の代わりに selector と書きます。select は配列を返しますが、selector はそれに相当する Enumerator を返します。Enumerator なので、評価が遅延されています。上のプログラムでは、10 個見つかった時点で評価が止まります。

enumerabler.rb は、Enumrable に grepper 、finder_all (all_finder 、selector) 、rejecter 、collector (mapper) 、flat_mapper (concat_collector) 、zipper 、taker 、taker_while 、dropper 、dropper_while を追加します *1 。どれも、-er のないメソッドが返す配列に相当する Enumerator を返します。

個人的には「-er を付けると Enumerator を返す」という convension が気に入っています。(自分で言うな)


「Fiber を使うから遅いんじゃないの?」

いいえ、enumerabler.rb を使うだけでは、Fiber の生成や呼び出しは一切起こりません。なぜだか気になる人は Ruby のソースを読んでください。

ただし、Proc の呼び出しが多数発生するので、遅いことは確かです。でも、中間配列の分の消費メモリ量は減ります。


活用例

p ary.selector {|x| x.even? }.taker(100).take_while {|x| x >= 0 }

↑最初に現れる 100 個の偶数 (ただし負の値があったら 100 個行かなくても打ち切る) という抽出操作を、無駄な列挙や中間配列生成なしに行う。

require "enumerabler"

def sieve(e, &blk)
  yield n = e.first
  sieve(e.rejecter {|x| x % n == 0 }, &blk)
end

sieve(2..(1.0/0.0)) {|x| p x } #=> 2, 3, 5, 7, 11, 13, 17, 19, 23, ...

↑エラトステネスの篩。rejecter を使っています。

require "enumerabler"

def fibonacci
  Enumerator.new do |e|
    e << 1
    e << 1
    fibonacci.zip(fibonacci.dropper(1)) {|x, y| e << x + y }
  end
end

fibonacci.each {|x| p x } #=> 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

フィボナッチ数列。dropper を使うことで無限列を drop できます。ただし、call-by-name なのと、zip は中で Fiber を呼ぶので、スピードはとても遅いです。


インストール方法とソース

$ gem install enumerabler

http://github.com/mame/enumerabler

*1:余談ですが、-er と -or の使い分けがわからない。

knuknu 2009/11/12 01:41 列挙ストリームの編集はずいぶん前からほしいと思っていて、作ったのがこれ。
http://gist.github.com/232084

個別にメソッドを用意しなくても、yielderを渡して好きにやってもらえばいいんじゃないかなあ。

ku-ma-meku-ma-me 2009/11/12 02:09 うーん、それって遠まわしに Enumerable の存在意義を否定してません?
「Enumerable#select とか個別にメソッドを用意しなくても、each で好きにやってもらえばいいんじゃないかなあ」という風に。

あと、「Enumerator を勝手に使って」というのはどのくらい通用するんでしょうね。Rubyist なら大抵使える、というほど簡単ではないのかもと思ったり。

knuknu 2009/11/12 13:02 私の経験では、圧倒的に多いユースケースはselectとmapとselect&map(これは別の問題ですが)です。
そして渡すか渡さないかを選べて加工もできるインターフェースを考えると、上記のfilterがシンプルで最適かつ最小ではないかと思いました。

そのほかはまれだし、個別にメソッドを用意するほどかなと思います。
前半ではto_enumでできない例を挙げていますがtaker, dropper, grepper, zipperはto_enumで実現できるし、taker_whileやdropper_whileは後続するメソッドのブロックでbreak if/next ifで制御すれば済むことが多いです。

to_enumがブロックをサポートしていないことが問題かも。

knuknu 2009/11/12 14:52 to_enumがブロックをサポートするという話はナンセンスでした。
ブロックを取り配列を返すようなメソッドは個別に手当が必要ですね。

ところで-er/-orの別ですが、大まかな基準であるラテン語由来かどうかというのも見ただけでは分からないし、rejectなどは慣用によって-orも-erも使われるようです。

ということはつまり、自動生成もしづらく使い時も迷いやすい(特に動詞一語でない場合)ので、あまり良い名前付け方法ではないと言えるかもしれません。

まあ自動生成はあきらめるとして、今後Enumerableにメソッドを増やす際は安易に配列を返さず、Enumeratorを返す(手段を用意する)ことも考えようということは訴えたいですね。

ku-ma-meku-ma-me 2009/11/12 20:27 filter はプリミティブとして便利そうですが、あくまでプリミティブだと思います。
例えるなら inject 。map も select も inject で実装できますが、それだけで OK とはなりませんよね。
私は select(or) & map の方が意図が伝わりやすくて良いと思います。条件と変換が明確に分かれているのがいい。

> そのほかはまれだし、個別にメソッドを用意するほどかなと思います。
Enumerable にある select と map 以外の機能はまれ、ということでしょうか。
私は今回挙げたものはどれも結構使ってると思います (grep 以外) 。map と select は特に多いですけど。

> taker, dropper, grepper, zipperはto_enumで実現できるし、
あ、確かに zipper は ary1.to_enum(:zip, ary2) でできますね。気づいてませんでした。
でも他はできないと思います。できます?

> 後続するメソッドのブロックでbreak if/next ifで制御すれば済むことが多いです。
後続するメソッドのブロックの本来の意図が不明瞭になるので、犠牲は大きいです。
制御命令は特にわかりにくくなるので、リスト処理においては最後の手段だと思います。


> 自動生成もしづらく使い時も迷いやすい(特に動詞一語でない場合)ので、あまり良い名前付け方法ではないと言えるかもしれません。
確かにその問題はあります。英語のバカ。語感はかなりいいと思うんですけどね。
select は「選べ」という命令または動詞で、いかにも実行しそう。
selector は「選ぶもの」を返すプロパティで、(これから) その動作をするものを返しそう。

> 今後Enumerableにメソッドを増やす際は安易に配列を返さず、Enumeratorを返す(手段を用意する)ことも考えようということは訴えたいですね。
そう思います。訴える所存です。

knuknu 2009/11/12 22:43 ああ、takeとdropはできないですね。
grepはできると思いますよ。ブロックを与えるとイテレータ動作するので。

e = ("1".."50").to_enum(:grep, /3/)
p e #=> #<Enumerator: "1".."50":grep(/3/)>
p e.take(3) #=> ["3", "13", "23"]

takeとdropも今はブロックを無視しますが、同様の動作をするようにすればto_enumでいけます。

Enumeratorを返すという件は、もし一から作り直すのなら自分と同じクラスのインスタンスを返すのがいいのかなと思います。
その場で配列にしたければ newarray = array.map {...} で、動的に列挙したければ newenum = array.to_enum.map {...} という具合に。

ku-ma-meku-ma-me 2009/11/12 23:09 > grepはできると思いますよ。ブロックを与えるとイテレータ動作するので。
あ、そうか。grep の挙動を何か勘違いしてました。

> takeとdropも今はブロックを無視しますが、同様の動作をするようにすればto_enumでいけます。
take_while が take から分けられたのはこのためなんですかねえ。
個人的には分けなくてもよかったと思ってるんですけど。

> Enumeratorを返すという件は、もし一から作り直すのなら自分と同じクラスのインスタンスを返すのがいいのかなと思います。
なるほど。これはよさそうですね。
うまくできれば Hash の map が Hash でなく Array を返す問題もあわせて解決できそうですね。

まつもとまつもと 2009/11/21 08:49 名前が、enum_XXXX とかで妥協できるんなら採用の余地があるような気がします。

ku-ma-meku-ma-me 2009/11/21 12:12 今無理に採用せずとも、将来 LazyArray と共に導入するくらいでいいと思います。
名前に関しては、enum は Enumerable の略称に見えるので、違うものに感じます。そういえばなかださんが -ing というのを IRC でおっしゃっていました。

まつもとまつもと 2009/11/22 23:00 昨日(現地時間)、ささだくんたちとも話したのですが、LazyArrayって作るの面倒な割に、関数型言語ファンを喜ばせる程度のメリットしかないなあ、と感じるようになりました。
実は、そういう遅延が役に立つケースってそんなにないような。
ごくまれに、無限の列を扱いたいとかがあるとしても、むしろ明示的にメソッドを分けた方がよいような気がしてきました。
でも、-erは(私にとって自明ではないので)採用したくありません。
ということでの、「enum_XXX」の提案だったわけですが。

「enum_XXX」が気に入らないにしても、別の名前の提案は歓迎します。

ku-ma-meku-ma-me 2009/11/23 00:53 なんですと。そういうことならどうすべきかな。
2.0 では select がデフォルトで Enumerator を返すとか。あと成瀬さんの Indexable (だっけ?) とか。
「将来 LazyArray が入るから今は pending」みたいな扱いになった提案や案件がいくつかあったと思うので、そういうのを見直しながら考えます。2.0 までにゆっくり。

kwatchkwatch 2010/03/31 09:03 > 個人的には「-er を付けると Enumerator を返す」という convension が気に入っています。

+1
-er と -or の使い分けが気になるけど、いい命名規則だと思います。

> LazyArrayって作るの面倒な割に、関数型言語ファンを喜ばせる程度のメリットしかない

メモリ消費量は減らせると思うので、少なくともWebアプリでのチューニングがしやすくなります。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証