From: "Yugui (Yuki Sonoda)" Date: 2008-08-17T23:13:26+09:00 Subject: [ruby-dev:35867] Re: Refactoring of enumerating prime numbers This is a multi-part message in MIME format. --------------020908050006030200000000 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit Yuguiです。 いしづかさん、ありがとうございます。 keiju ISHITSUKA さんは書きました: >> == mathn.rbに入っている >> 素数列挙は整数に閉じた計算でも必要になるものなので、mathn.rbがもたらす >> int / int => rational >> は嬉しくないことがあります。 > > 分からないことはないです. (snip) > そのあたりが, lib/prime.rb でなく lib/math/prime.rb という遠慮になって > いるような気がします. そうですね。私もlib/prime.rbは大げさすぎると感じました。場所は他に適当な ものを思いつかなかったのでlib/math/prime.rbにしたまでですが、分けていた だけると助かります。 >> == インスタンスを生成する >> 要するに、Primeオブジェクトは素数列挙に対する外部イテレータです。 >> これは少し奇妙に思えます。 > > 全然奇妙でもないと思いますが? 概念的には, Primeインスタンスが素数の集 > 合を表していると考えているからです. その素数集合から数え上げていると考 > えているのでこのようなインターフェースになっています. 素数の全体のインスタンスが複数存在し得るのはおかしいです。整数の全体に対 応するものがIntegerであるように、素数の全体に対応するのはPrimeであるほう が自然だと感じました。 結局、素数の全体をRubyにおいてどうやって表すかという同じところについての 見解の相違に帰結するのでしょうが、 > for prime in Prime > # ... > end > > って書くとおかしい気がするので, 私にはおかしくなく、こちらのほうが表記として自然だと感じられます。 素数全体というもののRuby表現が複数存在し得るようになっているのは、やはり 外部イテレータとしての機能を期待されていたがためではないでしょうか。 私としては、その機能を抜けば素数全体は唯一であるべきであると考えます。 そして、実装上の指摘3点について、 (1) > 現行のPrimeから内部イテレータを実現する方法とYuguiさんの内部イテレータ > からEnumertorを利用する方法とどちらが自然かといえば, 外部イテレータを > 実現するためにFiberを用いている方がよっぽど不自然だと思います. 牛刀っ > て感じがします. 牛刀といえばそうかもしれません。 (2) > Enumeratorと外部イテレータとしてのPrimeインスタンスですが, Enumerator > はスレッドの境界を越えられないという制約がありますので, そのような制約 > のないPrimeからわざわざダウグレードする必要はないです. 確かに。 (3) > 次に, 実装的側面から, Yuguiさんの実装はでは, Integerのクラス変数として > > @@primes > @@next_to_check > @@ulticheck_index > @@ulticheck_next_squared > > とうが, 導入されていますが, これはとても許せないですね. Integerのクラ > ス変数としてはふさわしくないと思います. これも確かに。 であれば、こういうのはどうでしょうか。 1. Prime::Generator という素数列挙の外部イテレータクラスを作成 1.1. 互換性のため、また内部イテレータの提供者としてPrimeクラスを温存 2. Prime.each は Prime::Generator オブジェクトを呼び出して列挙 3. (optional) Integer.each_primeはPrime.eachに転送 このように変更してみたパッチを添付します。 理由としては、 1. わざわざ外部イテレータのクラスを新設するのは、実装上で指摘を頂いたデ メリットは納得できる一方で、やはり素数全体を表すインスタンスが複数存在す るのは違和感を持つためです。Primeのインスタンスが外部イテレータであるこ とを避けられれば、インスタンス化はobsoleteにできます。 2. Prime.eachという用法は欲しいです。そして、これは単なる利便性のためだ けではなく「素数全体」をあらわすのがPrime定数、つまり唯一であってほしい からです。 3. Integer.each_primeはどうしても欲しいというほどではありませんが、素数 列挙機能があって整数クラスがあるならば、整数クラスに列挙機能が付いていた 方が自然であると感じます。 -- Yugui http://yugui.jp 私は私をDumpする --------------020908050006030200000000 Content-Type: text/plain; x-mac-type="0"; x-mac-creator="0"; name="prime.diff" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="prime.diff" ZGlmZiAtLWdpdCBhL2xpYi9tYXRoL3ByaW1lLnJiIGIvbGliL21hdGgvcHJpbWUucmIKbmV3 IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMC4uMzZlNmIyNgotLS0gL2Rldi9udWxs CisrKyBiL2xpYi9tYXRoL3ByaW1lLnJiCkBAIC0wLDAgKzEsMTIwIEBACitjbGFzcyBJbnRl Z2VyCisKKyAgZGVmIEludGVnZXIuZnJvbV9wcmltZV9kaXZpc2lvbihwZCkKKyAgICB2YWx1 ZSA9IDEKKyAgICBmb3IgcHJpbWUsIGluZGV4IGluIHBkCisgICAgICB2YWx1ZSAqPSBwcmlt ZSoqaW5kZXgKKyAgICBlbmQKKyAgICB2YWx1ZQorICBlbmQKKyAgCisgIGRlZiBwcmltZV9k aXZpc2lvbgorICAgIHJhaXNlIFplcm9EaXZpc2lvbkVycm9yIGlmIHNlbGYgPT0gMAorICAg IHBzID0gUHJpbWUubmV3CisgICAgdmFsdWUgPSBzZWxmCisgICAgcHYgPSBbXQorICAgIGZv ciBwcmltZSBpbiBwcworICAgICAgY291bnQgPSAwCisgICAgICB3aGlsZSAodmFsdWUxLCBt b2QgPSB2YWx1ZS5kaXZtb2QocHJpbWUpCisJICAgICBtb2QpID09IDAKKwl2YWx1ZSA9IHZh bHVlMQorCWNvdW50ICs9IDEKKyAgICAgIGVuZAorICAgICAgaWYgY291bnQgIT0gMAorCXB2 LnB1c2ggW3ByaW1lLCBjb3VudF0KKyAgICAgIGVuZAorICAgICAgYnJlYWsgaWYgcHJpbWUg KiBwcmltZSAgPj0gdmFsdWUKKyAgICBlbmQKKyAgICBpZiB2YWx1ZSA+IDEKKyAgICAgIHB2 LnB1c2ggW3ZhbHVlLCAxXQorICAgIGVuZAorICAgIHJldHVybiBwdgorICBlbmQKKworICBk ZWYgSW50ZWdlci5lYWNoX3ByaW1lKCZwcm9jKQorICAgIFByaW1lLmVhY2goJnByb2MpCisg IGVuZAorZW5kCisgIAorY2xhc3MgUHJpbWUKKyAgaW5jbHVkZSBFbnVtZXJhYmxlCisKKyAg ZGVmIGVhY2goJnByb2MpCisgICAgR2VuZXJhdG9yLm5ldy5lYWNoKCZwcm9jKQorICBlbmQK KworICBjbGFzcyA8PCBzZWxmCisgICAgaW5jbHVkZSBFbnVtZXJhYmxlCisgICAgIyBSZXR1 cm4gdGhlIHByaW1lIGNhY2hlLgorICAgIGRlZiBjYWNoZQorICAgICAgR2VuZXJhdG9yLmNh Y2hlCisgICAgZW5kCisgICAgYWxpYXMgcHJpbWVzIGNhY2hlCisgICAgYWxpYXMgcHJpbWVz X3NvX2ZhciBjYWNoZQorICAgIGRlZiBlYWNoKCZwcm9jKQorICAgICAgR2VuZXJhdG9yLm5l dy5lYWNoKCZwcm9jKQorICAgIGVuZAorICBlbmQKKworICBjbGFzcyBHZW5lcmF0b3IKKyAg ICBpbmNsdWRlIEVudW1lcmFibGUKKyAgICAjIFRoZXNlIGFyZSBpbmNsdWRlZCBhcyBjbGFz cyB2YXJpYWJsZXMgdG8gY2FjaGUgdGhlbSBmb3IgbGF0ZXIgdXNlcy4gIElmIG1lbW9yeQor ICAgICMgICB1c2FnZSBpcyBhIHByb2JsZW0sIHRoZXkgY2FuIGJlIHB1dCBpbiBQcmltZSNp bml0aWFsaXplIGFzIGluc3RhbmNlIHZhcmlhYmxlcy4KKworICAgICMgVGhlcmUgbXVzdCBi ZSBubyBwcmltZXMgYmV0d2VlbiBAQHByaW1lc1stMV0gYW5kIEBAbmV4dF90b19jaGVjay4K KyAgICBAQHByaW1lcyA9IFsyLCAzLCA1LCA3LCAxMSwgMTMsIDE3LCAxOSwgMjMsIDI5LCAz MSwgMzcsIDQxLCA0MywgNDcsIDUzLCA1OSwgNjEsIDY3LCA3MSwgNzMsIDc5LCA4MywgODks IDk3LCAxMDFdCisgICAgIyBAQG5leHRfdG9fY2hlY2sgJSA2IG11c3QgYmUgMS4gIAorICAg IEBAbmV4dF90b19jaGVjayA9IDEwMyAgICAgICAgICAgICMgQEBwcmltZXNbLTFdIC0gQEBw cmltZXNbLTFdICUgNiArIDcKKyAgICBAQHVsdGljaGVja19pbmRleCA9IDMgICAgICAgICAg ICAjIEBAcHJpbWVzLmluZGV4KEBAcHJpbWVzLnJldmVyc2UuZmluZCB7fG58CisgICAgIyAg IG4gPCBNYXRoLnNxcnQoQEBuZXh0X3RvX2NoZWNrKSB9KQorICAgIEBAdWx0aWNoZWNrX25l eHRfc3F1YXJlZCA9IDEyMSAgICMgQEBwcmltZXNbQEB1bHRpY2hlY2tfaW5kZXggKyAxXSAq KiAyCisKKworICAgICMgUmV0dXJuIHRoZSBwcmltZSBjYWNoZS4KKyAgICBkZWYgc2VsZi5j YWNoZQorICAgICAgcmV0dXJuIEBAcHJpbWVzCisgICAgZW5kCisKKyAgICBkZWYgaW5pdGlh bGl6ZQorICAgICAgQGluZGV4ID0gLTEKKyAgICBlbmQKKworICAgICMgUmV0dXJuIHByaW1l cyBnaXZlbiBieSB0aGlzIGluc3RhbmNlIHNvIGZhci4KKyAgICBkZWYgcHJpbWVzCisgICAg ICByZXR1cm4gQEBwcmltZXNbMCwgQGluZGV4ICsgMV0KKyAgICBlbmQKKyAgICBhbGlhcyBw cmltZXNfc29fZmFyIHByaW1lcworCisgICAgZGVmIHN1Y2MKKyAgICAgIEBpbmRleCArPSAx CisgICAgICB3aGlsZSBAaW5kZXggPj0gQEBwcmltZXMubGVuZ3RoCisJIyBPbmx5IGNoZWNr IGZvciBwcmltZSBmYWN0b3JzIHVwIHRvIHRoZSBzcXVhcmUgcm9vdCBvZiB0aGUgcG90ZW50 aWFsIHByaW1lcywKKwkjICAgYnV0IHdpdGhvdXQgdGhlIHBlcmZvcm1hbmNlIGhpdCBvZiBh biBhY3R1YWwgc3F1YXJlIHJvb3QgY2FsY3VsYXRpb24uCisJaWYgQEBuZXh0X3RvX2NoZWNr ICsgNCA+IEBAdWx0aWNoZWNrX25leHRfc3F1YXJlZAorCSAgQEB1bHRpY2hlY2tfaW5kZXgg Kz0gMQorCSAgQEB1bHRpY2hlY2tfbmV4dF9zcXVhcmVkID0gQEBwcmltZXMuYXQoQEB1bHRp Y2hlY2tfaW5kZXggKyAxKSAqKiAyCisJZW5kCisJIyBPbmx5IGNoZWNrIG51bWJlcnMgY29u Z3J1ZW50IHRvIG9uZSBhbmQgZml2ZSwgbW9kdWxvIHNpeC4gQWxsIG90aGVycworCSMgICBh cmUgZGl2aXNpYmxlIGJ5IHR3byBvciB0aHJlZS4gIFRoaXMgYWxzbyBhbGxvd3MgdXMgdG8g c2tpcCBjaGVja2luZyBhZ2FpbnN0CisJIyAgIHR3byBhbmQgdGhyZWUuCisJQEBwcmltZXMu cHVzaCBAQG5leHRfdG9fY2hlY2sgaWYgQEBwcmltZXNbMi4uQEB1bHRpY2hlY2tfaW5kZXhd LmZpbmQge3xwcmltZXwgQEBuZXh0X3RvX2NoZWNrICUgcHJpbWUgPT0gMCB9Lm5pbD8KKwlA QG5leHRfdG9fY2hlY2sgKz0gNAorCUBAcHJpbWVzLnB1c2ggQEBuZXh0X3RvX2NoZWNrIGlm IEBAcHJpbWVzWzIuLkBAdWx0aWNoZWNrX2luZGV4XS5maW5kIHt8cHJpbWV8IEBAbmV4dF90 b19jaGVjayAlIHByaW1lID09IDAgfS5uaWw/CisJQEBuZXh0X3RvX2NoZWNrICs9IDIgCisg ICAgICBlbmQKKyAgICAgIHJldHVybiBAQHByaW1lc1tAaW5kZXhdCisgICAgZW5kCisgICAg YWxpYXMgbmV4dCBzdWNjCisKKyAgICBkZWYgZWFjaAorICAgICAgcmV0dXJuIHNlbGYgdW5s ZXNzIGJsb2NrX2dpdmVuPworICAgICAgbG9vcCBkbworCXlpZWxkIHN1Y2MKKyAgICAgIGVu ZAorICAgIGVuZAorICAgIGFsaWFzIHdpdGhfaW5kZXggZWFjaF93aXRoX2luZGV4CisgICAg ZGVmIHJld2luZAorICAgICAgQGluZGV4ID0gLTEKKyAgICBlbmQKKyAgZW5kCitlbmQKZGlm ZiAtLWdpdCBhL2xpYi9tYXRobi5yYiBiL2xpYi9tYXRobi5yYgppbmRleCBjZTFhY2M5Li5l NWQwMTkxIDEwMDY0NAotLS0gYS9saWIvbWF0aG4ucmIKKysrIGIvbGliL21hdGhuLnJiCkBA IC0xMiwxMDEgKzEyLDcgQEAKIHJlcXVpcmUgImNvbXBsZXgucmIiCiByZXF1aXJlICJyYXRp b25hbC5yYiIKIHJlcXVpcmUgIm1hdHJpeC5yYiIKLQotY2xhc3MgSW50ZWdlcgotCi0gIGRl ZiBJbnRlZ2VyLmZyb21fcHJpbWVfZGl2aXNpb24ocGQpCi0gICAgdmFsdWUgPSAxCi0gICAg Zm9yIHByaW1lLCBpbmRleCBpbiBwZAotICAgICAgdmFsdWUgKj0gcHJpbWUqKmluZGV4Ci0g ICAgZW5kCi0gICAgdmFsdWUKLSAgZW5kCi0gIAotICBkZWYgcHJpbWVfZGl2aXNpb24KLSAg ICByYWlzZSBaZXJvRGl2aXNpb25FcnJvciBpZiBzZWxmID09IDAKLSAgICBwcyA9IFByaW1l Lm5ldwotICAgIHZhbHVlID0gc2VsZgotICAgIHB2ID0gW10KLSAgICBmb3IgcHJpbWUgaW4g cHMKLSAgICAgIGNvdW50ID0gMAotICAgICAgd2hpbGUgKHZhbHVlMSwgbW9kID0gdmFsdWUu ZGl2bW9kKHByaW1lKQotCSAgICAgbW9kKSA9PSAwCi0JdmFsdWUgPSB2YWx1ZTEKLQljb3Vu dCArPSAxCi0gICAgICBlbmQKLSAgICAgIGlmIGNvdW50ICE9IDAKLQlwdi5wdXNoIFtwcmlt ZSwgY291bnRdCi0gICAgICBlbmQKLSAgICAgIGJyZWFrIGlmIHByaW1lICogcHJpbWUgID49 IHZhbHVlCi0gICAgZW5kCi0gICAgaWYgdmFsdWUgPiAxCi0gICAgICBwdi5wdXNoIFt2YWx1 ZSwgMV0KLSAgICBlbmQKLSAgICByZXR1cm4gcHYKLSAgZW5kCi1lbmQKLSAgCi1jbGFzcyBQ cmltZQotICBpbmNsdWRlIEVudW1lcmFibGUKLSAgIyBUaGVzZSBhcmUgaW5jbHVkZWQgYXMg Y2xhc3MgdmFyaWFibGVzIHRvIGNhY2hlIHRoZW0gZm9yIGxhdGVyIHVzZXMuICBJZiBtZW1v cnkKLSAgIyAgIHVzYWdlIGlzIGEgcHJvYmxlbSwgdGhleSBjYW4gYmUgcHV0IGluIFByaW1l I2luaXRpYWxpemUgYXMgaW5zdGFuY2UgdmFyaWFibGVzLgotCi0gICMgVGhlcmUgbXVzdCBi ZSBubyBwcmltZXMgYmV0d2VlbiBAQHByaW1lc1stMV0gYW5kIEBAbmV4dF90b19jaGVjay4K LSAgQEBwcmltZXMgPSBbMiwgMywgNSwgNywgMTEsIDEzLCAxNywgMTksIDIzLCAyOSwgMzEs IDM3LCA0MSwgNDMsIDQ3LCA1MywgNTksIDYxLCA2NywgNzEsIDczLCA3OSwgODMsIDg5LCA5 NywgMTAxXQotICAjIEBAbmV4dF90b19jaGVjayAlIDYgbXVzdCBiZSAxLiAgCi0gIEBAbmV4 dF90b19jaGVjayA9IDEwMyAgICAgICAgICAgICMgQEBwcmltZXNbLTFdIC0gQEBwcmltZXNb LTFdICUgNiArIDcKLSAgQEB1bHRpY2hlY2tfaW5kZXggPSAzICAgICAgICAgICAgIyBAQHBy aW1lcy5pbmRleChAQHByaW1lcy5yZXZlcnNlLmZpbmQge3xufAotICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAjICAgbiA8IE1hdGguc3FydChAQG5leHRfdG9fY2hlY2sp IH0pCi0gIEBAdWx0aWNoZWNrX25leHRfc3F1YXJlZCA9IDEyMSAgICMgQEBwcmltZXNbQEB1 bHRpY2hlY2tfaW5kZXggKyAxXSAqKiAyCi0KLSAgY2xhc3MgPDwgc2VsZgotICAgICMgUmV0 dXJuIHRoZSBwcmltZSBjYWNoZS4KLSAgICBkZWYgY2FjaGUKLSAgICAgIHJldHVybiBAQHBy aW1lcwotICAgIGVuZAotICAgIGFsaWFzIHByaW1lcyBjYWNoZQotICAgIGFsaWFzIHByaW1l c19zb19mYXIgY2FjaGUKLSAgZW5kCi0gIAotICBkZWYgaW5pdGlhbGl6ZQotICAgIEBpbmRl eCA9IC0xCi0gIGVuZAotICAKLSAgIyBSZXR1cm4gcHJpbWVzIGdpdmVuIGJ5IHRoaXMgaW5z dGFuY2Ugc28gZmFyLgotICBkZWYgcHJpbWVzCi0gICAgcmV0dXJuIEBAcHJpbWVzWzAsIEBp bmRleCArIDFdCi0gIGVuZAotICBhbGlhcyBwcmltZXNfc29fZmFyIHByaW1lcwotICAKLSAg ZGVmIHN1Y2MKLSAgICBAaW5kZXggKz0gMQotICAgIHdoaWxlIEBpbmRleCA+PSBAQHByaW1l cy5sZW5ndGgKLSAgICAgICMgT25seSBjaGVjayBmb3IgcHJpbWUgZmFjdG9ycyB1cCB0byB0 aGUgc3F1YXJlIHJvb3Qgb2YgdGhlIHBvdGVudGlhbCBwcmltZXMsCi0gICAgICAjICAgYnV0 IHdpdGhvdXQgdGhlIHBlcmZvcm1hbmNlIGhpdCBvZiBhbiBhY3R1YWwgc3F1YXJlIHJvb3Qg Y2FsY3VsYXRpb24uCi0gICAgICBpZiBAQG5leHRfdG9fY2hlY2sgKyA0ID4gQEB1bHRpY2hl Y2tfbmV4dF9zcXVhcmVkCi0gICAgICAgIEBAdWx0aWNoZWNrX2luZGV4ICs9IDEKLSAgICAg ICAgQEB1bHRpY2hlY2tfbmV4dF9zcXVhcmVkID0gQEBwcmltZXMuYXQoQEB1bHRpY2hlY2tf aW5kZXggKyAxKSAqKiAyCi0gICAgICBlbmQKLSAgICAgICMgT25seSBjaGVjayBudW1iZXJz IGNvbmdydWVudCB0byBvbmUgYW5kIGZpdmUsIG1vZHVsbyBzaXguIEFsbCBvdGhlcnMKLSAg ICAgICMgICBhcmUgZGl2aXNpYmxlIGJ5IHR3byBvciB0aHJlZS4gIFRoaXMgYWxzbyBhbGxv d3MgdXMgdG8gc2tpcCBjaGVja2luZyBhZ2FpbnN0Ci0gICAgICAjICAgdHdvIGFuZCB0aHJl ZS4KLSAgICAgIEBAcHJpbWVzLnB1c2ggQEBuZXh0X3RvX2NoZWNrIGlmIEBAcHJpbWVzWzIu LkBAdWx0aWNoZWNrX2luZGV4XS5maW5kIHt8cHJpbWV8IEBAbmV4dF90b19jaGVjayAlIHBy aW1lID09IDAgfS5uaWw/Ci0gICAgICBAQG5leHRfdG9fY2hlY2sgKz0gNAotICAgICAgQEBw cmltZXMucHVzaCBAQG5leHRfdG9fY2hlY2sgaWYgQEBwcmltZXNbMi4uQEB1bHRpY2hlY2tf aW5kZXhdLmZpbmQge3xwcmltZXwgQEBuZXh0X3RvX2NoZWNrICUgcHJpbWUgPT0gMCB9Lm5p bD8KLSAgICAgIEBAbmV4dF90b19jaGVjayArPSAyIAotICAgIGVuZAotICAgIHJldHVybiBA QHByaW1lc1tAaW5kZXhdCi0gIGVuZAotICBhbGlhcyBuZXh0IHN1Y2MKLQotICBkZWYgZWFj aAotICAgIHJldHVybiB0b19lbnVtKDplYWNoKSB1bmxlc3MgYmxvY2tfZ2l2ZW4/Ci0gICAg bG9vcCBkbwotICAgICAgeWllbGQgc3VjYwotICAgIGVuZAotICBlbmQKLWVuZAorcmVxdWly ZSAibWF0aC9wcmltZS5yYiIKIAogY2xhc3MgRml4bnVtCiAgIHJlbW92ZV9tZXRob2QgOi8K --------------020908050006030200000000--