メモ化で速度改善した話

Pocket
LINEで送る

こんにちは、有安です。

最近フクロウラボでコード書いていて、「1度計算した結果をメモしておく」ことで大幅に速度改善出来たことがありました。

メモ化はアルゴリズムの問題を解く際には大事な技術ですが、実際のウェブアプリ開発にもそのまま活かせることもあるということで、これは是非知らない人に伝えたい!となったわけです。なので知らない人向けです。

メモ化とは

メモ化Memoization)とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン(関数)の呼び出し毎の再計算を防ぐ手法

ということで、今回はフィボナッチ数列の問題を題材に、メモ化の威力を伝えたいと思います!

フィボナッチ数列とは

最初の二項が1で、第三項以降の項がすべて直前の二項の和になっている数列 すなわち、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…という数列のこと。

フィボナッチ数列のn番目の数の求め方を、メモ化を使う方法と使わない方法で比べてみましょう。

def fib(n)
  if n == 1 || n == 1
    1
  else
    return fib(n - 2) + fib(n - 1)
  end
end
puts fib(ARGV[0].to_i)

例えばコマンドライン引数として渡したn番目のフィボナッチ数を出力する関数は上のように書けます。

再帰を使って、愚直に計算しています。

これ実行してみると分かるんですが、かなり時間がかかります。

実際に測ってみましょう。

require 'benchmark'
def fib(n)
  if n == 1 || n == 2
    1
  else
    fib(n - 2) + fib(n - 1)
  end
end
result = Benchmark.realtime do
  puts fib(ARGV[0].to_i)
end
puts "処理に#{result}秒かかりました。"

例えばこんな感じのtest.rbというファイルを作って、terminal

$ ruby test.rb 40

などと実行してみます。

すると、僕の環境では

165580141

処理に12.800130449999415秒かかりました。

と出力されました。渡す数を45に変えると、

1134903170

処理に87.92296592901403秒かかりました。

50なら

12586269025

処理に980.8132537749916秒かかりました。

と、かかる時間が加速度的に増加していくのが分かるかと思います。ちなみに100番目だと、1時間経っても終わらず。

これはまずいということで、無駄な計算をしていないかアルゴリズムを確認してみましょう。

コードを読むと分かりますが、かなり単純なアルゴリズムです。

例えば10を渡した場合。

fib(10) fib(9) + fib(8) に変換されます。

fib(9) fib(8) はそれぞれ、

fib(9) -> fib(8) + fib(7)

fib(8) -> fib(7) + fib(6)

に変換されますね。

ということで、計算の重複があります。

fib(9)でもfib(8)でも、fib(7)を知りたがっています。これは是非メモ化して計算量を減らしたいところです。

実際にメモ化した書き方が以下になります。

require 'benchmark'
@memo = {}
def fib(n)
return @memo[n] if @memo.has_key?(n)
  if n == 2 || n == 1
    @memo[n] = 1
  else
    @memo[n] = fib(n - 2) + fib(n - 1)
  end
end
result = Benchmark.realtime do
  puts fib(ARGV[0].to_i)
end
puts "処理に#{result}秒かかりました。"

変わったのは少しだけですが、スピードはどう変わっているでしょうか?

100番目のフィボナッチ数を求めてみましょう。

354224848179261915075

処理に0.00012598700413946062秒かかりました。

なんと!ものすごい速いじゃない!また来月!

(処理の途中でもキャッシュを上手く使いたいね、という記事でした~)

Pocket
LINEで送る