Rubyで数値の各桁を計算で取得することは無駄な努力だった (と思ったらそうでもなかった)

まとめ (2015/04/28追記)

• 桁数はMath.log10を使って求める方法がダントツで速い
• 各桁を配列で取得するには「一旦to_sで文字列にする」「1桁ずつ計算で求める」の2種類の方法がある
• 桁数が膨大な場合はto_sしたほうが速いが、十分に小さい場合は計算で求めたほうが速い
• 計算方法にもよるので計算のほうが早くなる方法もあるかもしれない
• まぁそこまで速度に差はつかないのでどっちでもいいと思う

Integer#length、Integer#to_aとしてモンキーパッチにしてみる

class Integer

  # 桁数
  def length #sizeはバイト数だけどlengthは使われてなかったので
    # 0を渡すとエラーが出るので避ける
    self.zero? ? 1 : Math.log10(self.abs).to_i + 1 
  end

  # 各桁
  def to_a
    if Bignum === self # Bignumなら文字列にする方法で取得
      self.abs.to_s.each_byte.map{|b| b - 0x30}
    else # Fixnumなら計算で取得
      n = self.abs
      digits = []

      begin
        digits.unshift n % 10
        n /= 10
      end while n > 0

      digits
    end
  end
end

---

Rubyで遊んでると数値の桁を調べたくなることが稀によくあります。
で、真っ先に思いつくのが一旦文字列にする方法です。

文字列に変換して桁を調べる

# 数値の各桁の配列として得る
def get_digits(n)
  n.abs.to_s.each_byte.map{|b| b - 0x30}
  # n.abs.to_s.each_char.map &:to_iよりもちょっと速い (コメントありがとうございました！)
end

def count_digits(n)
  n.abs.to_s.size
end

実行例

get_digits 123456789
# => [1, 2, 3, 4, 5, 6, 7, 8, 9]

count_digits 123456789
# => 9

で

文字列にしたり戻したり無駄味ある
計算で出したほうが早いんだろうなー

とかいつも思ってました。

数値計算で桁を調べる

なので試しに文字列に変換しないメソッドも作ってみました。
(どの方法でも、負の値も扱えるようにabsすべき)

# 数値の各桁の配列として得る
def get_digits_alt(n)
  n = n.abs
  digits = []

  begin # 10の剰余を配列に入れ、nを10で割っていく
    digits.unshift n % 10
    n /= 10
  end while n > 0

  digits
end

# 桁数を数える
def count_digits_alt(n)
  n = n.abs

  1.upto Float::INFINITY do |i| # nが10未満になるまで10で割っていく
    break i if n < 10
    n /= 10
  end
end

ベンチマーク

で、意気揚々とベンチ取ったら明らかに文字列に変換したほうが速かったです。

bench.rb

require 'benchmark'

n = 100000000 ** 10000 # 8万桁の数値

Benchmark.bm(10) do |r|
  r.report("各桁 (str)"){ get_digits n }
  r.report("各桁 (num)"){ get_digits_alt n }

  r.report("桁数 (str)"){ count_digits n }
  r.report("桁数 (num)"){ count_digits_alt n }
end

結果

                 user     system      total        real
各桁 (str)     0.020000   0.000000   0.020000 (  0.021378)
各桁 (num)     8.100000   0.360000   8.460000 (  8.456943)
桁数 (str)     0.000000   0.000000   0.000000 (  0.001893)
桁数 (num)     4.220000   0.150000   4.370000 (  4.396235)

クソアルゴリズムすぎたんでしょうか？
たしかにちょっと考えれば、大きい数値を何度も計算していて明らかに非効率です。

でも、他に数値計算で効率のいい方法が思いつきません。
多少の書き方の違いはあるでしょうけど、劇的に早くなる方法はあるんでしょうか。
(あったら教えてほしいです。)

(追記: 大きな数値をそのまま計算せず、おおまかに桁を分けることで大幅に処理時間を短縮したメソッドを教えていただきました。コメント欄参照)

おとなしく一旦文字列にしたほうが実行速度もソースも短くなりそうでした。

追記 (Math.log10で桁数を数える)

桁数を数える方法については、コメントで教えていただいたlogを使う方法が爆速でした。

def count_digits(n)
  Math.log10(n.abs).to_i + 1
end

bench.rb

require 'benchmark'

n = 100000000 ** 100000 # 80万桁の数値を用意。(速すぎたので増やした)

Benchmark.bm(10) do |r|
  r.report("桁数 (str)"){ n.to_s.size } # 文字列に変換する方法
  r.report("桁数 (log)"){ Math.log10(n).to_i + 1 } # logを使う方法
  # 計算で出す方法は遅すぎるのでスルー
end

結果

                 user     system      total        real
桁数 (str)     1.220000   0.010000   1.230000 (  1.226869)
桁数 (log)     0.000000   0.000000   0.000000 (  0.000026)

各桁を得るほうはやっぱり文字列にしたほうが良さげ。

追追記 (桁数が少ないなら文字列に変換しないほうが速い)

各桁を得る方法について。
上では「8万桁の大きな数値を1回だけ変換」した時間を計測して、文字列に変換したほうが速いという結果が出ました。
ですが「10桁の数値を100万回変換」した場合は計算で得る方法の方が速かったです。

桁数が少ない場合は計算で得る方法のほうが速いので、適材適所な感じで使い分けるといいかもしれません。
(ベンチはコメント欄参照)