algorithmic-complexity-review

dot-skills アルゴリズム計算量（Big-O）のベストプラクティス

コード内のアルゴリズム計算量（Big-O）の問題を、言語に依存せず特定、分類、修正します。8 つのカテゴリにわたる 39 のルールでは、本番コードで意図せず二次、指数的、N+1 の性能劣化を引き起こす大半のパターンを扱います。具体的には、ネストした反復処理、ループ不変の I/O、データ構造の不適切な選択、再帰の爆発、重複計算、コレクション構築のアンチパターン、検索・ソートの選択、メモリ使用量の落とし穴です。

適用するタイミング

次の場合にこのスキルを使用します。

• プルリクエストや関数をレビューして、パフォーマンスの低下を確認するとき
• 「なぜ遅いのか？」「もっと速くできますか？」と尋ねられたとき
• ホットパスや、ユーザー数に応じて入力が増える関数をリファクタリングするとき
• 次の要素を含むコードを読むとき：ネストしたループ、反復処理内の .includes／.find／x in list、ループ内の ORM アクセス、メモ化されていない再帰、+= やスプレッド構文による文字列・配列の構築、反復処理内のファイル／データベース I/O
• サイズが増えていくリスト、ツリー、ストリームを処理するコードをレビューするとき

ワークフロー：特定、分類、修正

このスキルは、レビュー対象のあらゆるコードに対する 3 ステップのワークフローとして構成されています。

1. 特定 — 疑わしいパターンを探す

まず、次の構造的な兆候を探します（検出率が最も高いもの）。

兆候	該当しやすいカテゴリ	最初に確認するルール
2 つのネストした for ループ	nested-	nested-explicit-quadratic-loops
ループ内の .includes／.find／x in list	nested-	nested-includes-in-loop
ループ内の ORM アクセス（for o in orders: o.customer.x）	io-	io-n-plus-one-query
for-of 内の await fetch	io-	io-sequential-await-in-loop
2 つの配列の「結合」に array.find を使用	ds-	ds-hashmap-for-keyed-access
引数が重複する再帰関数	rec-	rec-memoize-overlapping-subproblems
ループ内の s = s + part または [...acc, x]	build-	build-avoid-quadratic-string-concat、build-avoid-spread-in-reducer
ループ内で sorted(...) を呼び出す	search-	search-sort-once-outside-loop
readlines()／ファイル全体の読み込み	space-	space-stream-dont-load

2. 分類 — Big-O を導き出す

コードの構造から計算量を求めます。

構造	計算量
n 個の項目に対する単一ループ、O(1) の本体	O(n)
n 個／m 個の項目を反復する 2 つのネストしたループ	O(n*m)
O(n) の操作（.includes、.find、x in list）を呼び出すループ	O(n*m)。多くの場合、O(n) と誤解されます
メモ化なしの再帰 f(n) = f(n-1) + f(n-2)	O(2ⁿ)
再帰 f(n) = 2*f(n/2) + O(n)	O(n log n)
再帰 f(n) = 2*f(n/2) + O(1)	O(n)（ツリー全体の走査）
再帰 f(n) = f(n/2) + O(1)	O(log n)
ループ内の s = s + part	O(n²)（文字列の不変性）
reduce 内の [...acc, x]	O(n²)（スプレッドによるコピー）
n 個の項目を処理するループ内のクエリ／RPC	O(n) 回のラウンドトリップ

迷ったら、次のように考えてください。「入力が 2 倍になると、実行時間もおよそ 2 倍（線形）、4 倍（二次）、それ以上（指数的）になるだろうか？」 これが実用的な計算量の分類です。

3. 修正 — 該当するルールのパターンを適用する

references/ 内の各リファレンスファイルは、次の内容を含む {category}-{slug}.md 形式のファイルです。

• そのパターンが重要な理由（連鎖的な影響）
• コストの注釈が付いた誤ったコード例
• 最小限の差分を示す正しい例
• 修正を適用しない場合（ルールに例外がある場合）

最小差分を重視する方針は意図的なものです。複雑性クラスを変えるために、何行だけ変更すればよいかをエージェントが正確に把握できるようにすることが目的です。

優先度別のルールカテゴリ

#	カテゴリ	接頭辞	影響度	ルール数
1	ネストした反復処理のパターン	nested-	重大	6
2	ループ不変の I/O と N+1	io-	重大	5
3	データ構造の不一致	ds-	高	6
4	再帰の複雑性	rec-	高	5
5	冗長な計算	compute-	中〜高	5
6	コレクションの構築	build-	中	4
7	検索とソートの選択	search-	中	4
8	空間計算量の落とし穴	space-	低〜中	4

優先順位の根拠の詳細は、references/_sections.md を参照してください。

クイックリファレンス

1. ネストした反復処理のパターン（重大）

