前回の続き。
素数表の検索にバイナリサーチを使う
前回、素数の判定法としてはもっとも素直な「√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 以下の整数で割る」ものよりも速くなった。とはいえ、やはり素数表を生成しながらの場合は、比較にならないほど遅い。
エラトステネスの篩
素数表の生成でもう少し速そうな方法を試してみることにした。有名な「エラトステネスの篩」だ。コードを以下に示す。
| #!/opt/local/bin/ruby1.9 -w | |
| # -*- coding: utf-8 -*- | |
| # listprimes_sieve.rb: make a list of prime numbers using the sieve of Eratosthenes | |
| start = ARGV.shift.to_i | |
| start = 2 if start < 2 | |
| range = ARGV.shift.to_i | |
| def sieve(start, range) | |
| limit = start + range | |
| max = Math::sqrt(limit).to_i | |
| s = Array.new(limit, true) | |
| s[0] = s[1] = false | |
| i = step = 2 | |
| while i <= max | |
| j = i + step | |
| while j < limit | |
| s[j] = false | |
| j += step | |
| end | |
| i += 1 | |
| until s[i] or i > max | |
| i += 1 | |
| end | |
| step = i | |
| end | |
| primes = [] | |
| (start...limit).each do |n| | |
| primes.push(n) if s[n] | |
| end | |
| return primes | |
| end | |
| t0 = Time.now | |
| sieve(start, range).each do |p| | |
| print "#{p}\n" | |
| end | |
| elapsed = Time.now - t0 | |
| print "Elapsed: #{elapsed}\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 から始まる素数表を生成する方式では、範囲の上限に至るまでのすべての素数を生成する分不利になる。
| #!/opt/local/bin/ruby1.9 -w | |
| # -*- coding: utf-8 -*- | |
| # listprime.rb: make a list of prime numbers. | |
| require 'prime' | |
| def die(*x) | |
| STDERR.puts x | |
| exit 1 | |
| end | |
| if ARGV.length < 2 | |
| die <<USAGE | |
| Usage: #{__FILE__} <start> <range> | |
| print prime numbers (start <= primes < start + range) | |
| USAGE | |
| end | |
| start = ARGV.shift.to_i | |
| range = ARGV.shift.to_i | |
| def prime(n) | |
| return [false, 1] if n.even? | |
| c = 1 | |
| d = 3 | |
| limit = Math::sqrt(n) | |
| while d <= limit | |
| return [false, c] if (n % d == 0) | |
| c += 1 | |
| d += 2 | |
| end | |
| [true, c] | |
| end | |
| t0 = Time.now | |
| (start...(start + range)).each do |n| | |
| result = prime(n) | |
| print "#{n} (#{result[1]})\n" if result[0] | |
| end | |
| elapsed = Time.now - t0 | |
| print "Elapsed: #{elapsed}\n" |
たとえば、画面に一定範囲にふくまれる素数を表示する(だけの)アプリを作るとしたら、素数表を作る方式は適さないことになる。画面に表示できる範囲は限られているのだから、素数表を(作って)保持しておくより、見えている分だけをシンプルな方法(√n 以下の整数で割る)で判定する方がずっと素早く表示できるはずだ。
