«
»

倍数判別ロジックの高速化

2010 年 6 月 14 日 by 山平

前回、3と7と11の倍数かどうかを判別するプログラムを作成しました。
最初から分かっていたことではありますが、単純に剰余を求めるよりも計算に時間がかかってしまうのです。
人間が計算する場合は、桁数が多いと計算が大変だったり計算ミスが発生してしまったりするので、倍数判別を行なったほうがミスが減ることが期待できます。
しかし、コンピュータに計算させる場合、各桁を足したり引いたりする行為のコストが大きいため、単純な剰余の方が効率が良いのです。

今回は、前回のプログラムをもうちょっと早くできないか試行錯誤してみました。

計算時間を測定する

まずはそれぞれの計算にかかる時間を計測するプログラムを作成します。

def calctime(times)
start = Time.now
times.times do |t|
yield t
end
finish = Time.now
finish - start
end

受け取ったブロックを指定回数実行して、それにかかった秒数を返します。

maxcount = 100000
p calctime(maxcount){|n| by3d(n) }
p calctime(maxcount){|n| by3p(n) }
p calctime(maxcount){|n| by7d(n) }
p calctime(maxcount){|n| by7p(n) }
p calctime(maxcount){|n| by11d(n)}
p calctime(maxcount){|n| by11p(n)}

数回流して時間を計ってみましたが、単純剰余はどれも0.2秒以下、倍数判別はどれも20秒以上かかっています。
なんと100倍以上の差が出てしまっています。
恐らく各桁の計算を行なう際に、安易に文字列操作を繰り返しているのが原因ではないかと思われますので、その辺を中心に改善していきます。

倍数判別を高速化

3の倍数判別は各桁の和を求めれば良いのでした。
しかしrubyにはphpのarray_sumのようなメソッドがないので、injectメソッドを使います。

def by3pkai(n)
while n > 9 do
n = n.to_s.split(//).inject(0){|t, v| t+=v.to_i }
end
(n % 3 == 0)
end

to_sが残りましたが、数値-文字列変換の操作が1ループ内で4回から2回へと減りました。

7の倍数判別では1桁目と2桁目以上を分ける必要があるため、文字列操作を減らすためにちょっと苦しい(スマートでない)処理を書く必要があります。

def by7pkai(n)
while n > 9 do
upper = (n / 10).to_i
lower = n - upper * 10
n = upper - (2 * lower)
end
(n % 7 == 0)
end

ひとまず文字列変換がなくなったので、早くなっていることを期待します。

11の倍数判別もinjectで実装できました。

def by11pkai(n)
while n > 9 do
n = (n.to_s.split(//).inject(0){|t, v|
t += v.to_i
t *= -1
}).abs
end
(n == 0)
end

前回作成した11の倍数判別ではふんだんに文字列操作を行なっていましたが、１ループ内2回に抑えました。

計算時間の計測

各メソッドを1から10万までの値を計算するのにかかった時間を3回計測して平均を取ってみました。
結果は以下の通り。

3の倍数

  • 単純剰余：0.14秒
  • 倍数判定(改善前)：26秒(剰余の約185倍)
  • 倍数判定(改善後)：14秒(剰余の約100倍、改善前の約54%)

7の倍数

  • 単純剰余：0.18秒
  • 倍数判定(改善前)：29秒(剰余の約166倍)
  • 倍数判定(改善後)：0.6秒(剰余の約3.4倍、改善前の約2%)

11の倍数

  • 単純剰余：0.14秒
  • 倍数判定(改善前)：22秒(剰余の約160倍)
  • 倍数判定(改善後)：9.2秒(剰余の約68倍、改善前の約57%)

文字列操作を完全に排除できた7の倍数判別の改善率が光っていますが、単純剰余には全く歯が立ちませんでした。

結論

今回の計測結果から、少々の小細工では単純な剰余を越えるパフォーマンスを出すことは難しいという事実が再確認されました。
逆に考えると、無理な効率化よりも単純な記述、意味を伝えるコードを心がけたので良い、と言えなくもないようです。

高級言語は高級たれ、という結論で終わります。

以上です。

TrackBack