成長率のためのコードの読み込み
正確性に対するコードレビュー vs 複雑性に対するコードレビュー
正確性に対するコードレビューは論理エラーを捕捉します: 間違った条件、オフバイワンインデックス、nullチェックの欠落。複雑性を認識したコードレビューは異なるクラスの欠陥を捕捉します: N = 100では正しく機能するが、N = 100,000では壊滅的に成長するコード。
このレッスンはunhammingコースでより深い調査に接続しています: 欠けている章: アルゴリズム複雑性 は本番欠陥の文脈でBig Oをカバーし、& MOAD-0001: 堆積欠陥 は60以上のソフトウェアエコシステム全体のパターンをマップしています。
2つのレビューヒューリスティック
ネストされたループが複雑性を乗算します。 N個のアイテムの2つのネストされたループはO(N²)を生成します。3つはO(N³)を生成します。レビューするときは: ループのネスト深さを最初にカウントしてください。
ホットループ内のシーケンシャルコンテナ。 ホットループ内の .contains()、.includes()、.find()、または in list チェックは、1チェックあたりO(N)がかかります。N回の反復の場合: 合計O(N²)。このパターンはGHC Haskellコンパイラ、Python pip、Apache Maven、Rust Cargo、TypeScript、Godotなど、数十のエコシステム全体で本番コードに現れます。同じ間違い、異なるコードベース。
レビュー: find_duplicates
複雑性のために次のPython関数をレビューしてください:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: 堆積欠陥
同じ欠陥、60のエコシステム
パターン 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、堆積欠陥。 堆積物: 薄い層では正確で無害です。時間とともに、層が蓄積して硬化します。
修正
すべてのケースで: シーケンシャルコンテナをハッシュコンテナに置き換えます。1行。正しい入力で動作的な変化はありません。実世界のNで100–1,000倍のスピードアップ。
修正が機能する理由は、2つの操作が高速である必要があるためです:
1. メンバーシップチェック: この要素は以前に見たことがありますか?
2. 順序付き出力: 表示される順序で要素を返します(時々必須、時々そうではありません)。
セットは(1)をO(1)で処理します。(2)も重要な場合は、順序付き出力用に別のリストと、メンバーシップチェック用にセットを保持します。2つのデータ構造、各々1つの仕事をしています。
レビュアーへの応答
プルリクエストがプロジェクトのグラフトラバーサル関数でMOAD-0001を修正します。レビュアーがコメントします:
> "セットは挿入順序を保存しません — これが動作を変更します。"
インタビュー分析パターン
予想される形式
アルゴリズム複雑性分析はソフトウェアエンジニアリングインタビューに表示されます。強い答えは4部構成のパターンに従います:
1. 現在の複雑性を述べる — 時間はO(?)、空間はO(?)。
2. なぜかを説明する — 責任のある具体的な構文を特定する(ネストされたループ、ループ内の線形スキャン、再帰的ブランチング)。
3. 最適化を提案する — 変更の名前とそれが導入するデータ構造またはアルゴリズムを命名します。
4. 新しい複雑性を述べる — 修正後、時間と空間の複雑性は何ですか?
例:
コード: [ループ内のリスト内のメンバーシップをチェックする関数]
現在: O(N²) — `item in seen_list` はN回の反復ごとにO(N)
最適化: seen_listをseen_setに置き換える(ハッシュセット)
その後: O(N) — セットメンバーシップチェックはO(1)このスキルはインタビューを超えて転送されます: 複雑性を認識したコードレビュー、アーキテクチャ設計、パフォーマンスデバッグ、セキュリティ監査。可変サイズの入力を処理するシステムはすべてそれから利益を得ます。
このレッスンはunhammingコースに転送され、これらの60以上のオープンソースプロジェクト全体で実際の欠陥調査にこの正確なパターンを適用しています。
インタビュー: 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