【ITニュース解説】Memoization

プログラミング学習の初期段階では、コードの実行速度や効率性について深く意識することは少ないかもしれない。しかし、より複雑で大規模なシステムを構築するシステムエンジニアを目指す上で、プログラムのパフォーマンスは非常に重要な要素となる。特に、同じ計算を何度も繰り返すような状況では、処理に膨大な時間がかかってしまう場合がある。このような計算コストを削減し、プログラムを高速化するための強力な技術の一つが「メモ化（Memoization）」である。

メモ化とは、一度実行した関数の計算結果を記憶しておき、同じ入力で関数が再度呼び出されたときに、その記憶しておいた結果を再利用することで、計算処理をスキップし、実行速度を向上させる手法だ。これは、人間の記憶に似ている。一度解いた問題は、次に同じ問題に遭遇したときに再び最初から考える必要はなく、解法を思い出してすぐに答えを出すことができる、というイメージだ。

メモ化がどのような状況で役立つか、具体的な例としてフィボナッチ数列を考えてみよう。フィボナッチ数列は、F(0)=0、F(1)=1と定義され、その後はF(n) = F(n-1) + F(n-2)というように、直前の2つの項の和で次の項が決まる数列である。この定義をそのままJavaScriptで実装すると次のようになる。

Copy
1function fibonacci(n) {
2    if (n === 0) {
3        return 0;
4    } else if (n === 1) {
5        return 1;
6    } else {
7        return fibonacci(n-1) + fibonacci(n-2);
8    }
9}

このコードは数列の定義に忠実で非常に分かりやすいが、F(40)やF(45)といった比較的大きな数値を計算させようとすると、実行にかなりの時間がかかることに気づくだろう。なぜなら、この関数は再帰的に自身を呼び出すため、例えばF(5)を計算するためにはF(4)とF(3)が必要となり、F(4)にはF(3)とF(2)が必要…という具合に、計算のツリーが深く広がる。この過程で、F(3)やF(2)といった同じ値が何度も繰り返し計算されてしまうのだ。F(n)の計算に必要な呼び出しの数は約2のn乗に比例するため、nが少し大きくなるだけで計算量が指数関数的に増え、プログラムはたちまち遅くなってしまう。

この非効率性を解消するのがメモ化である。フィボナッチ数列のF(n)は、nが決まれば常に同じ結果を返す「決定論的な」関数だ。つまり、一度F(5)を計算して結果が5だと分かれば、次にF(5)が必要になったときに再度計算する必要はなく、記憶しておいた結果を返せばよい。 基本的なメモ化の実装方法として、計算済みの入力値とそれに対応する結果を外部の配列（またはJavaScriptのMapオブジェクトのようなデータ構造）に保存しておく方法がある。

Copy
1let inputs = [];  // 計算したnの値を保存
2let outputs = []; // 対応する計算結果を保存
3
4function fibExternalMemo(n) {
5    // 既に計算済みかチェック
6    if (inputs.includes(n)) {
7        let index = inputs.indexOf(n);
8        return outputs[index];
9    }
10
11    // 基本ケース
12    if (n === 0) return 0;
13    if (n === 1) return 1;
14
15    // 未計算の場合、計算を実行し、結果を保存
16    let result = fibExternalMemo(n - 1) + fibExternalMemo(n - 2);
17    inputs.push(n);
18    outputs.push(result);
19    return result;
20}

このfibExternalMemo関数は、引数nが過去に計算されたことがあるかをinputs配列で確認し、もしあればoutputs配列から結果を取り出してすぐに返す。初めての引数であれば、通常通り計算を行い、その結果をinputsとoutputsに記録してから返す。この修正により、F(45)のような大きな数でも瞬時に計算できるようになり、劇的な速度向上を体感できるだろう。

しかし、この方法では、inputsとoutputsというグローバルな変数に依存しているため、関数の独立性が損なわれ、汎用性に欠けるという問題がある。より洗練された方法として、「高階関数」と「クロージャ」というJavaScriptの機能を利用する方法がある。高階関数とは、関数を引数として受け取ったり、関数を戻り値として返したりする関数のことだ。

