Myers diff 在大改写上会退化，作者用编辑区间把它提速数个数量级

_jzhao · x · 2026-07-22

这篇迷你博客解释了：为什么默认的 Myers unified diff 算法在“大改动”场景下会退化，以及如何利用类似 strreplace 工具拿到的编辑区间，把 diff 计算加速几个数量级。

文章先用图示说明 edit graph：当大规模重写时，几乎没有可匹配的字符，搜索带会不断变宽，最后覆盖整个图。作者强调，agent 工作流的编辑模式和人类完全不同——它们常常一次性改写成千上万行代码，导致 Myers 逼近二次复杂度。文中还提到，一个退化的 diff 就曾花了 4.3 秒，直接把整个 agent 卡住。