Enumerator::Lazy は無限数列を扱うことができるが、それを使って「エラトステネスの篩」をちょっとおもしろく実装できることに気づいた。何はともあれコードである。
lazy_prime.rb
prime_seq = Enumerator.new do |y| sieve = 2.step.lazy loop do a = sieve.first y << a sieve = sieve.reject {|x| (x % a).zero?} end end prime_seq.take(10) #=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Enumerator::Lazy はsieve = 2.step.lazy
のところで生成している。これの先頭a
は必ず素数なので、素数列として Enumerator で取り出す(y << a
)。そして、sieve
からa
の倍数をreject
ですべて篩い落とし(Lazy だから可能なのである)、そうされたものを新しいsieve
とする。以下、繰り返し、というわけである。
これは子供の頃に紙と鉛筆でやってみた「エラトステネスの篩」のやり方そのものである。小さい方から素数に丸でも打っておいて、その倍数を斜線で消していく…。実装としては、素直といえば素直だ。
しかし、これ、めちゃめちゃに遅いのはすぐわかる。素数ひとつ得るたびに、Enumerator::Lazy オブジェクトを作り直しているのだから、どれほど遅いかというと、例えば最初の 500個の素数を得るのに、この方法だとわたしの環境でなんと 2.8秒ほどもかかる。標準添付ライブラリの prime を使うと 0.0002秒ほどだから、比較にもならない。
でもまあ、ちょっとおもしろかったので書いてみた。
なお、単なる Enumerator ももちろん無限数列を扱うことができるが、map
やselect
、それにここで使ったreject
などの結果が有限数列(Array)になってしまう。なので、Enumerator::Lazy を使ったのである。為念。