NLineDiff：文本文件的 Diff 实现

• 下载二进制文件 - 55.59 KB
• 下载源代码 - 64.66 KB
• 下载Diff论文 - 60.57 KB

引言

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

我实现了一个 Eugene W. Myers 的 diff 算法的轻微变体，并使用了下载中列出的论文中的线性空间优化。

该算法的时间复杂度为 O(ND)，空间复杂度为 O(N)，其中

N = number of lines in FileA + number of lines in FileB
D = number of different lines

输出使用一个简单的 WinForms WebBrowser 控件进行渲染。

结果

对于测试文件，N = 3,573 且 D = 19。在我的 2.5 GHz 机器上，解决方案大约需要 5 毫秒，并使用大约 450 KB 的内存。

时间

大部分时间都花在从磁盘读取文件并将它们拆分成 string 数组。使用 File.ReadAllText 需要大约 1.7 毫秒读取两个文件，而 File.ReadAllLines 需要大约 1.9 毫秒。使用 File.OpenRead 和 StreamReader.ReadLine 的执行时间几乎相同。

从结果构建 HTML 也会花费一些时间。仅显示更改需要大约 0.15 毫秒，如果也包含公共行，则上升到 2.6 毫秒。我选择包含公共行以提供更有用的结果。

至于 diff 算法本身，100 次迭代的平均时间约为 0.33 毫秒。单次运行的时间显然比平均时间变化更大，但通常需要大约 0.4 毫秒。

这些操作的总时间为 1.9 + 0.4 + 2.6 ≈ 5 毫秒。

在计时运行之前运行一次 diff，以允许 JIT 编译器工作。这大约需要 27 毫秒，这比计算时间要长得多。我认为不包括这个时间是合法的，正如 Chris 在笔记中说的那样

如果你不同意，你可以加上 JIT 时间，总时间约为 32 毫秒。

空间

使用的空间是三个区域的总和

• 文件被加载到内存中，这大约需要 360 KB。
• 它们被拆分成 string 数组，这大约需要 30 KB。
• 算法本身使用一个 int 数组，大约需要 60 KB。

总和给出的最大工作内存为 450 KB。

我看到其他条目使用了 Process.PeakWorkingSet64，但这主要衡量框架使用了多少内存。运行此代码报告 Thread.Sleep 调用使用了大约 900 KB，这显然是不正确的。

static void Main( string[] args )
{
  var p = Process.GetCurrentProcess();
  var peak = p.PeakWorkingSet64;

  Thread.Sleep( 1000 );

  p.Refresh();

  Console.WriteLine( String.Format( "peak: {0:N0} bytes", p.PeakWorkingSet64 - peak ) );
}

Using the Code

二进制文件是一个单一的可执行文件，其中包含作为嵌入式资源包含的测试文件。它被配置为加载这两个文本并将它们拆分成 string 数组，然后对 diff 算法进行计时。

您还可以在命令行上提供两个文件路径来使用这些文件。

源代码包含一些在 Form1.cs 中被注释掉的变体。您可以编辑此文件并重新编译，以验证您机器上的时间和空间测量值。

关注点

Myers 的算法是一件艺术品，我非常喜欢学习它。我花了大约一周的时间来实现它，因为这花了我很长时间才完全理解它。它绝对值得单独写一篇文章（即将推出！）。

历史

• 2009 08 27：第一版
• 2009 08 28：修复了当 D=1 && Δ 为偶数时与重叠对角线相关的错误