或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

Rubyで素数判定の繰り返しを効率化してみた話

はじめに

とあるプログラミング問題に取り組んでる時、連続する数をそれぞれ素数か否かの判断を結構な回数繰り返す処理をRubyで書いていたのですが、もう少し処理速度が上がらんかなーと試行錯誤した結果、処理が効率化できたー。というお話です。

問題

実際の問題をそのまま紹介すると要点が分かりづらくなるので、今回は例題として以下の問題を考えます。

20,000,000以上21,000,000以下の素数がいくつあるか求めよ。

※あくまで説明の為のサンプル問題になります。

簡単な実装

RubyではPrimeクラスで素数かどうかの判定ができるので、以下のように実装すれば答えは出ます。

require "prime"
val = 20000000
cnt = 0
loop do
  cnt += 1 if Prime.prime?(val)
  val += 1
  break if val > 21000000
end
puts cnt#=>59336

効率化の検討

前述の実装で答えは出ますが、如何せん処理が重たく数十秒程度は掛かってしまいます。そこで、prime?メソッドを効率よく使うことが出来ないか調査してみることにしました。

prime?メソッドを調べてみる

https://docs.ruby-lang.org/ja/latest/class/Prime.html#I_PRIME--3F
ドキュメントに拠れば、prime?メソッドの仕様は以下の通り。

prime?(value, generator = Prime::Generator23.new) -> bool

第1引数のvalueのほかに、どうもgeneratorなるものがあります。そこで、Generator23クラスも調べてみます。

2と3と、3 より大きくて 2 でも 3 でも割り切れない全ての整数を生成します。

ある整数の素数性を疑似素数による試し割りでチェックする場合、このように低精度だが高速でメモリを消費しない疑似素数生成器が適しています。

https://docs.ruby-lang.org/ja/search/query:Prime::Generator23/#entry-0

どうやら、このクラスは疑似素数の配列を生成して、素数の判定に利用しているようです。
ちなみに、実行してみるとこんな感じの値の数列を作ってくれます。

gen = Prime::Generator23.new()
20.times do
  print "%d " % gen.next() 
end
#=>2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 
試行1:Generator23のインスタンスをループ外から渡してみる

じゃ、ループ外で1回インスタンス生成して使い回せば効率良くなるんじゃね?
というわけで、以下のようなコードにしてみました。

require "prime"
val = 20000000
cnt = 0
gen = Prime::Generator23.new
loop do
  cnt += 1 if Prime.prime?(val, gen)
  val += 1
  break if val > 21000000
end
puts cnt
#=>999998

が、これはダメ!
何故か素数判定が上手く行かず、ほとんどの数が素数として扱われてしまったようです。これは失敗例。

prime?の中身を覗いてみる

Eclipseのデバッガを使い、実際prime?メソッドが何してるか覗いてみる。

  def prime?(value, generator = Prime::Generator23.new)
    raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
    raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
    return false if value < 2
    generator.each do |num|
      q,r = value.divmod num
      return true if q < num
      return false if r == 0
    end
  end

このコードを覗いてみると、以下の事が分かります。

  • 引数generatorはeachメソッドを実装していることが必須。
  • generator.eachで得られる数を用いて素数判定をしている。
  • 判定処理で得られた商が除数より小さい時処理を打ち切っている。よってeachメソッドで得られる値が昇順であることが前提。

恐らく、試行1でやったgeneratorのインスタンスを1回だけ生成するやり方では、それぞれの数の素数判定をする際に内部で呼ばれるeachメソッドで得られる値が最初からではなくなるので正常な判定が出来なかったのでしょう。

試行2:素数配列を予めつくっておいて、prime?メソッドに渡す

eachメソッドを実装してれば良いらしいので、素数の配列作っておいて渡せばイケるんじゃね?
ということで以下のコードを書いてみました。なお、素数の配列は判定する値の最大値の平方根までの値があれば十分です。

require "prime"
val = 20000000
cnt = 0
prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
loop do
  cnt += 1 if Prime.prime?(val, prime_array)
  val += 1
  break if val > 21000000
end
puts cnt#=>59336

今度は、正しく判定できた様です。しかも気持ち処理速度は大分改善されたようです。

試行3:素数配列を予めつくっておいて、判定処理も自作する

しかし、元々Generatorを受け取る前提で作成されたメソッドに、(動くとはいえ)自作の配列を突っ込むのは多少気が引けます。というか、Rubyがバージョンアップした場合にこのコードが正しく動くのかどうか怪しいものです。

ということで、もう素数判定のメソッドも自分で実装することにします。

require "prime"
def is_prime(num, p_array)
  p_array.each do |x|
    q, r = num.divmod(x)
    return false if r == 0
    return true  if q < x
  end
end

val = 20000000
cnt = 0
prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
loop do
  cnt += 1 if is_prime(val, prime_array)
  val += 1
  break if val > 21000000
end
puts cnt#=>59336

こちらも正しい結果が返ってきました。コードは少し長くなりましたが、標準のメソッドに本来想定してないものを渡してるかも?という気持ち悪さは解消できたと思います。

処理時間計測

今までの処理をベンチマークで計測してみます。

require "prime"
require 'benchmark'
def is_prime(num, p_array)
  p_array.each do |x|
    q, r = num.divmod(x)
    return false if r == 0
    return true  if q < x
  end
end

Benchmark.bm 10 do |x|
  #単純な実装版
  x.report "prime_1" do
    val = 20000000
    cnt = 0
    loop do
      cnt += 1 if Prime.prime?(val)
      val += 1
      break if val > 21000000
    end
    #puts cnt
  end
  #prime?に素数配列を渡す版
  x.report "prime_2" do
    val = 20000000
    cnt = 0
    prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
    loop do
      cnt += 1 if Prime.prime?(val, prime_array)
      val += 1
      break if val > 21000000
    end
    #puts cnt
  end
  #判定処理自作版
  x.report "prime_3" do
    val = 20000000
    cnt = 0
    prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
    loop do
      cnt += 1 if is_prime(val, prime_array)
      val += 1
      break if val > 21000000
    end
    #puts cnt
  end
end

結果

                 user     system      total        real
prime_1     25.912000   0.000000  25.912000 ( 25.980192)
prime_2      7.238000   0.000000   7.238000 (  7.253440)
prime_3      6.911000   0.000000   6.911000 (  6.908018)

単純な実装版より、判定処理の自作版の方が3倍以上の効率で処理できました。

まとめ

今回は、標準のメソッドを使わずに自作で判定処理を実装することで処理効率を劇的に上げることが出来ました。

だだ、今回のケースでは以下のような前提条件が揃っているので自作の判定処理の効率の良さが出たと思います。

  • 判定する数の最大値が予め予測できる事
  • 繰り返しの数が多いこと
  • 判定する素数の値自体が大きい数でること

判定する数の最大値が高々1,000程度だったり、判定する回数が数十回程度のケースではわざわざ処理を自作して効率を求めるよりは、コードの可読性という観点からすると標準のメソッドを素直に利用したほうが良いのかもしれません。

というわけで、今回は処理効率を上げる為にはこんな方法もありますよーというお話でした。