diff アルゴリズム徹底解説 - Myers・patience・histogram は何が違うのか
約36分
git diff の裏で動く diff アルゴリズムを、LCS と編集距離、編集グラフ、Myers の O(ND) アルゴリズム、patience diff、histogram diff の順に解説します。Python のミニ実装と、git diff --diff-algorithm の実測で「最小」と「読みやすい」が別物であることを確かめます。
git diff の裏で動く diff アルゴリズムを、LCS と編集距離、編集グラフ、Myers の O(ND) アルゴリズム、patience diff、histogram diff の順に解説します。Python のミニ実装と、git diff --diff-algorithm の実測で「最小」と「読みやすい」が別物であることを確かめます。
動的計画法(DP)を、部分問題の重なりと最適部分構造という2条件から解説。メモ化(トップダウン)とテーブル化(ボトムアップ)の違い、フィボナッチ・コイン・0-1ナップサック・編集距離の実装と計算量、状態と遷移の設計手順まで、初学者向けにPythonコードで具体的に整理します。