メモ化(キャッシュ)で計算を高速化する

このレッスンでは、C言語でメモ化(キャッシュ)を使って計算を高速化する方法を学び、同じ計算を繰り返さない工夫を理解することを目標にします。「C言語 メモ化 使い方」で調べている方向けです。

メモ化は、一度計算した結果を「保管箱」に保存しておき、同じ入力が来たら計算し直さずに保管箱から取り出すテクニックです。「毎回同じ質問をされたら、覚えておいた答えをそのまま返す」ようなイメージです。

サンプルコードでは、cacheというグローバル配列に計算済みの結果を保存し、slowSquare()関数が呼ばれるたびにcache[n] != -1で既に計算済みかを確認しています。2回目以降の同じ入力では「キャッシュから取得」というメッセージが表示されます。

初心者がよくつまずくのが、キャッシュ配列の初期値の扱いです。「未計算」を表す値(この場合は-1)を事前に決めておき、実際の計算結果と区別する仕組みが必要になります。

実際の開発現場では、特に再帰的な計算やAPIの呼び出し結果をキャッシュする場面で、体感できるほどの速度改善が得られます。