任意の関数をメモ化する高階関数memoizeは次のようになる。

Copy
1function memoize(f) {
2    let inputs = [];  // メモ化対象関数の入力
3    let outputs = []; // メモ化対象関数の出力
4
5    function memoized(input) {
6        // 既に計算済みかチェック
7        for (let i = 0; i < inputs.length; i++) {
8            if (inputs[i] === input) {
9                return outputs[i];
10            } 
11        }
12
13        // 未計算の場合、元の関数fを実行し、結果を保存
14        let newResult = f(input);
15        inputs.push(input);
16        outputs.push(newResult);
17        return newResult;
18    }
19
20    return memoized; // メモ化機能付きの新しい関数を返す
21}

このmemoize関数は、メモ化したい関数fを受け取り、そのfにメモ化機能を追加した新しい関数memoizedを返す。inputsとoutputs配列はmemoize関数が実行されたときに生成され、返されたmemoized関数によって「クロージャ」という仕組みでアクセス可能になる。これにより、メモ化に必要なデータが関数の内部に隠蔽され、外部の変数を汚染することなく、異なる関数に対しても同じmemoize関数を使って汎用的にメモ化を適用できるようになる。

しかし、再帰関数をメモ化する際には一つ注意点がある。先の素朴なfibonacci関数をこのmemoize関数でラップしても、初回呼び出しは期待通りに速くならない。

Copy
1let wrappedFib = memoize(fibonacci);
2// wrappedFib(45) を実行すると、依然として非常に時間がかかる

これは、wrappedFib(45)を初めて呼び出すと、memoize関数内部のmemoized関数は、引数で渡された元のfibonacci関数をf(45)として呼び出すためだ。このfibonacci関数内部で行われるfibonacci(n-1) + fibonacci(n-2)という再帰呼び出しは、メモ化機能を持つwrappedFibではなく、メモ化されていない元のfibonacci関数自身を呼び出している。結果的に、すべての計算がやり直しになってしまい、速度向上にはつながらないのだ。

この問題を解決するには、メモ化された関数自身が再帰的に呼び出されるように定義する必要がある。

Copy
1let memoizedFib = memoize(n => {
2    if (n === 0) return 0;
3    if (n === 1) return 1;
4    // ここで memoizedFib 自身を再帰的に呼び出すのがポイント
5    return memoizedFib(n-1) + memoizedFib(n-2); 
6});

このように、memoize関数に渡す関数（ここではアロー関数で記述されている部分）の内部で、自身（つまりmemoizedFib）を再帰的に呼び出すようにする。これにより、すべての再帰呼び出しがメモ化機能を持つmemoizedFibを経由することになり、効率的な計算が可能となる。この書き方には少し慣れが必要だが、様々な再帰関数に汎用的にメモ化を適用できる非常に強力なテクニックだ。

メモ化は非常に効果的な最適化手法だが、万能ではない。メモ化の大きなデメリットは、計算結果を記憶するためにメモリを消費することだ。入力と出力のペアが増えれば増えるほど、メモリ使用量も増大する。また、すべての入力が一度しか使われないような関数では、結果を記憶しても再利用される機会がないため、単にメモリを無駄に消費するだけで、かえってオーバーヘッドになることもある。

したがって、メモ化は以下のような場合に特に有効だと覚えておくとよい。

• 計算コストが高い関数である。
• 同じ入力に対して何度も呼び出されることが予想される。
• 関数が決定論的である（同じ入力に対して常に同じ出力を返す）。

このような条件を満たす場面では、メモ化はプログラムの実行速度を劇的に改善し、システムのパフォーマンス向上に大きく貢献する強力なツールとなる。システムエンジニアとして効率的で高速なプログラムを開発するためには、メモ化のような最適化技術を適切に使いこなす知識が不可欠である。