NLineDiffConsole：文本文件的控制台 Diff 实现

4.73/5 (7投票s)

2009 年 8 月 31 日

2分钟阅读

32154

618

Lean and Mean 比赛的参赛作品

引言

本文是为精简高效竞赛的参赛作品，该竞赛于 2009 年 8 月在 Code Project 上进行。

这是我对先前参赛作品的控制台版本。因此，它也使用了具有线性空间优化的差异算法。我已在下载文件中包含原始论文。在这个版本中，我将内存需求减半，但算法保持不变。

更正：根据维基百科的说法，该算法由道格拉斯·麦克罗伊 (Douglas McIlroy) 在 70 年代初编写，而尤金·W·迈尔斯 (Eugene W. Myers) 只是在他的论文中描述了它。为此表示歉意。

如果 N = 第一个文件的行数，M = 另一个文件的行数，D = 不同行数，那么差异算法的时间复杂度为 O( (N+M) D )，空间复杂度为 O( N+M )。

这比 LCS 算法好得多，LCS 算法的时间和空间复杂度均为 O( N * M )。对于测试文件，N = 1784，M = 1789，D = 19。因此，在这种情况下，LCS 算法的复杂度比差异算法高出几个数量级，并且速度更慢。

我必须再次表达我对麦克罗伊算法的赞赏。我对它的了解越多，我就越印象深刻。我肯定无法发明出更好的东西！

演示是一个控制台应用程序，它使用差异实现，该实现位于单独的程序集中。演示将两个文件路径作为参数。它读取文件，计算差异，并显示结果和一些计时测量。在 program.cs 中有一个 #define，可以选择测量 Process.PeakWorkingSet64 的变化。

上面的截图显示了典型运行的计时结果。不包括 JIT 编译，时间约为 5.5 毫秒。包括 JIT 编译，总时间约为 32 毫秒。

算法使用的主数组现在略低于 30 KB，因此计算出的内存使用量为 420 KB 加上少量变化。

其他参赛作品测量 Process.PeakWorkingSet64 的变化，因此我也会这样做。测量结果差异很大，但 600-700 KB 的值很常见。