前回の続き。
素数表の検索にバイナリサーチを使う
前回、素数の判定法としてはもっとも素直な「√n 以下の整数で割る」よりは割り算が少なくなると考え、素数表を使った「√n 以下の素数で割る」方法を実装してみた。ところが、列挙範囲の素数表が完成している場合であっても(つまり割り算は一度も行わない)、「√n 以下の整数で割る」方が速いという結果になった。
その原因は Array#include? を使った素数表の検索にあるのではないかと考え、今回は検索に「バイナリサーチ(二分検索)」を使ってみることにした。
(listprimes_binsearch.rb より)
def ($primes).binsearch(n)
len = self.size
first = 0
last = len - 1
while len > 0
mid = first + len / 2
v = self[mid]
if n == v
return true
elsif n < v
last = mid - 1
else
first = mid + 1
end
len = last - first + 1
end
false
end
結果として、Array#include? を使ったものより高速になったことはもちろん、(素数表が完成していれば)列挙する範囲によっては「√n 以下の整数で割る」ものよりも速くなった。とはいえ、やはり素数表を生成しながらの場合は、比較にならないほど遅い。
エラトステネスの篩
素数表の生成でもう少し速そうな方法を試してみることにした。有名な「エラトステネスの篩」だ。コードを以下に示す。
「√n 以下の素数で割る」版、「篩」版、そして「シンプルに √n 以下の整数で割る」版を実行してみた結果は以下のようになった。
[imac] mnbi% rm primes.txt [imac] mnbi% time ./listprimes_binsearch.rb 100000 100 START (99991): 100003 (66) 100019 (66) 100043 (66) 100049 (66) 100057 (66) 100069 (66) Elapsed: 0.000275 ./listprimes_binsearch.rb 100000 100 17.60s user 0.02s system 100% cpu 17.601 total [imac] mnbi% time ./listprimes_sieve.rb 100000 100 100003 100019 100043 100049 100057 100069 Elapsed: 0.019148 ./listprimes_sieve.rb 100000 100 0.02s user 0.00s system 83% cpu 0.033 total [imac] mnbi% time ./listprimes_simple.rb 100000 100 100003 (158) 100019 (158) 100043 (158) 100049 (158) 100057 (158) 100069 (158) Elapsed: 0.00028 ./listprimes_simple.rb 100000 100 0.01s user 0.01s system 89% cpu 0.020 total
「篩」版は確かに速いが、「シンプル」版はさらに速い。
もっとも、これは表示させる領域を大きな数を基点として「狭めて」いるから起きることだ。1 から 100000 までの範囲の素数を列挙するなら「シンプル版」の方が遅くなる。
一番、速いのは
範囲(それも比較的大きな数から始まるものを)を指定して列挙させる場合、速いのは「√n 以下の整数で割る」方法をシンプルに実装したものだ。2 から始まる素数表を生成する方式では、範囲の上限に至るまでのすべての素数を生成する分不利になる。
たとえば、画面に一定範囲にふくまれる素数を表示する(だけの)アプリを作るとしたら、素数表を作る方式は適さないことになる。画面に表示できる範囲は限られているのだから、素数表を(作って)保持しておくより、見えている分だけをシンプルな方法(√n 以下の整数で割る)で判定する方がずっと素早く表示できるはずだ。
