今まで、Project Eulerの問題で素数を扱うときは、Prime.eachを多用してきたのですが、40000000までの素数を扱う問題で、これを列挙するだけでも、かなり時間を要することに気づきました。
そこで、定番のエラトステネスの篩を作って、Prime.eachと速度比較してみました。
prime_list.rb
- my_prime_listは、自作
- prime_listは、「エラトステネスの篩 #Ruby - Qiita」で紹介されていたものです。
- use_prime_libは、Prime.eachを用いたもの
# -*- coding: utf-8 -*- require 'prime' require 'benchmark' def my_prime_list(n) arr = Array.new(n).fill(1) arr[0] = arr[1] = 0 limit = Math.sqrt(n).to_i for i in 2..limit if arr[i] == 1 2.upto(Float::INFINITY) {|j| if i * j < n arr[i * j] = 0 else break end } end end prime_list = [] arr.each_with_index {|e, i| prime_list << i if arr[i] == 1 } prime_list end def prime_list(n) return [] if n < 2 return [2] if n == 2 limit = (n ** 0.5).to_i arr = (1 .. n).step(2).to_a arr[0] = 2 len = arr.size i = 0 while true i = i + 1 j = arr[i] next unless j break if j > limit k = 2 * i * (i + 1) while k < len arr[k] = nil k = k + j end end arr.compact! return arr end def use_prime_lib(n) prime_list = [] Prime.each {|pr| break if pr > n prime_list << pr } prime_list end MAX = 40_000_000 Benchmark.bm(15) do |x| x.report("My Eratosthenes") { p my_prime_list(MAX).size } x.report("Eratosthenes") { p prime_list(MAX).size } x.report("Prime.each") { p use_prime_lib(MAX).size } end
実行結果
Prime.eachを用いる方法は10分以上かかっているのに対して、2番目のprime_list関数を用いる方法では7秒程度で実行できています。これほど実行速度に差があるとは思いませんでした。
$ ruby prime_list.rb user system total real My Eratosthenes 2433654 57.880000 0.340000 58.220000 ( 58.523879) Eratosthenes 2433654 7.380000 0.150000 7.530000 ( 7.586200) Prime.each 2433654 686.610000 1.910000 688.520000 (708.199233)