🏧

「AI任せ」にしないパフォーマンス最適化：開発者こそ知るべき計算量の知識

に公開
PHP
パフォーマンス改善
tech

はじめに

近年、生成AIの活用により、コードの自動生成やレビューが身近になりました。開発の初速が劇的に向上する一方で、新たな課題も生まれています。

  • AIは計算量を無視することがある: 生成AIは、一見すると正しく動作するものの、計算量を考慮していない非効率なコード（例: O(n²)のループ）を生成することがあります。
  • 提案を評価する知識が必要: AIがパフォーマンス改善案を提示してくれても、その良し悪しを最終的に判断し、責任を持つのは開発者自身。そのためにも基本的な知識が必要。

AIは便利ですが、最終的なコードの品質を担保し、長期的にスケールするアプリケーションを設計するのは、開発者の知識とスキルのはずです。（自分への戒めもたぶんにあります、、）

そのための一歩として、下記にて計算量オーダー（O記法）について簡単にまとめました。

1. 基本の考え方

計算量オーダー（O記法）とは、処理の速さをデータ量 n の増え方で表す指標。
定数倍や細かい処理時間ではなく、スケールの仕方に注目する。

記法 処理の増え方 概要
O(1) 一定時間 データ量に関係ない
O(log n) 対数的 半分ずつ絞り込む処理
O(n) 線形 データを1回ずつ処理
O(n log n) 準線形 ソートや分割統治型
O(n²) 二乗 ネストされたループ

2. PHPコード例で理解する

O(1)

$numbers = [10, 20, 30, 40, 50];
echo $numbers[2]; // 常に一定時間

O(n)

foreach ($numbers as $num) {
    echo $num;
}

O(n²)

foreach ($numbers as $a) {
    foreach ($numbers as $b) {
        echo "($a, $b)";
    }
}

O(log n)

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);
        if ($arr[$mid] === $target) return true;
        if ($arr[$mid] < $target) $left = $mid + 1;
        else $right = $mid - 1;
    }
    return false;
}

O(n log n)

$numbers = [5, 3, 8, 6, 2, 7, 4, 1];
sort($numbers); // PHP内部でクイックソート系

3. 実務での意識ポイント

シーン 典型的な落とし穴 改善策
コレクション検索 foreachで毎回探す keyBy()で連想配列化しO(1)化
ネストループで関連付け O(n²) になる 一度マップ化→単一ループ
filter+first の繰り返し O(n²) keyBy + 直接アクセス
ソート データが大きいと遅い DB側ORDER BY＋インデックス活用
集計 ループで足し算 SQLでSUM()またはgroupBy活用

4. コレクション最適化パターン

1. 特定IDの検索： O(n) → O(1)

foreachで毎回探すのではなく、keyBy()でIDをキーにした連想配列に変換しておくことで、計算量をO(1)にできます。

悪い例: O(n)

function findUser(array $users, int $targetId): ?array
{
    foreach ($users as $user) {
        if ($user['id'] === $targetId) {
            return $user;
        }
    }
    return null;
}

良い例: O(1)アクセス

// 事前にIDで索引付けしたマップを作成
$usersById = collect($users)->keyBy('id');

// O(1)でアクセス
$user = $usersById[$targetId] ?? null;

2. 関連データの紐付け： O(n²) → O(n)

ネストループで関連データを紐付けるとO(n²)になります。これもkeyBy()でマップ化しておくことで、単一のループで済み、O(n)に改善できます。

悪い例: O(n²)

foreach ($orders as &$order) {
    foreach ($users as $user) {
        if ($order['user_id'] === $user['id']) {
            $order['user_name'] = $user['name'];
            break;
        }
    }
}

良い例: O(n)

$usersById = collect($users)->keyBy('id');

foreach ($orders as &$order) {
    $order['user_name'] = $usersById[$order['user_id']]['name'] ?? null;
}

3. ループ内でのfilter/first呼び出しの回避

ループの中で毎回コレクション全体を検索するfirstWhereのようなメソッドを呼び出すと、実質的にO(n²)の処理になります。これも事前にマップ化することで解決します。

悪い例: O(n²)

foreach ($targets as $t) {
    // ループのたびにコレクション全体を検索している
    $matched = $collection->firstWhere('id', $t->id);
    // ...
}

良い例: O(n)で準備し、ループ内はO(1)

// 最初に一度だけマップ化
$indexed = $collection->keyBy('id');

foreach ($targets as $t) {
    // O(1)でアクセス
    $matched = $indexed[$t->id] ?? null;
    // ...
}

例外・補足

データが非常に小さい（10件以下など）なら、keyBy() の構築コストが上回る場合もあります。

PHPの連想配列はハッシュテーブル構造なので、キー検索の平均計算量はO(1)、
ただし最悪の場合は衝突によって O(n) になる可能性も理論上はある（通常は無視してOK）。

4.5.【注意】N+1クエリ問題

ループ内でデータベースへの問い合わせが繰り返し発生し、パフォーマンスが著しく低下する問題です。特にORMを利用していると無意識に発生させがちです。

悪い例 (N+1が発生)

// 投稿一覧を取得 (1クエリ)
$posts = Post::all();