• nested-explicit-quadratic-loops — ペア単位のループを、ハッシュベースの単一パスに置き換える
• nested-includes-in-loop — ループ内で .includes() / .indexOf() を使わない
• nested-find-in-loop — 反復ごとに .find() を呼ぶのではなく、検索対象を事前にインデックス化する
• nested-cartesian-comparison — 直積比較ではなく、キーでグループ化する
• nested-set-operations-on-arrays — 積集合、和集合、差集合にはセットを使う
• nested-substring-search-in-loop — パターンごとに再スキャンするのではなく、一度だけトークン化する

2. ループ不変の I/O と N+1 クエリ（重大）

• io-n-plus-one-query — 関連データを1回の往復で取得し、N+1 クエリをなくす
• io-sequential-await-in-loop — 独立した非同期処理を並列実行する
• io-batch-instead-of-per-item — アイテムごとの呼び出しではなく、バッチエンドポイントを使う
• io-file-read-in-loop — 高頻度のループの外でファイルを読み取るか、状態を取得する
• io-missing-eager-load — アクセスする ORM リレーションを先行読み込みする

3. データ構造の不一致（高）

• ds-hashmap-for-keyed-access — レコードは並列配列ではなく、キー付きのハッシュマップに格納する
• ds-heap-for-top-k — 上位 k 件の取得には、全件ソートしてスライスするのではなく、ヒープを使う
• ds-deque-for-front-operations — 先頭への挿入や削除には、デキューを使う
• ds-counter-for-histograms — 頻度のカウントには Counter / マルチセットを使う
• ds-sorted-structure-for-range-queries — 範囲クエリにはソート済みのデータ構造を使う
• ds-trie-for-prefix-search — 前方一致検索にはトライを使う

4. 再帰の計算量（高）

• rec-memoize-overlapping-subproblems — 重複する部分問題を含む再帰をメモ化します
• rec-tabulate-bottom-up — ボトムアップで表を作成し、再帰のオーバーヘッドをなくします
• rec-iterative-for-deep-recursion — 深い再帰の代わりに明示的なスタックを使用します
• rec-prune-with-bounds — 上限と制約を使って再帰検索を枝刈りします
• rec-share-memo-across-top-level-calls — トップレベルの呼び出し間でメモ化を共有します

5. 冗長な計算（中〜高）

• compute-hoist-loop-invariants — ループ不変の計算をループの外に移動します
• compute-precompile-regex — 正規表現パターンを事前コンパイルします
• compute-cache-expensive-pure-results — コストの高い純粋関数の結果をキャッシュします
• compute-cache-property-lookup — ホットループ内で繰り返されるプロパティ参照をキャッシュします
• compute-defer-or-short-circuit — 必要ない可能性がある処理は遅延または短絡します

6. コレクションの構築（中）

• build-avoid-quadratic-string-concat — 文字列は繰り返し連結するのではなく、joinやビルダーを使って構築します
• build-avoid-spread-in-reducer — スプレッド構文の代わりに、変更可能なアキュムレーターへ追加します
• build-avoid-immutable-object-spread — プレーンオブジェクトを構築してからフリーズします
• build-presize-when-length-known — 長さがわかっている場合は、コレクションを事前に確保します

7. 検索とソートの選択（中）

• search-binary-search-on-sorted — ソート済みデータには二分探索を使用します
• search-sort-once-outside-loop — 毎回の反復でソートするのではなく、ループの外で一度だけソートします
• search-quickselect-not-full-sort — 全件ソートではなく、k番目の要素にはクイックセレクトを使用します
• search-build-index-once-amortize — クエリが多い場合は、インデックスを一度だけ構築します

8. 空間計算量の落とし穴（低〜中）

• space-stream-dont-load — 大きな入力をすべて読み込むのではなく、ストリーム処理します
• space-generators-over-intermediate-lists — 中間リストを実体化するのではなく、ジェネレーターで処理をつなぎます
• space-shallow-not-deep-copy — ディープコピーではなく、シャローコピー（またはコピーなし）を使用します
• space-release-retained-references — ガベージコレクションを妨げている参照を解放します

使用方法

1. まず、上の Find シグナル表を確認し、該当する可能性が最も高いパターンを探します。
2. 一致するリファレンスファイルを開き、理由と最小差分の修正を確認します。
3. 計算量を一から分類する場合は、Classify 表を使い、コードの構造からBig-Oを導きます。
4. 修正を提案するときは、レビュー担当者が根拠を確認できるよう、ファイルパスを示してルールを引用します。
5. カテゴリーの順序の根拠については references/_sections.md を、新しいルールを追加する場合は assets/templates/_template.md を参照してください。

参考ファイル

ファイル	説明
references/_sections.md	カテゴリの定義、影響レベル、順序付けの根拠
assets/templates/_template.md	新しいルールを追加するためのテンプレート
metadata.json	分野、種類、出典の参照情報

関連スキル

• bug-review — 複数のパスで PR のバグをレビューします（このスキルは、特にパフォーマンスの問題に特化した補完スキルです）
• 言語固有のベストプラクティススキル（React、Python、Go）— Big-O 以外のイディオムを扱います。パフォーマンスが重要なレビューでは、このスキルと組み合わせてください