こんばんは、すずしんです。
以前、「Java フィボナッチ数列を求めるプログラムを書いてみた」という記事をきっかけにして、フィボナッチ数列の要素を求めるプログラムを作成してみました。
そして、「Java フィボナッチ数列を求めるプログラムを高速化してみた」という記事では、HashMapを使うことで高速にフィボナッチ数列の計算を行えるようにしました。
この度、フィボナッチ数列の要素を求めるにあたって、「動的計画法」（Dynamic Programming）と呼ばれる方法でプログラムを新たに作成して動作チェックしてみました。
すると、実装がシンプルなのにも関わらず、非常に高速に要素の値を求めることができることが分かりました。
今回の記事では、その動的計画法で作成したプログラムについて紹介したいと思います。
フィボナッチ数列とは？
フィボナッチ数列というのは、「前の2つの数を加えると次の数になる」数列のことを言います。
ただし、初項と第2項の値は1となっています。
例えば、第3項の値は初項と第2項の数の和になりますので2です。
第4項の値は第2項と第3項の数の和で3です。
これを繰り返していくと以下のような並びになります。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
ここで、フィボナッチ数列の第n項の値を求める関数をfib(n)とします。
フィボナッチ数列の条件を式で表すと以下のような感じになりますね。
fib(1) = 1 fib(2) = 1 fib(n) = fib(n-2) + fib(n-1) (n >= 3)
以前のプログラムの問題点
以前の記事で作成したサンプルプログラムFibTestを再掲します。
ソースコードは以下のとおりです。
FibTestのfibメソッドは、まさにフィボナッチ数列の定義通りに実装したものです。
これでも一応正しく動作はしますが…。
引数のnが大きくなるほど内部での再帰呼び出しの回数が爆発的に増えてしまい、結果として計算時間が大幅にかかってしまいます。
package jp.suzushin7;
public class FibTest {
public static void main(String[] args) {
Timer timer = new Timer(Timer.MILLISECOND);
long value;
for(int i = 10; i <= 50; i += 10) {
timer.start();
value = fib(i);
timer.stop();
System.out.printf("fib(%d) = %d : %.3f ms%n", i, value, timer.getTime());
}
}
public static long fib(int n) {
if(n == 1 || n == 2) return 1;
return fib(n-2) + fib(n-1);
}
}
実行結果
今回作成するサンプルプログラムと比較するために、前回のサンプルプログラムFibTestの実行結果を載せておきます。
明らかに実行時間が増えていくのが分かりますね。
FibTestのような単純な実装では問題があるというのが見て取れます。
fib(10) = 55 : 0.017 ms fib(20) = 6765 : 0.922 ms fib(30) = 832040 : 8.660 ms fib(40) = 102334155 : 808.037 ms fib(50) = 12586269025 : 115598.251 ms
動的計画法による高速化
動的計画法とは、Wikipediaによると「対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。」とあります。
この動的計画法で問題を解く方法としては2種類あります。
1つは、計算履歴を記録（メモ化）してその結果を再利用しながら解く「トップダウン方式」です。
もう1つは、先に部分問題を解いていく「ボトムアップ方式」です。
「Java フィボナッチ数列を求めるプログラムを高速化してみた」で実装したHashMapを用いて問題を解く方法は、実は動的計画法で言うところのトップダウン方式になります。
一度計算した結果をHashMapに記録（メモ化）して再利用していますよね。
今回実装した方法は、動的計画法で言うところのボトムアップ方式になります。
フィボナッチ数列の問題で言えば、先に小さい方から順に値を求め、最終的にfib(n)を求めるということになります。
フィボナッチ数列の要素を求めるプログラム（高速版）
今回作成したサンプルプログラムFibTest3のソースコードは以下のとおりです。
以前のプログラムと同様にfib(10)、fib(20)、fib(30)、fib(40)、fib(50)の値を求め、その実行時間と併せてコンソールに結果を出力しています。
実行時間の計測には「Java 処理の実行時間を計測するプログラムを書いてみた」で作成したTimerクラスを使っています。
Timerクラスの詳細については上記記事を参照して下さい。
fibメソッドでは、まずnが1か2の場合1を返すという処理を行います。
それ以外、つまりnが3以上の場合は、forループで直前の2つの値n1、n2を記憶しながら、valueに順に足しあわせていきます。
ループを抜けた時のvalueが求める値ですので、その値valueを返します。
やっていることはたったこれだけです。
ねっ、簡単でしょ？
この方法は、人がフィボナッチ数列の要素を求める時の考え方と同じですよね。
package jp.suzushin7;
public class FibTest3 {
public static void main(String[] args) {
Timer timer = new Timer(Timer.MILLISECOND);
long value;
for(int i = 10; i <= 50; i += 10) {
timer.start();
value = fib(i);
timer.stop();
System.out.printf("fib(%d) = %d : %.3f ms%n", i, value, timer.getTime());
}
}
public static long fib(int n) {
if(n == 1 || n == 2) return 1;
long value = 0, n1 = 1, n2 = 1;
for(int i = 3; i <= n; i++) {
value = n1 + n2;
n1 = n2;
n2 = value;
}
return value;
}
}
実行結果
このサンプルプログラムFibTest3を実行してみた結果は以下のとおりです。
非常に高速にフィボナッチ数列の要素を求められているのがお分かりになると思います。
これは自分でも予想していた以上に速かったですね～。
fib(10) = 55 : 0.009 ms fib(20) = 6765 : 0.003 ms fib(30) = 832040 : 0.003 ms fib(40) = 102334155 : 0.003 ms fib(50) = 12586269025 : 0.003 ms
まとめ
今回の記事では、動的計画法のボトムアップ方式で、フィボナッチ数列の要素を求めるプログラムを作成して動作を確認しました。
その結果として、非常に高速に値を求められることが分かりました。
フィボナッチ数列のように、通常の方法では解くのに時間がかかってしまう問題でも…。
動的計画法を用いて、部分問題に分割し、その計算結果を利用しながら解くと高速に解けることがあります。
今回作成したサンプルプログラムで、そのポテンシャルの高さを直に実感しました。
動的計画法の力は本当に凄いですね！
プログラムの実装次第で、プログラムの実行速度は速くも遅くもなります。
どうせプログラムを作るなら、できるだけ速くプログラムを動作するようにしたいですよね？
そのために、例えば動的計画法のようなアルゴリズムに関する知識を持っていたほうが有利です。
私ももっと効率良く問題を解けるようにアルゴリズムの勉強をしてみようかな…。
あなたもアルゴリズムに関心を持って勉強してみてはいかがでしょうか？
プログラミングの学習が今までよりもっと楽しくなるかもしれませんよっ！？
[参考]
・Java フィボナッチ数列を求めるプログラムを書いてみた おすすめ！
・Java フィボナッチ数列を求めるプログラムを高速化してみた おすすめ！
・Java 処理の実行時間を計測するプログラムを書いてみた