成長率を読むコード
正確性を確認するコードレビューと複雑性に注意を払ったコードレビュー
正確性を確認するコードレビューは、間違った条件、オフバイワンインデックス、見つからないチェックがないことを確認します。複雑性に注意を払ったコードレビューは、N = 100で正しく動作するが、N = 100,000で急速に悪化するコードを検出します。
このレッスンは、unhammingコースのより深い調査に接続されます：[アルゴリズムの複雑性：見えない章](/en/un/unhamming_algorithmic_complexity)は、生産欠陥の文脈でBig Oを扱い、[MOAD-0001：堆積欠陥](/en/un/unhamming_moad_sedimentary)は、60以上のソフトウェアエコシステムでパターンをマップします。
二つのレビューのヒューリスティック
ネストされたループは複雑性を増やす。 N個のアイテムの上に2重ループはO(N²)、3重はO(N³)。レビューする際には、ループのネスト深度を最初に数えます。
シーケンシャルなコンテナ内に熱いループ。 ループ内で.contains(), .includes(), .find()、またはin listチェックは、NのiterationあたりO(N)のコストです。Nのオーバーイテレーション：O(N²)の総計です。このパターンは、数十のエコシステムの生産コードに登場しています — GHC Haskellコンパイラ、Python pip、Apache Maven、Rust Cargo、TypeScript、Godot。同じ間違い、異なるコードベース。
レビュー：find_duplicates
複雑性に注意を払ったコードレビューを行ってください：
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001:堆積物障害
同じ障害、六十のエコシステム
ループ内に if x not in list: list.append(x) パターンが -- あるいはすでに -- 複数のソフトウェアエコシステムの実行中のコードで見られました:
- GHC (Haskell コンパイラ): 依存解決器、N = 50,000 のパッケージの場合、O(N²)、17分間のビルド時間
- Python pip: 依存関係の対立解決
- Apache Maven: クラスパス重複解消
- Rust Cargo: 機能統一
- TypeScript コンパイラ: モジュール解決
- Godot / Redot ゲームエンジン: ノードグラフのトラバース
これらのチームは、間違いをしました。N が小さい場合に正しいコードを書きました。N が増加しました。コードは硬化しました。パターンには名前があります:MOAD-0001, The Sedimentary Defect。堆積物：正確で、薄い層では害なし。時間の経過とともに、層が蓄積し、硬化します。
解決策
すべての場合で、順序付きコンテナをハッシュコンテナに置き換えます。1 行。正しい入力に対してビヘイビアが変わらない。実用的な N の場合で 100-1,000 倍のスピードアップ。
解決策は、次の 2 つの操作が速くて残る必要があるため、効果があります:
1. メンバー検索: これらの要素は前に見たことがありますか？
2. 順序付き出力: 要素がどの順序で表示されるか (時々必要、時々必要ない)
集合体は (1) を O(1) で処理します。もし (2) も重要である場合、順序付き出力のために別のリストを保持し、メンバー検索のために集合体を使用します。各データ構造は、それぞれの役割をこなす
レビューへの対応
プルリクエストは、プロジェクトのグラフトラバース関数で MOAD-0001 を修正します。レビュワーがコメントします:
> "Sets には挿入順序が保持されません — これは挙動が変わります。"
インタビューア分析パターン
期待されるフォーマット
アルゴリズム的複雑性分析は、ソフトウェア開発インタビューで登場します。強力な回答は、4つのパターンに従います:
1. 現在の複雑さを述べる — 時間 O(?)、空間 O(?)。
2. なぜそうであるか説明する — 特定の構造（入れ子にしたループ、ループ内で線形スキャン、再帰的な分岐）がどれであるかを特定する。
3. 最適化を提案する — 変更の名前と導入するデータ構造またはアルゴリズムを名指しする。
4. 新しい複雑さを述べる — 修正後の時間と空間複雑さは何ですか？
例:
コード：[リスト内ループでメンバーをチェックする関数]
現在：O(N²) — `item in seen_list` はチェックごとにO(N) × N回の繰り返し
最適化：seen_list を seen_set（ハッシュセット）に置き換えます
後：O(N) — セットのメンバー判定はO(1)このスキルは、インタビューの外でも転用できます：複雑性に意識したコードレビュー、アーキテクチャ設計、パフォーマンスデバッグ、セキュリティオーディト。変動する入力処理を行うシステムはすべてこれに利益をもたらします。
このレッスンは、60以上のオープンソースプロジェクトでの生産デフォルト調査にこのexactパターンを適用するunhammingコースに繋がります。
インタビュー：analyze_has_common_element
この関数に4つのインタビューフォーマットを適用してください:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False