search
LoginSignup
3
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

Ruby その2 Advent Calendar 2020 Day 10

posted at

updated at

Ruby の prime が爆速化した件

Ruby の標準添付ライブラリーが次々と gem 化している。
gem 化すると,Ruby バージョンに縛られずにアップデートすることができる。

prime 0.1.2 リリース

さて,昨日(2020-12-09)Ruby の素数ライブラリー prime の新しい版(バージョン 0.1.2)がリリースされた。
何が変わったのだろうか?
prime のリポジトリー を見ても CHANGE.txt や HISTORY.txt の類は無いが,コミット一覧

Optimize Integer#prime?

というコミットメッセージを見つけた。
ん? もしや? コミットを覗くと,冒頭に MILLER_RABIN_BASES などという定数が定義されている。
やはりアレだ。ミラー–ラビン素数判定法 を使って素数判定を高速化したんだ。

ベンチマーク

素数判定プログラムのベンチマークテストはなかなか難しい。判定する数によって処理時間が大きく変わりうるから。
しかし,ここでは難しいことは考えず,昔作ったプログラムを一つだけ引っ張り出して,time コマンドで時間を測ってみた。

これはかつて以下の記事で提示したコードの一つ。
Ruby で百世紀までの素数日リスト - Qiita

百世紀までの素数日(解説は上の記事を参照)をテキストファイルに書き出すもの。
当然,大量の素数判定が行われる。

require "date"
gem "prime", "0.1.1"
require "prime"

def prime_dates(start_year, end_year)
  result = []
  days = [*1..31].reject{ |day| day.even? || day % 5 == 0 }
  start_year.upto(end_year) do |year|
    1.upto(12) do |month|
      days.each do |day|
        next unless Date.valid_date?(year, month, day)
        if (year * 10_000 + month * 100 + day).prime?
          result << "%04d-%02d-%02d" % [year, month, day]
        end
      end
    end
  end
  result
end

IO.write "prime_dates.txt",
  prime_dates(1, 10_000).join("\n") + "\n"

2 行目の

gem "prime", "0.1.1"

で prime gem のバージョンを 0.1.1 に固定している。
ここを 0.1.2 にしたものと両方で測ってみる。

0.1.1 0.1.2
19.4 sec 3.4 sec

うひょーっ! 5 倍速以上ですかい。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
3
Help us understand the problem. What are the problem?