算法 - Linux下的diff命令复杂度多少？

Question

网上查了下diff的实现都是先求LCS，但是LCS复杂度我记的是$$O(N*M)$$的，我自己手动生成了100W个随机数字到两个文件里去，跑了下diff发现大约5s就出结果了，很好奇Linux下的diff是怎么实现？是优化了什么吗？

Answer 1

你可以到 gnu 官网去下载一份 diffutils 的源码研究，里面包含 diff，cmd 两个命令的实现。

我粗略看过源码，因为 diff 和 cmd 寻找差异都是以行为单位进行比对的，所以跟你想象的 LCS 算法是有区别的。

算法里的核心思路之一是哈希，每一行内容都被哈希成一个数值并放入一个开链式的哈希表中，比对时是从哈希表中快速找出另一个文件中匹配相等的行。

另外内部使用了 LCS 算法的变体，如果没有指定 --minimal，它查找到的结果是接近最优。官方文档里的复杂度介绍：

Unless the --minimal option is used, diff uses a heuristic by Paul Eggert that limits the cost to O(N^1.5 log N) at the price of producing suboptimal output for large inputs with many differences.

当差异非常小时，这里算法的复杂度接近O(N)，并且N为行的数量。执行上，几乎是仅对两个文件扫描一遍的速度，因为从磁盘读文件的时间比往往计算多。

Answer 2

你可以看一下linux源代码 应该就知道它怎么实现的了