フィボナッチ数列を題材に、動的計画法の基本概念であるメモ化を実例とコードで詳しく解説。計算時間の大幅短縮を体験できます。
フィボナッチ数列で悩んでいませんか？
こんな経験はありませんか？
- 再帰処理を書いたら、思った以上に処理時間がかかってしまった
- プログラムが重くなる原因が分からない
- 動的計画法という言葉は聞いたことがあるが、具体的にどう実装するか分からない
- 効率的なアルゴリズムを身につけて、パフォーマンスの良いシステムを作りたい
これらの悩みは、実は多くの開発者が通る道です。Fivenine Designでも、20年以上のWeb制作経験の中で、「なぜこんなに遅いのか？」というご相談を数多くいただいてきました。
あるクライアント様では、商品レコメンデーション機能を実装した際、単純な再帰処理で計算していたため、ユーザーが商品ページを開くたびに5秒以上待たせてしまうという問題が発生しました。この問題を動的計画法で解決したところ、処理時間を0.1秒以下に短縮できたのです。
なぜ処理が重くなるのか？再帰処理の落とし穴
処理が重くなる最大の原因は、同じ計算を何度も繰り返していることです。これを理解するために、まずフィボナッチ数列を例に見てみましょう。
フィボナッチ数列とは、「前の2つの数を足した値が次の数になる」という規則で構成される数列です： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
素朴な再帰実装の問題点
最初に思いつく実装は、このようなものでしょう：
function fibonacci($n) {
if ($n <= 1) {
return $n;
}
return fibonacci($n - 1) + fibonacci($n - 2);
}
// 実行例
echo fibonacci(10); // 55
しかし、この実装には致命的な問題があります。fibonacci(5)を計算する際の処理の流れを見てみましょう：
flowchart TD
A[fib(5)] --> B[fib(4)]
A --> C[fib(3)]
B --> D[fib(3)]
B --> E[fib(2)]
C --> F[fib(2)]
C --> G[fib(1)]
D --> H[fib(2)]
D --> I[fib(1)]
E --> J[fib(1)]
E --> K[fib(0)]
F --> L[fib(1)]
F --> M[fib(0)]
H --> N[fib(1)]
H --> O[fib(0)]fib(3)が3回、fib(2)が5回も計算されています。数が大きくなるにつれて、この無駄は指数関数的に増加します。
計算回数の爆発的増加
実際の計算回数を測定してみると、その深刻さが分かります：
このグラフからも明らかなように、単純な再帰では計算回数が爆発的に増加します。fibonacci(40)を計算するのに3億回以上の関数呼び出しが発生するのです。
メモ化による劇的な改善 - 動的計画法の核心
メモ化とは
メモ化（Memoization）とは、一度計算した結果を記録しておき、同じ計算が必要になったときは記録した結果を使う技術です。これにより、重複計算を避けることができます。
PHP版：配列を使ったメモ化実装
class FibonacciCalculator {
private $memo = [];
public function fibonacci($n) {
// すでに計算済みの場合は記録された値を返す
if (isset($this->memo[$n])) {
return $this->memo[$n];
}
// ベースケース
if ($n <= 1) {
$this->memo[$n] = $n;
return $n;
}
// 計算結果をメモに保存してから返す
$this->memo[$n] = $this->fibonacci($n - 1) + $this->fibonacci($n - 2);
return $this->memo[$n];
}
// メモの状態を確認するメソッド
public function getMemo() {
return $this->memo;
}
}
// 使用例
$calc = new FibonacciCalculator();
echo $calc->fibonacci(40); // 102334155
print_r($calc->getMemo()); // 計算過程が確認できる
JavaScript版：Mapを使った実装
class FibonacciCalculator {
private $memo = [];
public function fibonacci($n) {
if (isset($this->memo[$n])) {
return $this->memo[$n];
}
if ($n <= 1) {
$this->memo[$n] = $n;
return $n;
}
$this->memo[$n] = $this->fibonacci($n - 1) + $this->fibonacci($n - 2);
return $this->memo[$n];
}
}
ボトムアップ方式（反復版）
メモ化は再帰を使いましたが、より効率的な反復版も実装できます：
function fibonacci_iterative($n) {
if ($n <= 1) return $n;
$dp = [0, 1];
for ($i = 2; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] + $dp[$i - 2];
}
return $dp[$n];
}
// さらに空間効率を改善した版
function fibonacci_optimized($n) {
if ($n <= 1) return $n;
$prev2 = 0;
$prev1 = 1;
for ($i = 2; $i <= $n; $i++) {
$current = $prev1 + $prev2;
$prev2 = $prev1;
$prev1 = $current;
}
return $prev1;
}
パフォーマンス比較
実際のパフォーマンス測定結果を見てみましょう：
実案件での活用例
ケース1：商品レコメンデーション機能
前述のクライアント様では、「この商品を見た人におすすめの商品」を計算する際、類似度スコアの計算で再帰処理を使用していました。10万件の商品データに対して、単純な再帰では処理時間が5秒以上かかっていましたが、メモ化を適用することで0.1秒以下に短縮できました。
class RecommendationEngine {
private $similarity_cache = [];
public function calculateSimilarity($product_id_1, $product_id_2) {
$cache_key = min($product_id_1, $product_id_2) . '_' . max($product_id_1, $product_id_2);
if (isset($this->similarity_cache[$cache_key])) {
return $this->similarity_cache[$cache_key];
}
// 複雑な類似度計算処理
$similarity = $this->computeComplexSimilarity($product_id_1, $product_id_2);
$this->similarity_cache[$cache_key] = $similarity;
return $similarity;
}
}
ケース2：ウェブサイトのナビゲーションパンくずリスト
階層の深いウェブサイトでは、パンくずリストの生成にも動的計画法が活用できます：
class BreadcrumbGenerator {
private $path_cache = [];
public function generateBreadcrumb($page_id) {
if (isset($this->path_cache[$page_id])) {
return $this->path_cache[$page_id];
}
$page = $this->getPage($page_id);
if ($page['parent_id'] === null) {
$path = [$page['title']];
} else {
$parent_path = $this->generateBreadcrumb($page['parent_id']);
$path = array_merge($parent_path, [$page['title']]);
}
$this->path_cache[$page_id] = $path;
return $path;
}
}
よくある失敗パターンと対処法
失敗パターン1：メモリ使用量を考慮しない
よくある失敗
// 悪い例：無制限にキャッシュしてメモリ不足になる
class BadFibonacci {
private static $memo = [];
public static function fibonacci($n) {
// メモリ使用量を全く考慮しない実装
if (isset(self::$memo[$n])) {
return self::$memo[$n];
}
// ... 計算処理
}
}
正しい対処法
// 良い例：キャッシュサイズを制限
class SafeFibonacci {
private $memo = [];
private $max_cache_size = 1000;
public function fibonacci($n) {
// キャッシュサイズが上限に達したらクリア
if (count($this->memo) > $this->max_cache_size) {
$this->memo = array_slice($this->memo, -500, null, true);
}
if (isset($this->memo[$n])) {
return $this->memo[$n];
}
// ... 計算処理
}
}
失敗パターン2：マルチスレッド環境でのデータ競合
問題となるケース
// 悪い例：複数リクエストで同時実行すると整合性が取れない
class UnsafeFibonacci {
private static $memo = []; // static変数が危険
public static function fibonacci($n) {
// 他のリクエストからも同時にアクセスされる可能性
if (isset(self::$memo[$n])) {
return self::$memo[$n];
}
// ...
}
}
安全な実装
// 良い例：インスタンスごとに管理、または適切な排他制御
class SafeFibonacci {
private $memo = []; // インスタンス変数にする
public function fibonacci($n) {
// インスタンスごとにキャッシュが独立
if (isset($this->memo[$n])) {
return $this->memo[$n];
}
// ...
}
}
失敗パターン3：キャッシュキーの設計ミス
よくある失敗
// 悪い例：キャッシュキーが重複する可能性
class BadCache {
private $memo = [];
public function calculate($x, $y) {
$key = $x . $y; // "12" + "3" と "1" + "23" が同じキーになる
if (isset($this->memo[$key])) {
return $this->memo[$key];
}
// ...
}
}
正しいキーの作り方
// 良い例：適切な区切り文字を使用
class GoodCache {
private $memo = [];
public function calculate($x, $y) {
$key = $x . '_' . $y; // 区切り文字で明確に分離
// または
$key = serialize([$x, $y]); // 配列をシリアライズ
if (isset($this->memo[$key])) {
return $this->memo[$key];
}
// ...
}
}
より高度な動的計画法の応用
最長共通部分列問題
class LCSCalculator {
private $memo = [];
public function longestCommonSubsequence($text1, $text2, $i = null, $j = null) {
if ($i === null) $i = strlen($text1) - 1;
if ($j === null) $j = strlen($text2) - 1;
$key = $i . '_' . $j;
if (isset($this->memo[$key])) {
return $this->memo[$key];
}
if ($i < 0 || $j < 0) {
return 0;
}
if ($text1[$i] === $text2[$j]) {
$result = 1 + $this->longestCommonSubsequence($text1, $text2, $i - 1, $j - 1);
} else {
$result = max(
$this->longestCommonSubsequence($text1, $text2, $i - 1, $j),
$this->longestCommonSubsequence($text1, $text2, $i, $j - 1)
);
}
$this->memo[$key] = $result;
return $result;
}
}
// 使用例：文書の類似度判定
$lcs = new LCSCalculator();
$similarity = $lcs->longestCommonSubsequence("programming", "grammar");
echo $similarity; // 5 ("gramm"が最長共通部分列)
ナップサック問題
class KnapsackSolver {
private $memo = [];
public function knapsack($items, $capacity, $index = 0) {
$key = $capacity . '_' . $index;
if (isset($this->memo[$key])) {
return $this->memo[$key];
}
if ($index >= count($items) || $capacity <= 0) {
return 0;
}
$item = $items[$index];
// アイテムを取らない場合
$without_item = $this->knapsack($items, $capacity, $index + 1);
// アイテムを取る場合（容量が足りる場合のみ）
$with_item = 0;
if ($item['weight'] <= $capacity) {
$with_item = $item['value'] + $this->knapsack(
$items,
$capacity - $item['weight'],
$index + 1
);
}
$result = max($without_item, $with_item);
$this->memo[$key] = $result;
return $result;
}
}
まとめと次のステップ
フィボナッチ数列を通じて動的計画法とメモ化を学んできました。重要なポイントを整理すると：
動的計画法の核心
- 同じ問題を何度も解くのではなく、一度解いた結果を保存して再利用する
- 指数時間の問題を多項式時間で解けるようになる場合が多い
- メモリと時間のトレードオフを意識した設計が重要
実際の効果
Fivenine Designでは、これまで数多くのクライアント様のシステム最適化を手がけてきました。動的計画法を適用することで、処理時間を数秒から数十ミリ秒に短縮できたケースは少なくありません。
次に学ぶべき領域
- データベースクエリの最適化: SQLクエリでも同様の考え方が適用できます
- キャッシュ戦略: Redis、Memcachedを使った大規模なキャッシュ設計
- 他の動的計画法の問題: 最短経路問題、編集距離、部分和問題など
今すぐできること 現在開発中のシステムで、以下のような処理があれば動的計画法の適用を検討してみてください：
- 再帰的な計算処理
- 同じデータを繰り返し処理している箇所
- レスポンス時間が遅いAPI処理
実装チェックリスト
もし「自社のシステムに動的計画法を適用したいが、どこから始めればよいか分からない」「既存システムのボトルネックを特定したい」といったご相談がございましたら、お気軽にFivenine Designまでお問い合わせください。20年以上の経験を活かし、貴社のシステム最適化をサポートいたします。
