From: "Yugui (Yuki Sonoda)" Date: 2008-08-26T22:09:25+09:00 Subject: [ruby-dev:35983] Re: Refactoring of enumerating prime numbers This is a multi-part message in MIME format. --------------070700020102060800000603 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit Yuguiです。 石塚圭樹 さんは書きました: >>> 私もそうなのかなぁ? と思いつつも, では, 元のクラスの名前はどうするんだ? >>> と思ったりもしてます. >> class << (Prime = Object.new); end で。 私が送ったコードも既存のPrime.newしているコードに配慮してはいますが、 互換性をより確実に提供するという意味ではPrimeがクラスで有り続けたほうが 良いかもしれません。 ただ、その意味では石塚さんの、Primeを完全にシングルトンパターンにしてし まうのはPrime.newできないので困ると思います。 もう一度整理します。 1. 素数全体を表すEnumerableなオブジェクトは唯一であるべき(yugui) 互換性のためにPrime.newできるのは仕方がないが、非推奨としたい => Primeを特異クラスを持つオブジェクトか、singletonパターン的なクラスに 2. 素数全体を表すものはインスタンスであるべき(石塚さん) => Primeがクラスというのはまずい。 Primeへのメソッド呼び出しをPrimeのインスタンスへ委譲するならばありえる。 3. 素数列挙の途中の状態を保持する外部イテレータが必要 4. 疑似素数列を生成するGeneratorもほしい => Prime::Generator, Prime::Generator23, Prime::EratosthenesGenerator Prime::*の定数スコープを提供するためにもPrimeは、私が書いたような singletonなオブジェクトよりは、石塚さんのようなsingletonパターンのほうが 良さそうに思えます。 ただし、互換性のためにPrime.newも許容するようにしてみました。このバー ジョンのprime.rbを添付します。 この他、 a) エラトステネスのふるいでGeneratorを書いてみたらとても速くなったので、 Prime::EratosthenesGeneratorを加えてあります。 user system total real trial division 17.060000 22.580000 39.640000 ( 39.556764) eratosthenes 2.270000 0.010000 2.280000 ( 2.277945) b) Prime.eachが上界をとるようにしてみました。そこに到達したら列挙を打ち 切ります。 c) Prime.eachの第2引数にgeneratorを指定できるようにしてみました。 d) Prime.eachとPrime.each.eachが同じオブジェクトであるために列挙状態を共 有してしまいます。generatorがselfではなくself.dupを返すようにしました。 e) Enumeratorに合わせて、Generatorにwith_indexとnextとrewindを足しました。 > * Prime::IncreaseSuperPrimeGenerator > 上記2つのgeneratorの抽象スーパークラス > 名前はいまいちなんですが, 昇順で, 素数集合のスーパーセットになる > generator ということろからとっています. > よい名前募集中 確かにこの名前には違和感がありますね。 PseudoPrimeGeneratorあたりではどうでしょうか。Generator23みたいに「疑 似」の精度が悪くても、逆に真にprimeであってもPseudoのサブセットにはなる と思います。 -- Yugui http://yugui.jp 私は私をDumpする --------------070700020102060800000603 Content-Type: text/plain; x-mac-type="0"; x-mac-creator="0"; name="prime.rb" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="prime.rb" cmVxdWlyZSAic2luZ2xldG9uIgpyZXF1aXJlICJmb3J3YXJkYWJsZSIKCmNsYXNzIEludGVn ZXIKCiAgZGVmIEludGVnZXIuZnJvbV9wcmltZV9kaXZpc2lvbihwZCkKICAgIFByaW1lLmlu dF9mcm9tX3ByaW1lX2RpdmlzaW9uKHBkKQogIGVuZAogIAogIGRlZiBwcmltZV9kaXZpc2lv bihnZW5lcmF0b3IgPSBQcmltZTo6R2VuZXJhdG9yMjMubmV3KQogICAgUHJpbWUucHJpbWVf ZGl2aXNpb24oc2VsZiwgZ2VuZXJhdG9yKQogIGVuZAoKICBkZWYgcHJpbWU/CiAgICBQcmlt ZS5wcmltZT8oc2VsZikKICBlbmQKCiAgZGVmIEludGVnZXIuZWFjaF9wcmltZSh1Ym91bmQs ICZibG9jaykKICAgIFByaW1lLmVhY2godWJvdW5kLCAmYmxvY2spCiAgZW5kCmVuZAogIApj bGFzcyBQcmltZQogIGluY2x1ZGUgRW51bWVyYWJsZQogIEB0aGVfaW5zdGFuY2UgPSBQcmlt ZS5uZXcKCiAgZGVmIGluaXRpYWxpemUKICAgIHdhcm4gIlByaW1lOjpuZXcgaXMgb2Jzb2xl dGUuIHVzZSBQcmltZTo6aW5zdGFuY2Ugb3IgY2xhc3MgbWV0aG9kcyBvZiBQcmltZS4iCiAg ZW5kCgogIGNsYXNzPDxzZWxmCiAgICBleHRlbmQgRm9yd2FyZGFibGUKICAgIGluY2x1ZGUg RW51bWVyYWJsZQogICAgZGVmIGluc3RhbmNlOyBAdGhlX2luc3RhbmNlIGVuZAoKICAgIGRl ZiBtZXRob2RfYWRkZWQobWV0aG9kKQogICAgICAjcHV0cyAibWV0aG9kIGFkZDogI3ttZXRo b2R9IgogICAgICAoY2xhc3M8PHNlbGY7c2VsZjtlbmQpLmRlZl9kZWxlZ2F0b3IgOmluc3Rh bmNlLCBtZXRob2QKICAgIGVuZAogIGVuZAoKICBkZWYgZWFjaCh1Ym91bmQgPSBuaWwsIGdl bmVyYXRvciA9IEdlbmVyYXRvci5uZXcsICZibG9jaykKICAgIGdlbmVyYXRvci5lYWNoKHVi b3VuZCwgJmJsb2NrKQogIGVuZAoKICBkZWYgcHJpbWU/KHZhbHVlLCBnZW5lcmF0b3IgPSBQ cmltZTo6R2VuZXJhdG9yMjMubmV3KQogICAgZm9yIG51bSBpbiBnZW5lcmF0b3IKICAgICAg cmV0dXJuIGZhbHNlIGlmIHZhbHVlICUgbnVtID09IDAKICAgICAgcmV0dXJuIHRydWUgaWYg dmFsdWUgPiBudW0gKiBudW0KICAgIGVuZAogIGVuZAoKICBkZWYgaW50X2Zyb21fcHJpbWVf ZGl2aXNpb24ocGQpCiAgICBwZC5pbmplY3QoMSl7fHZhbHVlLCAocHJpbWUsIGluZGV4KXwK ICAgICAgdmFsdWUgKj0gcHJpbWUqKmluZGV4CiAgICB9CiAgZW5kCgogIGRlZiBwcmltZV9k aXZpc2lvbih2YWx1ZSwgZ2VuZXJhdG9yPSBQcmltZTo6R2VuZXJhdG9yMjMubmV3KQogICAg cmFpc2UgWmVyb0RpdmlzaW9uRXJyb3IgaWYgc2VsZiA9PSAwCiAgICBwdiA9IFtdCiAgICBm b3IgcHJpbWUgaW4gZ2VuZXJhdG9yCiAgICAgIGNvdW50ID0gMAogICAgICB3aGlsZSAodmFs dWUxLCBtb2QgPSB2YWx1ZS5kaXZtb2QocHJpbWUpCgkgICAgIG1vZCkgPT0gMAoJdmFsdWUg PSB2YWx1ZTEKCWNvdW50ICs9IDEKICAgICAgZW5kCiAgICAgIGlmIGNvdW50ICE9IDAKCXB2 LnB1c2ggW3ByaW1lLCBjb3VudF0KICAgICAgZW5kCiAgICAgIGJyZWFrIGlmIHByaW1lICog cHJpbWUgID49IHZhbHVlCiAgICBlbmQKICAgIGlmIHZhbHVlID4gMQogICAgICBwdi5wdXNo IFt2YWx1ZSwgMV0KICAgIGVuZAogICAgcmV0dXJuIHB2CiAgZW5kCgogIGNsYXNzIEluY3Jl YXNlU3VwZXJQcmltZUdlbmVyYXRvcgogICAgaW5jbHVkZSBFbnVtZXJhYmxlCgogICAgZGVm IHN1Y2MKICAgICAgcmFpc2UgTm90SW1wbGVtZW50ZWRFcnJvciwgIm5lZWQgdG8gZGVmaW5l IGBzdWNjJyIKICAgIGVuZAogICAgZGVmIG5leHQKICAgICAgcmFpc2UgTm90SW1wbGVtZW50 ZWRFcnJvciwgIm5lZWQgdG8gZGVmaW5lIGBuZXh0JyIKICAgIGVuZAogICAgZGVmIHJld2lu ZAogICAgICByYWlzZSBOb3RJbXBsZW1lbnRlZEVycm9yLCAibmVlZCB0byBkZWZpbmUgYHJl d2luZCciCiAgICBlbmQKCiAgICBkZWYgZWFjaCh1Ym91bmQgPSBuaWwsICZibG9jaykKICAg ICAgcmV0dXJuIHNlbGYuZHVwIHVubGVzcyBibG9jawogICAgICBpZiB1Ym91bmQKCWxvb3Ag ZG8KCSAgcCA9IHN1Y2MKCSAgYnJlYWsgaWYgcCA+IHVib3VuZAoJICBibG9jay5jYWxsIHAK CWVuZAogICAgICBlbHNlCglsb29wIGRvCgkgIGJsb2NrLmNhbGwgc3VjYwoJZW5kCiAgICAg IGVuZAogICAgZW5kCiAgICBhbGlhcyB3aXRoX2luZGV4IGVhY2hfd2l0aF9pbmRleAogIGVu ZAogIElTUEcgPSBJbmNyZWFzZVN1cGVyUHJpbWVHZW5lcmF0b3IKICAKICBjbGFzcyBHZW5l cmF0b3I8SVNQRwogICAgZGVmIGluaXRpYWxpemUKICAgICAgQGluZGV4ID0gLTEKICAgIGVu ZAogICAgCiAgICBkZWYgc3VjYwogICAgICBQcmltZVNldC5pbnN0YW5jZVtAaW5kZXggKz0g MV0KICAgIGVuZAogICAgZGVmIHJld2luZAogICAgICBpbml0aWFsaXplCiAgICBlbmQKICAg IGFsaWFzIG5leHQgc3VjYwogIGVuZAoKICBjbGFzcyBFcmF0b3N0aGVuZXNHZW5lcmF0b3Ig PElTUEcKICAgIGRlZiBpbml0aWFsaXplCiAgICAgIEBsYXN0X3ByaW1lID0gbmlsCiAgICBl bmQKICAgIAogICAgZGVmIHN1Y2MKICAgICAgQGxhc3RfcHJpbWUgPSBAbGFzdF9wcmltZSA/ IEVyYXRvc3RoZW5lc1NpZXZlLmluc3RhbmNlLm5leHRfdG8oQGxhc3RfcHJpbWUpIDogMgog ICAgZW5kCiAgICBkZWYgcmV3aW5kCiAgICAgIGluaXRpYWxpemUKICAgIGVuZAogICAgYWxp YXMgbmV4dCBzdWNjCiAgZW5kCgogIGNsYXNzIEdlbmVyYXRvcjIzPElTUEcKICAgIGRlZiBp bml0aWFsaXplCiAgICAgIEBwcmltZSA9IDEKICAgICAgQHN0ZXAgPSBuaWwKICAgIGVuZAog ICAgCiAgICBkZWYgc3VjYwogICAgICBsb29wIGRvCglpZiAoQHN0ZXApCgkgIEBwcmltZSAr PSBAc3RlcAoJICBAc3RlcCA9IDYgLSBAc3RlcAoJZWxzZQoJICBjYXNlIEBwcmltZQoJICB3 aGVuIDE7IEBwcmltZSA9IDIKCSAgd2hlbiAyOyBAcHJpbWUgPSAzCgkgIHdoZW4gMzsgQHBy aW1lID0gNTsgQHN0ZXAgPSAyCgkgIGVuZAoJZW5kCglyZXR1cm4gQHByaW1lCiAgICAgIGVu ZAogICAgZW5kCiAgICBhbGlhcyBuZXh0IHN1Y2MKICAgIGRlZiByZXdpbmQKICAgICAgaW5p dGlhbGl6ZQogICAgZW5kCiAgZW5kCgogIGNsYXNzIFByaW1lU2V0CiAgICBpbmNsdWRlIFNp bmdsZXRvbgoKICAgIGRlZiBpbml0aWFsaXplCiAgICAgICMgVGhlc2UgYXJlIGluY2x1ZGVk IGFzIGNsYXNzIHZhcmlhYmxlcyB0byBjYWNoZSB0aGVtIGZvciBsYXRlciB1c2VzLiAgSWYg bWVtb3J5CiAgICAgICMgICB1c2FnZSBpcyBhIHByb2JsZW0sIHRoZXkgY2FuIGJlIHB1dCBp biBQcmltZSNpbml0aWFsaXplIGFzIGluc3RhbmNlIHZhcmlhYmxlcy4KCiAgICAgICMgVGhl cmUgbXVzdCBiZSBubyBwcmltZXMgYmV0d2VlbiBAcHJpbWVzWy0xXSBhbmQgQG5leHRfdG9f Y2hlY2suCiAgICAgIEBwcmltZXMgPSBbMiwgMywgNSwgNywgMTEsIDEzLCAxNywgMTksIDIz LCAyOSwgMzEsIDM3LCA0MSwgNDMsIDQ3LCA1MywgNTksIDYxLCA2NywgNzEsIDczLCA3OSwg ODMsIDg5LCA5NywgMTAxXQogICAgICAjIEBuZXh0X3RvX2NoZWNrICUgNiBtdXN0IGJlIDEu ICAKICAgICAgQG5leHRfdG9fY2hlY2sgPSAxMDMgICAgICAgICAgICAjIEBwcmltZXNbLTFd IC0gQHByaW1lc1stMV0gJSA2ICsgNwogICAgICBAdWx0aWNoZWNrX2luZGV4ID0gMyAgICAg ICAgICAgICMgQHByaW1lcy5pbmRleChAcHJpbWVzLnJldmVyc2UuZmluZCB7fG58CiAgICAg ICMgICBuIDwgTWF0aC5zcXJ0KEBAbmV4dF90b19jaGVjaykgfSkKICAgICAgQHVsdGljaGVj a19uZXh0X3NxdWFyZWQgPSAxMjEgICAjIEBwcmltZXNbQHVsdGljaGVja19pbmRleCArIDFd ICoqIDIKICAgIGVuZAoKICAgICMgUmV0dXJuIHRoZSBwcmltZSBjYWNoZS4KICAgIGRlZiBj YWNoZQogICAgICByZXR1cm4gQHByaW1lcwogICAgZW5kCiAgICBhbGlhcyBwcmltZXMgY2Fj aGUKICAgIGFsaWFzIHByaW1lc19zb19mYXIgY2FjaGUKCiAgICBkZWYgW10oaW5kZXgpCiAg ICAgIHdoaWxlIGluZGV4ID49IEBwcmltZXMubGVuZ3RoCgkjIE9ubHkgY2hlY2sgZm9yIHBy aW1lIGZhY3RvcnMgdXAgdG8gdGhlIHNxdWFyZSByb290IG9mIHRoZSBwb3RlbnRpYWwgcHJp bWVzLAoJIyAgIGJ1dCB3aXRob3V0IHRoZSBwZXJmb3JtYW5jZSBoaXQgb2YgYW4gYWN0dWFs IHNxdWFyZSByb290IGNhbGN1bGF0aW9uLgoJaWYgQG5leHRfdG9fY2hlY2sgKyA0ID4gQHVs dGljaGVja19uZXh0X3NxdWFyZWQKCSAgQHVsdGljaGVja19pbmRleCArPSAxCgkgIEB1bHRp Y2hlY2tfbmV4dF9zcXVhcmVkID0gQHByaW1lcy5hdChAdWx0aWNoZWNrX2luZGV4ICsgMSkg KiogMgoJZW5kCgkjIE9ubHkgY2hlY2sgbnVtYmVycyBjb25ncnVlbnQgdG8gb25lIGFuZCBm aXZlLCBtb2R1bG8gc2l4LiBBbGwgb3RoZXJzCgoJIyAgIGFyZSBkaXZpc2libGUgYnkgdHdv IG9yIHRocmVlLiAgVGhpcyBhbHNvIGFsbG93cyB1cyB0byBza2lwIGNoZWNraW5nIGFnYWlu c3QKCSMgICB0d28gYW5kIHRocmVlLgoJQHByaW1lcy5wdXNoIEBuZXh0X3RvX2NoZWNrIGlm IEBwcmltZXNbMi4uQHVsdGljaGVja19pbmRleF0uZmluZCB7fHByaW1lfCBAbmV4dF90b19j aGVjayAlIHByaW1lID09IDAgfS5uaWw/CglAbmV4dF90b19jaGVjayArPSA0CglAcHJpbWVz LnB1c2ggQG5leHRfdG9fY2hlY2sgaWYgQHByaW1lc1syLi5AdWx0aWNoZWNrX2luZGV4XS5m aW5kIHt8cHJpbWV8IEBuZXh0X3RvX2NoZWNrICUgcHJpbWUgPT0gMCB9Lm5pbD8KCUBuZXh0 X3RvX2NoZWNrICs9IDIgCiAgICAgIGVuZAogICAgICByZXR1cm4gQHByaW1lc1tpbmRleF0K ICAgIGVuZAogIGVuZAoKICBjbGFzcyBFcmF0b3N0aGVuZXNTaWV2ZQogICAgaW5jbHVkZSBT aW5nbGV0b24KCiAgICBkZWYgaW5pdGlhbGl6ZQogICAgICAjIGJpdG1hcCBmb3Igb2RkIHBy aW1lIG51bWJlcnMgbGVzcyB0aGFuIDI1Ni4KICAgICAgIyBmb3IgYW4gb2RkIG51bWJlciBu LCBAdGFibGVbaV1bal0gaXMgMSB3aGVuIG4gaXMgcHJpbWUsIHdoZXJlIGksaiA9IG4uZGl2 bW9kKDMyKSAuCiAgICAgIEB0YWJsZSA9IFsweGNiNmUsIDB4NjRiNCwgMHgxMjlhLCAweDgx NmQsIDB4NGMzMiwgMHg4NjRhLCAweDgyMGQsIDB4MjE5Nl0KICAgIGVuZAoKICAgICMgcmV0 dXJucyB0aGUgbGVhc3Qgb2RkIHByaW1lIG51bWJlciB3aGljaCBpcyBncmVhdGVyIHRoYW4g K24rLgogICAgZGVmIG5leHRfdG8obikKICAgICAgbiA9IChuLTEpLmRpdigyKSoyKzMgIyB0 aGUgbmV4dCBvZGQgbnVtYmVyIG9mIGdpdmVuIG4KICAgICAgaSxqID0gbi5kaXZtb2QoMzIp CiAgICAgIGxvb3AgZG8KCWV4dGVuZF90YWJsZSB1bnRpbCBAdGFibGUubGVuZ3RoID4gaQoJ aWYgIUB0YWJsZVtpXS56ZXJvPwoJICAoai4uLjMyKS5zdGVwKDIpIGRvIHxqfAoJICAgIHJl dHVybiAzMippK2ogaWYgIUB0YWJsZVtpXVtqLmRpdigyKV0uemVybz8KCSAgZW5kCgllbmQK CWkgKz0gMTsgaiA9IDEKICAgICAgZW5kCiAgICBlbmQKICAgIHByaXZhdGUKICAgIGRlZiBl eHRlbmRfdGFibGUKICAgICAgb3JpZ19sZW4gPSBAdGFibGUubGVuZ3RoCiAgICAgIG5ld19s ZW4gPSBbb3JpZ19sZW4qKjIsIG9yaWdfbGVuKzI1Nl0ubWluCiAgICAgIGxib3VuZCA9IG9y aWdfbGVuKjMyCiAgICAgIHVib3VuZCA9IG5ld19sZW4qMzIKICAgICAgQHRhYmxlLmZpbGwo MHhGRkZGLCBvcmlnX2xlbi4uLm5ld19sZW4pCiAgICAgICgzLi5JbnRlZ2VyKE1hdGguc3Fy dCh1Ym91bmQpKSkuc3RlcCgyKSBkbyB8cHwKCWksIGogPSBwLmRpdm1vZCgzMikKCW5leHQg aWYgQHRhYmxlW2ldW2ouZGl2KDIpXS56ZXJvPwoKCXN0YXJ0ID0gKGxib3VuZC5kaXYoMipw KSoyKzEpKnAgICAgIyBvZGQgbXVsdGlwbGUgb2YgcCB3aGljaCBpcyBncmVhdGVyIHRoYW4g b3IgZXF1YWwgdG8gbGJvdW5kCgkoc3RhcnQuLi51Ym91bmQpLnN0ZXAoMipwKSBkbyB8bnwK CSAgaSwgaiA9IG4uZGl2bW9kKDMyKQoJICBAdGFibGVbaV0gJj0gMHhGRkZGIF4gKDE8PChq LmRpdigyKSkpCgllbmQKICAgICAgZW5kCiAgICBlbmQKICBlbmQKZW5kCg== --------------070700020102060800000603 Content-Type: text/plain; x-mac-type="0"; x-mac-creator="0"; name="prime_bench.rb" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="prime_bench.rb" cmVxdWlyZSAncHJpbWUucmInCnJlcXVpcmUgJ2JlbmNobWFyaycKCm1heCA9IDB4MTAwMDAw CkJlbmNobWFyay5ibSBkbyB8eHwKICB4LnJlcG9ydCgidHJpYWwgZGl2aXNpb24iKSB7IGMg PSAwOyBQcmltZS5lYWNoKG1heCwgUHJpbWU6OkdlbmVyYXRvci5uZXcpe3x4fCBjKz0xIH07 IHAgY30gCiAgeC5yZXBvcnQoImVyYXRvc3RoZW5lcyIpICAgeyBjID0gMDsgUHJpbWUuZWFj aChtYXgsIFByaW1lOjpFcmF0b3N0aGVuZXNHZW5lcmF0b3IubmV3KXt8eHwgYys9MSB9OyBw IGN9IAplbmQK --------------070700020102060800000603--