From: keiju@... (keiju ISHITSUKA)
Date: 2008-08-29T16:39:20+09:00
Subject: [ruby-dev:36042] Re: Refactoring of enumerating prime numbers

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

In [ruby-dev :35983 ] the message: "[ruby-dev:35983] Re: Refactoring
of enumerating prime numbers ", on Aug/26 22:09(JST) "Yugui (Yuki
Sonoda)" writes:

>Yuguiです。

遅メイルですいません.

>私が送ったコードも既存のPrime.newしているコードに配慮してはいますが、
>互換性をより確実に提供するという意味ではPrimeがクラスで有り続けたほうが
>良いかもしれません。

あとからでてきますが, Generatorを外から呼べなくなりますしね.

>ただ、その意味では石塚さんの、Primeを完全にシングルトンパターンにしてし
>まうのはPrime.newできないので困ると思います。

まあ, 1.9用だから良いかと思って(^^;;


>もう一度整理します。
>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)

おー. 

(2**19-1)**2 の素因数分解でも:

Generator23  0.450000   0.000000   0.450000 (  0.468806)
Generator  3.680000   0.430000   4.110000 (  4.145663)
Eratos  0.620000   0.000000   0.620000 (  0.635689)

けっこう良い値がでています. 

気になるのがどのくらいメモリを消費するかです. n 以下のの素数で考えると:

Generator: 約 n/lon(n) * 4 byte
Eratos:       n/32 byte

になります. オーダーはGeneratorの方が良いです. ただ, 最初のうちは
Eratos の方が空間効率は良いです, Generatorの方がメモリを使わなくなる n
を求めると

  n = 3.8*10**55

となります. その時の使用バイト数は 10**54 byteぐらいになります. そんな
にメモリないので, 現実的な範囲では Eratosの方が空間使用量は少ないとい
えます.

# 検算求む(^^;

ということで, Prime#each の デフォルトの Generator を
EratosthenesGenerator にしましょう. 

あと, 

  Generator を TrialDivisionGenerator
  PrimeSet を TrialDivision 

に改名しましょうか? それと, 掲載順番を Eratosthenes* を先にしましょう
か?

>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
>確かにこの名前には違和感がありますね。
>
>PseudoPrimeGeneratorあたりではどうでしょうか。Generator23みたいに「疑
>似」の精度が悪くても、逆に真にprimeであってもPseudoのサブセットにはなる
>と思います。

そうしましょう. 

何カ所か変更個所がありましたが, いかがでしょう? 

もし, 問題ないようであれば, すいませんが, それを変更してcomit していた
だけないです?


__
---------------------------------------------------->> 石塚 圭樹 <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---