// 各投稿のユーザー名を表示するために、ループ内で毎回クエリが発行される (Nクエリ)
foreach ($posts as $post) {
    echo $post->user->name; 
}

このコードは、投稿が100件あれば 1 + 100 = 101 回のクエリが実行されてしまいます。

良い例 (Eager Loadingで解決)

with() を使って事前に関連モデルを読み込んでおく（Eager Loading）ことで、クエリ回数を大幅に削減できます。

// with('user') でユーザー情報もまとめて取得 (2クエリ)
$posts = Post::with('user')->get();

foreach ($posts as $post) {
    echo $post->user->name;
}

この場合、クエリは投稿を取得する1回と、関連するユーザーをまとめて取得する1回の、合計2回で済みます。データ量が増えてもクエリ回数は一定です。

5. 目安表

記法 データ1万件時の目安 改善の方向性
O(1) 即時 キャッシュ・連想配列
O(log n) 約14回処理 二分探索系
O(n) 1万回 一回で済むよう設計
O(n log n) 約14万回 分割統治（ソート等）
O(n²) 1億回 ネスト削減・前処理化

開発時のチェックリスト

  • 同じループの中で filter / firstWhere を呼んでいないか
  • DBに対して N回のクエリを投げていないか
  • 重複計算を避ける。キャッシュ or keyBy マップを作っているか
  • ソートや集計をアプリでなくDBに任せられるか

Tip:
Eloquentコレクションなら keyBy(), mapWithKeys(), groupBy() を積極的に活用すると
O(n²) → O(n) / O(1) に改善できるケースが多い。

Tip:
カスタムコマンドを利用して、AIにパフォーマンス分析を依頼するのもおすすめです。
例えば、以下のようなプロンプトを analyze_backend_response_flow という名前で登録しておくと、いつでもAIに計算量のレビューをさせることができます。

下記はgemini CLIでの例です。

name: analyze_backend_response_flow
prompt: |-
  添付されたバックエンドコードを対象に、パフォーマンスに関する問題を以下の観点で分析してください。

  ---

  - **計算量・アルゴリズムの最適化**
    - ループやコレクション操作の計算量（O(1), O(n), O(n²) など）を推定し、データ増加時の処理コストを分析。
    - `keyBy()`・`groupBy()` による連想配列化やSQL集約で、O(n²)→O(n)・O(n)→O(1) の改善を提案。

使い方:

gemini @path/to/your/code.php -w analyze_backend_response_flow

おわりに

本記事では、計算量の基本であるO記法から、PHP（特にLaravel）における具体的なパフォーマンス改善パターンまでを解説しました。

特に、以下の点は日々の開発で意識することが重要です。

  • O(n²)の回避: ネストループによるO(n²)の処理は、データ量の増加で致命的なパフォーマンス低下を招きます。keyByなどを活用し、O(n)やO(1)でのアクセスを心がけましょう。
  • N+1問題の防止: ORMを利用する際は、with()によるEager Loadingを習慣づけ、不要なクエリ発行を避けることが大切です。

これらの計算量の観点を意識することで、よりスケーラブルで堅牢なアプリケーションを構築できます。

FAQ（擬似）

Q1. 計算量オーダー（O記法）とは何ですか？
A. アルゴリズムの性能を評価するための指標で、データ量（n）が増えたときに、処理時間がどれくらい増えるかを示したものです。例えば、O(n)ならデータ量に比例して時間が増え、O(n²)ならデータ量の二乗に比例して増えることを意味します。

Q2. なぜ計算量を気にする必要があるのですか？
A. データが少ないうちは問題なくても、データ量が増えるにつれてパフォーマンスが急激に悪化するコードを書いてしまうのを防ぐためです。特にO(n²)のような処理は、データが数千件になるだけで、ユーザー体験を損なうほどの遅延を引き起こす可能性があります。

Q3. PHPでよくある、計算量が大きくなりがちな処理は何ですか？
A. 主に2つあります。1つはループの中でさらにループを回す「ネストループ」で、これはO(n²)になります。もう1つは、ループの中で毎回データベースに問い合わせを行う「N+1クエリ問題」です。

Q4. 配列やコレクションから特定のデータを検索する際、どうすれば速くなりますか？
A. foreachで毎回ループして探す（O(n)）のではなく、最初にkeyBy('id')のようなメソッドでIDなどをキーにした連想配列（マップ）を作っておくのが有効です。これにより、O(1)という非常に高速なアクセスが可能になります。

Q5. 「N+1クエリ問題」とは何ですか？どうすれば解決できますか？
A. 1回のクエリで親データを取得した後、ループ内で関連する子データを取得するためにN回のクエリが追加で発行されてしまう問題です。LaravelのEloquentなどでは、with()メソッドを使って関連データを事前に一括で読み込む（Eager Loading）ことで、クエリ回数を2回程度に抑えられます。

Q6. 生成AIが書いたコードは、計算量の観点から信頼できますか？
A. 必ずしも信頼できるとは限りません。生成AIは便利なコードを生成してくれますが、計算量を無視した非効率なコード（例：安易なネストループ）を生成することもあります。そのため、AIが生成したコードであっても、開発者自身が計算量を意識してレビューすることが重要です。

Discussion