ブログ開始から2ヶ月経過しました
どうも、パイソンです。
今日でブログ開始からちょうど2ヶ月目。先月に引き続きこれまでの振り返りをします。
5月の目標
5月も目標なるものを立てておりました。
- rubyでなんか作る
- 記事更新は10記事程度を目処に
それぞれどんな感じだったか振り返ります。
次月に向けて
1ヶ月は長いようで、気が付けばあっという間に過ぎ去ってしまうもの。次月以降は計画的に更新していけるように頑張ります。
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
試行１：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メソッドで得られる値が昇順であることが前提。
恐らく、試行１でやったgeneratorのインスタンスを1回だけ生成するやり方では、それぞれの数の素数判定をする際に内部で呼ばれるeachメソッドで得られる値が最初からではなくなるので正常な判定が出来なかったのでしょう。
試行２：素数配列を予めつくっておいて、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
今度は、正しく判定できた様です。しかも気持ち処理速度は大分改善されたようです。
試行３：素数配列を予めつくっておいて、判定処理も自作する
しかし、元々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程度だったり、判定する回数が数十回程度のケースではわざわざ処理を自作して効率を求めるよりは、コードの可読性という観点からすると標準のメソッドを素直に利用したほうが良いのかもしれません。
というわけで、今回は処理効率を上げる為にはこんな方法もありますよーというお話でした。
Rubyで素因数分解を行う
素因数分解をC言語やJavaで行う場合、自力で小さい素数から順に割っていく方法なんかが取られるかと思いますが、Rubyでは標準モジュールに素因数分解の処理が用意されていたのでメモ。
Primeクラスのprime_divisionメソッド
Rubyでは、このメソッド一発で素因数分解が出来ます。Ruby便利すぎる。。
使い方
require "prime" p Prime.prime_division(360)#=>[[2, 3], [3, 2], [5, 1]] p Prime.prime_division(1683)#=>[[3, 2], [11, 1], [17, 1]] p Prime.prime_division(65536)#=>[[2, 16]] p Prime.prime_division(8635844967113809)#=>[[89652331, 1], [96325939, 1]]
prime_divisionメソッドは2次元配列で結果を返してきます。
例として360を素因数分解すると、
となります。戻り値は各素因数とそのベキ指数の2要素の配列の配列ということですね。
因みに、prime_divisionメソッドにかなり大きい数の素数を引数に与えると結構処理時間が掛かります。
最大公約数、最小公倍数の求め方/ユーグリットの互除法
今回もアルゴリズムに関して学んだ知識のメモ。ユーグリットの互除法について調べてみました。
ユーグリットの互除法とは
最大公約数を求める手法です。
ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。
https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95
高校数学なんかでも学ぶ内容ですし、かなり有名なアルゴリズムですね。
ユーグリットの互除法のアルゴリズム
割り算で求めるやり方と引き算で求めるやり方があります。
以下、それぞれのやり方での整数aとb(a >= b)の最大公約数の求め方を記載します。
割り算バージョン
- aをbで割った余りを求める。
- 余りが0の場合、bが最大公約数。
- 余りが0以外の場合、除数(割った数)を先程の余りで割りその余りを求める。
- これを余りが0になるまで繰り返す。余りが0になった時の除数が最大公約数
引き算バージョン
- aをbで引いた差を求める。
- 差が0の場合、bが最大公約数。
- 差が0以外の場合、引いた数と差の大きい方から小さい方を引いた差を求める。
- これを差が0になるまで繰り返す。差が0になった時の減数(引いた数)が最大公約数
計算量としては割り算で求めるやり方のほうが少ないかと思われます。
最小公倍数の求め方
最大公約数が求めることができれば、最小公倍数は以下の式で求める事が出来ます。
A,Bの最小公倍数＝A×B÷A,Bの最大公約数
実装
というわけで、今回もRubyで実装してみます。
#割り算バージョン def gcd(a, b) a, b = b, a if a < b loop do m = a % b return b if m == 0 a, b = b, m end end #引き算バージョン def gcd2(a, b) loop do a, b = b, a if a < b d = a - b return b if d == 0 a, b = b, d end end #最小公倍数 def lcm(a, b) return ((a * b) / gcd(a, b)) end puts gcd(1071, 1029)#=>21 puts gcd2(1071, 1029)#=>21 puts lcm(1071, 1029)#=>52479
おまけ
ま、Rubyの場合は標準でメソッドが用意されているんですけどねー。
puts 1071.gcd(1029)#=>21 puts 1071.lcm(1029)#=>52479
解法の中身を理解する事も重要だと思います。
エラトステネスのふるいを実装してみる
アルゴリズムに関する知識も自分の中にストックしておきたいということで、今回は「エラトステネスのふるい」について調査したものをメモ。
エラトステネスのふるいとは
素数の一覧を簡易的に求める手法です。
エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
手法としては極めて簡潔で、2以上の整数のリストから先ず2の倍数を削除し、次に3の倍数をリストから削除、次に5の倍数を削除という具合に小さい素数から順にその合成数を削除するというやり方です。
アルゴリズム
或る整数nまでの素数を求める場合
- 2からnまでの整数を列挙した探索リストを作成する。
- 配列の先頭の数を素数リストに移動し、その数の倍数を配列から篩い落とす。
- 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
- 探索リストに残った数を素数リストに移動して処理終了。
以上の要領で処理を行います。
実装
Rubyで実装をしてみました。2からMAX_NUMまでの素数リストを作成、出力するプログラムです。
MAX_NUM = 120 array = (2..MAX_NUM).to_a x = 2 s = Math::sqrt(MAX_NUM) loop do pn = array.find{|num| num >= x } array.delete_if{|num| num != pn && num % pn == 0 } break if x >= s x += 1 end p array
実行結果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
Rubyのinject/reduceメソッドに関するメモ
つい最近までRubyのinjectやらreduceが何してるか分からんかったので調査したことをメモ。
inject/reduceメソッド
injectメソッドは、ブロックを使って繰り返し計算を行うのに使います。ブロックに順に「要素1、要素2」、「ブロックの前回の戻り値、要素3」、「ブロックの前回の戻り値、要素4」、...を渡します。メソッドの戻り値はブロックが最後に返した値になります。
http://ref.xaio.jp/ruby/classes/enumerable/inject
イメージとしては、ハッシュや配列(要はEnumerableオブジェクト)の各要素に対して繰り返し処理を行い一つに纏めた結果を返す処理に使うものかなーという感じです。
因みにreduceは、injectメソッドの別名となります。mapとcollectの関係みたいなものですね。
使い方いろいろ
injectメソッドの使用例として、配列の合計を求める方法が良く使われます。
以下、サンプルとしていろんな書き方を試してみました。
array = (1..20).to_a p array.inject {|sum, n| sum + n }#=>210 p array.inject(0){|sum, n| sum + n }#=>210 p array.inject(0,:+)#=>210 p array.inject(:+)#=>210 #100を初期値にしてみる p array.inject(100,:+)#=>310
injectの書き方にもブロックで要素を処理する方法や、初期値を指定または省略する方法、またメソッドの引数でシンボルを渡して処理する方法があります。
また、配列の合計を計算する以外の使い方もあります。
次の例では初期値を空のハッシュで定義し、レシーバの配列から条件に合致する値のみを追加したハッシュを返す処理を行っています。初期値を配列にすれば、結果を配列で返すことも可能です。
array = (1..10).to_a.reduce({}) do |arr, item | arr << item if item % 2 == 0 arr end p array #=>{2=>true, 4=>true, 6=>true, 8=>true, 10=>true}
工夫次第で、配列周りの処理を簡潔に記述できそうですね。
参考URL
reduceやinjectという名称と処理のイメージが中々結び付かなかったのですが、以下のURLの記事の説明がなかなか分かりやすかったです。
Rubyist Magazine - map と collect、reduce と inject ―― 名前の違いに見る発想の違い
Rubyで多重ループを抜ける方法
Rubyの大域脱出に関するメモ。
ネストが深いループから何かの条件で一気に抜けたい場合、Rubyではcatch-throwを使うのが適切なようです。
書き方
以下が大域脱出のサンプル。如何にもサンプルの為のサンプルという感じですが、ネストしたループから抜けているのがお分かりいただけるかと。
catch(:break_loop) do (1..5).each do |x| (1..5).each do |y| puts "x=%d, y=%d" % [x,y] throw :break_loop if x * y > 10 end end end
実行結果
x=1, y=1 x=1, y=2 x=1, y=3 x=1, y=4 x=1, y=5 x=2, y=1 x=2, y=2 x=2, y=3 x=2, y=4 x=2, y=5 x=3, y=1 x=3, y=2 x=3, y=3 x=3, y=4
JavaやC++に慣れた人だと、catch節には例外処理を書くものだというイメージがあったりするのですが、Rubyの場合はその辺は切り離して考えたほうが良さそうです。
オブジェクトを返すこともできます
catch内部に定義した変数を返却する事も可能。こういう書き方を覚えておくと何かの時に役に立つのかもしれません。
(a,b,c) = catch(:break_loop) do (1..20).each do |x| (1..20).each do |y| (1..20).each do |z| throw(:break_loop, [x,y,z]) if x * y * z > 1000 end end end end puts "a=%d, b=%d, c=%d" % [a,b,c]#=>a=3, b=17, c=20
雑感
RubyはGOTO文がありませんので、上の例以外に一気にネストを抜ける為には例外をraiseするか、メソッドに分割してreturnする方法ぐらいしかありませんね。
