メモを用いたプログラムの高速化

メモを用いることで、プログラムの実行を高速化することができる。メモというのは、その名の通り計算の途中経過を残しておくことである。一般に、プログラム実行時のメモリ消費量と実行スピードはトレードオフの関係にあると言われている。そのことをJavaでメモを利用する場合としない場合のそれぞれに分け、フィボナッチ数列を計算させることで確認した。

フィボナッチ数列は、a(1)=1、a(2)=1、a(n) = a(n-1)+a(n-2) (ただしn>=3)という関係を持った数列である。a(n)を計算する際に、過去に計算したa(n-1)、a(n-2)をメモとして残しておけば、オーバーフローするまでは高速に計算することが可能である。計算のオーダーはO(n)(n番目を計算するのにnに比例するという意味)になる。一方、再帰的に計算しようとすると、O(2^n)になる。これは、a(1)がおよそ2^n回に比例して現れることに由来する。オーダー表記では定数倍は考慮しないため、O(10*n)のような表記はしない。

public class fib_test{
 static int MAX_SIZE = 30; // 数列で何項目まで計算するか
 static int memo[] = new int [MAX_SIZE];

 private static int fib_memo(int n){
  if( n<0 ) return n;
  if( memo[n] != 0 ) return memo[n]; // メモの有無は値が0かそうでないかで判断
  memo[n] = fib_memo(n-1) + fib_memo(n-2);
  return memo[n];
 }

 private static int fib_recursive(int n){ // 再帰による計算
  if( n<=1 ) return 1;
  return fib_recursive(n-1) + fib_recursive(n-2);
 }

 public static void main(String args[]){
  memo[0] = 1;
  memo[1] = 1;

  // メモ利用時
  long start = System.currentTimeMillis();
  for( int i=0 ; i<MAX_SIZE ; i++){
   System.out.println("fib_memo[" + (i+1) + "] = " + fib_memo(i));
  }
  long end = System.currentTimeMillis();
  System.out.println("実行にかかった時間は " + (end - start) + " ミリ秒です。");

  // 再帰利用時
  start = System.currentTimeMillis();
  for( int i=0 ; i<MAX_SIZE ; i++){
   System.out.println("fib_recursive[" + (i+1) + "] = " + fib_recursive(i));
  }
  end = System.currentTimeMillis();
  System.out.println("実行にかかった時間は " + (end - start) + " ミリ秒です。");

 }
}

実行時間を比較すると、私の実行環境(Eclipse3.6、Core2Quad 3GHz、メモリ4GB)でも、明らかに差があった。上のプログラムを実行させてみると、メモを用いた場合は、実行にかかった時間が0ミリ秒となったのに対し、再帰で解いた場合は、実行時間は平均して15ミリ秒となった。

実行時間の計測にはSystem.currentTimeMillis()メソッドを用いた。実行の前後にメソッドを入れて時刻の差分をとり、差分を実行時刻とみなしている。