算法 - Linux下的diff命令复杂度多少?
本文介绍了算法 - Linux下的diff命令复杂度多少?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
网上查了下diff
的实现都是先求LCS,但是LCS复杂度我记的是$$O(N*M)$$的,我自己手动生成了100W个随机数字到两个文件里去,跑了下diff
发现大约5s就出结果了,很好奇Linux下的diff
是怎么实现?是优化了什么吗?
解决方案
你可以到 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为行的数量。执行上,几乎是仅对两个文件扫描一遍的速度,因为从磁盘读文件的时间比往往计算多。
这篇关于算法 - Linux下的diff命令复杂度多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文