アルゴリズム
この章では、アルゴリズムによってプログラムの所要時間に雲泥の差が出ることを、フィボナッチ数の実例を使って紹介します。
再帰的アルゴリズム
アルゴリズムとはプログラムで問題を解く際の計算のさせ方をさす用語です。
前章ではフィボナッチ数列の第n項を求めるコードを紹介しました。
function fib(n) {
if (n == 1) return 1
if (n == 2) return 1
return fib(n-1) + fib(n-2)
}
これは関数の再帰的な呼び出しを使って問題を解いているので「再帰的なアルゴリズム」と呼ばれます。
計算量
単純な再帰を利用したフィボナッチ数の実装は美しいのですが、一つ重大な問題があります。
実行速度が異常に遅いことです。
私のパソコンではfib(40)で1秒ほど、fib(45)で10秒ほど計算に時間がかかりました。
関数fibが呼び出される回数について考えると、次のことが分かります。
- fib(1)の時:
1回 - fib(2)の時:
1回 - fib(n)の時:
fib(n-1)がfibを呼び出す回数+fib(n-2)がfibを呼び出す回数+1回（自分自身）
この定義だけじゃ実際の値が分からないのでプログラムを使って計算します。
function kaisuu(n) {
if (n == 1) return 1
if (n == 2) return 1
return kaisuu(n-1) + kaisuu(n-2) + 1
}
console.log(kaisuu(40)) // 204668309
console.log(kaisuu(45)) // 2269806339
ということでなんと、第40項を求めるときには2億回、第45項を求める時には22億回も関数fibが呼ばれていることが判明しました。
処理回数がどのように増えていってるかを観察すると
kaisuu(41) / kaisuu(40)
// 1.6180339917695807
kaisuu(42) / kaisuu(41)
// 1.6180339906161634
kaisuu(43) / kaisuu(42)
// 1.6180339899033123
ということなので「第n+1項を求める際には、第n項を求めるときの1.6倍の回数fibを呼んでいる」ことが分かります。 ざっくりいうと、このアルゴリズムでフィボナッチ数列の第n項の値を求めるには「1.6のn乗のオーダーの時間」がかかります。
このざっくりした見積もりは「計算量」と呼ばれるもので、アルゴリズムの性能を評価する際に頻繁に使われます。 実際の処理にかかる時間はマシンの性能やプログラミング言語によってマチマチなので、「10秒かかった」という実測値ではアルゴリズムの評価には不便だからです。
今回の単純再帰のような指数オーダーのアルゴリズムは、対象データがよほど小さくない限り現実的には計算不可能なもので、その所要時間は宇宙の寿命を容易に超えます。
※再帰がすべてダメということはなく、再帰を効率化するテクニックが適用できるケースがあり、そのような場合には有効な解法として機能します。 テクニックとしては次のようなものがあります。
動的計画法
フィボナッチ数を求めるには、もっと速いアルゴリズムがあります。 人間がフィボナッチ数を計算するように、第1項から第n項まで足し算を積み上げていく方法です。 このようなアルゴリズムは「動的計画法」と呼ばれるものです。
function fib2(n) {
var current = 1
var next = 1
var tmp
for (var i = 1; i < n; i++) {
tmp = current + next
current = next
next = tmp
}
return current
}
このアルゴリズムの計算量は「forループの中身を何回繰り返すか」が支配的となり、実測値で第45項を求める際には44回転、計算量は「nのオーダー」となります。
この方法でフィボナッチ数列の第45項目を計算したところ、いままで10秒かかっていたところ0ミリ秒で完了しました。 ミリ秒とは1000分の1秒のことです。 つまり速すぎて計測できませんでした。 22億回計算していたのが44回に減ったので、ざっくり言うとn=45のときには5000万倍の高速化に成功しています。 nが大きくなっていくとこの差はさらに広がります。
まとめ
この章で見てきたように、問題に対して適切なアルゴリズムを選択することが大変重要です。
現実世界のさまざまな課題について、より効率的 / 効果的なアルゴリズムを探す研究は世界中で行われています。 アルゴリズムをまとめた辞典というものも存在しています。