[ruby-dev:38964] Re: Enumerator#peek

けいじゅ＠いしつかです.

In [ruby-dev:38944] the message: "[ruby-dev:38944] Re:
Enumerator#peek", on Jul/30 01:49(JST) Tanaka Akira writes:

>メソッドの仕様として、ソート済みかどうかで結果が変わらなくて
>わかりやすいのは良いですよね。

そうですね. あと, 処理のオーダーもO(n)になります. 

>でも、メモリとのトレードオフで、メモリ消費に耐えられないこと
>もあるので用途によっては困ります。

たしかに. それはいえますね. 

>Ruby では、ソート済みであることをプログラマが知っている状況
>に対する支援はかなり手薄ですよね。たまに話にあがる bsearch
>とか。ソート済みの複数の並びをマージするなんてのもあっていい
>ような気がします。
>(COBOL ではこれをマッチングというらしいのですが)

確かにそれは言えますよねぇ.

fairyでは, 分散ソートの内部処理でマージソートを使っているのですが, そ
ういうのがあるとかなり便利です(^^;;

>あー、場合にもよるんですが、IO や Array に対する Enumerator
>がそのような意味で応用的であるというのは間違っていると考えて
>います。IO や Array などに対する外部イテレータを実現するのは
>簡単なのに、Fiber を使うのは無駄が過ぎます。

私もそう思っています. それに, threadをまたげないので, 複数スレッドにま
たがるqueue見たいのも実現できないですし...

>たとえば、enum = io.lines としたときに enum.next は、結局
>io.gets するだけなのに、Fiber が使われるのはなんとも無駄です。

ですよねぇ...

>もし、Enumerator.external_iterator { ... } というような形式
>で enumerator が生成できて、next は指定したブロックを呼ぶだ
>け、というのが実現できれば、(私の構想では next は先読みの処
>理もしますが) io.lines は
>  Enumerator.external_iterator { io.gets or raise StopIteration }
>で実現できます。

getsとかなら, それで行けそうですね.

>IO, Array, Range 等、基本的なクラスの Enumerator は、ちょっ
>とがんばって効率の良い外部イテレータを提供して良いのではない
>かと思っています。

Arrayなんかは, 上記の Enumerator.external_iterator みたいな, やり方で
は実現できそうもない(fiber使えば別ですが(^^;;)ので別途対処が必要ですね.

>そういえば、[ruby-dev:38934] のコードで
>
>| a = %w[banana banana durian orange orange orange]
>| a.inject_by(proc{|w| w}){|key, sum, value| sum += value}.each{|key,sum| puts "#{key} #{sum}"}
>
>というのは、配列を作らないで済むという点を狙っていると思うの
>ですが、sum += value というところが意味不明です。ブロック変
>数の sum に代入してどうすんだ、とか、value はどこから出てく
>るのか、とか。

ごめんなさい. この場合は

a.inject_by(proc{|w| w}){|key, sum, value| sum += 1}.each{|key,sum| puts "#{key} #{sum}"}

でした. この場合valueには w 自身が渡るのですが. ワード数だけカウントす
るので1足せばよいことになります.

>思うに、複数のマシンに分散させて処理をやろうというなら、単語
>数を数えるときの足し算のように associative な演算は、
>associative であることを利用した仕掛けでやったほうがいいんじゃ
>ないかなぁ、と思います。associative であれば、つまり、
>(a+b)+c=a+(b+c) のような関係の演算であれば、各マシン内で個々
>に結果をまとめられますから。

実際はそのように処理します. まず, ローカルでinject(reduce)して, 各ノー
ドのものをまとめてinject(reduce)します. ですので, 結合律は前提になって
います. 

>inject だと、先頭から順にやっていかなければならない感じがし
>ます。つまり、associative でない演算を与えてよい、という感じ
>が。

あー. inject ってそんなイメージあります? いちおう, reduceという名前も
aliasしていますが, Rubyのinjectと似ているので同じ名前にしました.

>each_with_peek を Enumerator にするというのは、きっと Fiber
>を使うことになりますよね。それは嫌です。

それは, 同意します(^^;;;

>あと、each_with_peek
>は最後の要素での先読みをどうするかが問題ですかね。nil とする
>と、nil という要素があったときと区別できません。

確かに, それはあって, 配列で受けた場合は, 要素数減らすのかなぁとか考え
たのですが... あまりきれいに処理できない気がしています.

>あと、slice_by は配列にしちゃいますから、メモリの点で嫌です。

a = %w[banana banana durian orange orange orange]
a.slice_by {|w| w }.each {|key, values| puts "#{key} #{values.size}" }  

の values のことです? 

>slice_by は slice_by でいいんじゃないでしょうか。
>slice_by で簡単にできることは、slice_by でやるほうがいいと思
>います。

>peek は、より低級でより応用範囲が広いものが狙いです。

低級なのは認めます(^^; 応用範囲はまだ?ですが...

>コントロールブレークでブレークキーが複数あるというのは、結構
>一般的みたいです。情報処理技術者試験に出てくるほど。

>読んだことはないので確かなわけじゃないですが、「二段のコント
>ロールブレイク処理」などと目次にある本もあるようです。
>http://gihyo.jp/book/2002/4-7741-1607-6

これに関してですが, 

slice_byで valuesが来たらそれを今度は第2要素でslice_byすればよいような
気がします.

a = [[word1 docid1 linenum1],
     [word1 docid1 linenum2],...

a.slice_by{|l| l[0]}.each do |key, values|
  values.slice_by{|l| l[1]}.each do |key1, values1|
    ...

2段のコントロールブレーク処理を勘違いしていなければですが.

なんだか, slice_byは結構使えるかもって気になってきました(^^;;;
配列はどんどん出来てしまいますけどね(^^;

>peek は、そういうところを支援するベースになるものです。

slice_byを Ruby(のスクリプト)で実現したければ peekもしくはpeekと同じ処
理が必要になりますね. ---(1)

>そのまま使うというよりは部品なんですが、先読みが必要なのは
>(構文解析と考えると) かなり確かなので、まずそこをつけるのは
>どうか、という話です。

たしかに, (1)のようなことが実現できるので peek があるといろいろ便利な
気がしてきました.

それに 実装も, これによって実行コストが目に見えて増えるってわけでもな
いですしね.



__
---------------------------------------------------->> 石塚 圭樹 <<---
---------------------------------->> e-mail: [e-mail] <<---