すずろぐ

人生大逆転を目指す、鈴木俊吾の成長日記

Java フィボナッチ数列を求めるプログラムを高速化してみた

プログラミング

こんにちは、すずしんです。

前回の記事「Java フィボナッチ数列を求めるプログラムを書いてみた」では、フィボナッチ数列要素を求めるプログラムを作成してみました。 しかし、要素の計算に時間があまりにもかかり過ぎてしまうという問題がありました。

そこで、私はちょっとアルゴリズムを工夫しまして…。 高速フィボナッチ数列の要素を求められるようにしてみました。 今回の記事では、その方法について書いていきたいと思います。

フィボナッチ数列とは?

フィボナッチ数列というのは、「前の2つの数を加えると次の数になる」数列のことを言います。 ただし、初項と第2項の値は1となっています。

例えば、第3項の値は初項と第2項の数の和になりますので2です。 第4項の値は第2項と第3項の数の和で3です。 これを繰り返していくと以下のような並びになります。

[text] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … [/text]

ここで、フィボナッチ数列の第n項の値を求める関数をfib(n)とします。 フィボナッチ数列の条件を式で表すと以下のような感じになりますね。

[text] fib(1) = 1 fib(2) = 1 fib(n) = fib(n-2) + fib(n-1) (n >= 3) [/text]

前回のプログラムの問題点

前回の記事で作成したサンプルプログラムFibTestを再掲します。 ソースコードは以下のとおりです。

FibTestのfibメソッドは、まさにフィボナッチ数列の定義通りに実装したものです。 これでも一応正しく動作はしますが…。 引数のnが大きくなるほど内部での再帰呼び出しの回数が爆発的に増えてしまい、結果として計算時間が大幅にかかってしまいます。

[java] 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);
}

} [/java]

実行結果

今回作成するサンプルプログラムと比較するために、前回のサンプルプログラムFibTestの実行結果を載せておきます。 明らかに実行時間が増えていくのが分かりますね。 FibTestのような単純な実装では問題があるというのが見て取れます。

[text] 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 [/text]

改善策: HashMapを使って高速化!

今回、私がどのようにして高速化したのかと言いますと…。 HashMapを使って前回に求めた計算結果を保存して再利用するという方法を取りました。

HashMapというのは、keyとvalueをペアとした情報を保持することができるクラスです。 情報は(key, value)をセットにして、putメソッドでHashMapに登録します。 そして、getメソッドでkeyを検索することで、そのkeyに対応したvalueを取得することができます。

[java] HashMap<K, V> map = new HashMap<>(); // HashMapの作成 map.put(key, value); // データの登録 V value = map.get(key); // データの取得 [/java]

HashMapには、今計算しているのが何項目かという情報と、その時の計算結果の値、の2つを保持します。 つまり、HashMapのkeyがfibメソッドの引数であるn、valueがfib(n)の値、ということになります。 fibメソッド内で再帰呼び出しをする際に、もし前回までに計算した結果がHashMapに登録されていた場合、その値を直接返すことで再び同じ計算をする手間を省きます。 これによって計算量が大幅に減り実行時間が短縮されます。

フィボナッチ数列の要素を求めるプログラム(高速版)

今回作成したサンプルプログラムFibTest2のソースコードは以下のとおりです。 こちらは前述したHashMapを使って計算量を減らして高速化したバージョンになります。 前回と同じく、fib(10)、fib(20)、fib(30)、fib(40)、fib(50)の値を求め、その結果と実行時間と併せてコンソールに出力するプログラムとなっています。 実行時間の計測には、「Java 処理の実行時間を計測するプログラムを書いてみた」で作成したTimerクラスを使っています。

FibTest2では、HashMapとしてmapを保持しています。 fibメソッド内では、まずnが1か2の場合の処理を行った後、mapにfib(n)の計算結果が登録されているかどうかを検索します。 もしmapから見つかった場合には、その値をそのまま返します。 未登録の場合は、fib(n)の値を計算して、その結果をmapに登録してから返しています。

ちなみに、mainメソッド内のforループの中でmap.clear()を呼び出していますが…。 複数回fibメソッドを呼び出している関係上、前回までのmapの情報が参照されてしまうのを防ぐために使っています。 今回はfib(n)を単独のみで実行した場合と同じ状況での実行時間を知りたいのでこのようにしています。

[java] package jp.suzushin7;

import java.util.HashMap;

public class FibTest2 { private static final HashMap<Integer, Long> map = new HashMap<>();

public static void main(String[] args) {
    Timer timer = new Timer(Timer.MILLISECOND);
    long value;
    for(int i = 10; i &lt;= 50; i += 10) {
        timer.start();
        value = fib(i);
        timer.stop();
        System.out.printf(&quot;fib(%d) = %d : %.3f ms%n&quot;, i, value, timer.getTime());
        map.clear();
    }
}

public static long fib(int n) {
    if(n == 1 || n == 2) return 1;
    if(map.containsKey(n)) return map.get(n);

    long value = fib(n-2) + fib(n-1);
    map.put(n, value);

    return value;
}

} [/java]

実行結果

このサンプルプログラムFibTest2を実行してみた結果は以下のとおりです。 いかかでしょう? 計算結果は正しい値のままで、計算時間が大幅に軽減されているのが分かります。 fib(50)の計算にしても、なんと1ミリ秒もかかっていません!? まさにHashMapの力恐るべしですね。

[text] fib(10) = 55 : 0.754 ms fib(20) = 6765 : 0.064 ms fib(30) = 832040 : 0.071 ms fib(40) = 102334155 : 0.085 ms fib(50) = 12586269025 : 0.145 ms [/text]

まとめ

今回の記事では、フィボナッチ数列の要素を求める処理を、HashMapを使って再計算の手間を省くことで高速化したプログラムを作成してみました。 前回のプログラムと比較してみると、圧倒的に計算が早くなっているのがお分かりですね。 ちょっとした工夫で結果が大きく変わることがあるというのが、プログラミングをしていて面白い部分だったりします。

もしあなたもプログラミングをする際には…。 「もっと効率良く処理を行うことができないか?」ということを常に意識しながら、プログラムを実装してみてはいかがでしょうか? そうすれば、将来的にプログラミングスキルを向上させることに繋がると思いますよっ!

[関連] ・Java フィボナッチ数列を求めるプログラムを書いてみたJava 処理の実行時間を計測するプログラムを書いてみた