C#中的LCS基础差异库
4.98/5 (18投票s)
这是一个为Code Project“精瘦而强大”的差异引擎竞赛编写的LCS基础差异库。
引言
我写这篇文章主要是出于好玩，也是作为 CodeProject 的 精简高效大赛 的参赛作品，比赛主题是编写一个文本差异工具。该库和演示应用程序都使用 VS 2010 Beta 版用 C# 编写，并在 64 位 Windows 7 RC 机器上进行了测试。到目前为止提交的一些文章并没有真正意义上进行差异比较，这给了我更大的动力去写一个真正标准的差异比较工具。我主要参考了 维基百科上关于 LCS 算法的条目，但也参考了 这篇文章（大学讲义）。我将该类命名为 SimpleDiff<T>，因为虽然它确实进行了基于 LCS 的标准差异比较，但可能还可以进一步优化，尽管我已经应用了一些基本的优化。
性能/内存信息
该实现旨在更“高效”而非“精简”，主要目标是编写一个速度相对较快的差异引擎。这并不意味着它不能做得更快，也不意味着它不能在不严重牺牲速度的情况下做得更精简。对于 CodeProject 提供的测试文件，这里是五次迭代的计时结果以及平均值。
| 35.0069 毫秒 | 33.3978 毫秒 | 34.1942 毫秒 | 34.9919 毫秒 | 34.2274 毫秒 |
平均：34.3636 毫秒
测试在具有 12 GB RAM 的 64 位 Core i7 机器上进行。
内存使用量（字节）可能不如 C++ 应用程序或未将两个文件完全加载到内存中的应用程序那样令人印象深刻。
| 分页内存 | 6,492,160 |
| 虚拟内存 | 0 |
| 工作集 | 6,766,592 |
不出所料（考虑到 12 GB RAM），虚拟内存使用量为 0。但工作集（增量）为 6.7 MB。占用内存最多的两个因素是我们在整个过程中将两个文件都存储在内存中，以及 LCS 矩阵对于任何非平凡大小的文件来说都可能非常大。我已经考虑过一个不完全加载任何一个文件的版本，但我无法想到一种合理的方法来避免性能下降（这总是伴随着频繁的磁盘读写以获取/查找数据）。
内存计算说明 |
内存消耗是使用 Process 类的 PeakWorkingSet64 和相关属性计算的。我获取了一次值，调用了代码，然后再次读取值并计算了增量。为了考虑 JIT 内存，我们创建了 diff 类一次，但在计算内存之前不使用它。 |
使用演示应用程序
演示应用程序接受 2 个参数，源文件和目标文件（或您喜欢的左文件和右文件）。它会打印出所有行，并使用 **++** 前缀表示添加到左文件的行，使用 **--** 前缀表示从左文件删除的行。这里有一些屏幕截图，显示了它在 Chris M 的示例文件以及我的简单测试文件上的运行情况。
如果您想知道行号，请注意，此显示是调用程序的函数，我的 diff 库实际上不提供任何输出 - 它只提供一个调用者可以挂钩的事件。对于我的控制台应用程序，我选择模仿 Unix diff 程序（尽管不完全相同），但添加行号非常简单。编写 WPF 或 WinForms 界面来使用这个库同样简单。
类设计
这是一个泛型类，泛型参数指定了可比较项的类型。在我们的例子中，因为我们要比较文本文件，所以它将是 System.String（代表一行文本）。使用该类大致如下：
leftLines = File.ReadAllLines(args[0]);
rightLines = File.ReadAllLines(args[1]);
var simpleDiff = new SimpleDiff<string>(leftLines, rightLines);
simpleDiff.LineUpdate += simpleDiff_LineUpdate;
simpleDiff.RunDiff();
Console.WriteLine(simpleDiff.ElapsedTime);
只有一个构造函数，它接受两个数组 - 一个用于左实体，一个用于右实体。
public SimpleDiff(T[] left, T[] right)
{
_left = left;
_right = right;
InitializeCompareFunc();
}
InitializeCompareFunc 设置比较器 delegate，该委托定义为：
private Func<T, T, bool> _compareFunc;
我为 String 进行了特殊处理，以便获得最快的可用比较。
private void InitializeCompareFunc()
{
// Special case for String types
if (typeof(T) == typeof(String))
{
_compareFunc = StringCompare;
}
else
{
_compareFunc = DefaultCompare;
}
}
/// <summary>
/// This comparison is specifically
/// for strings, and was nearly thrice as
/// fast as the default comparison operation.
/// </summary>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
private bool StringCompare(T left, T right)
{
return Object.Equals(left, right);
}
private bool DefaultCompare(T left, T right)
{
return left.CompareTo(right) == 0;
}
还有一个公共事件，每行都会触发一次：
public event EventHandler<DiffEventArgs<T>> LineUpdate;
public class DiffEventArgs<T> : EventArgs
{
public DiffType DiffType { get; set; }
public T LineValue { get; set; }
public DiffEventArgs(DiffType diffType, T lineValue)
{
this.DiffType = diffType;
this.LineValue = lineValue;
}
}
public enum DiffType
{
None = 0,
Add = 1,
Subtract = 2
}
在演示应用程序中，它以一种非常简单的方式处理。但对于更具 UI 风格的应用程序，可能性是无限的。
static void simpleDiff_LineUpdate(object sender, DiffEventArgs<string> e)
{
String indicator = " ";
switch (e.DiffType)
{
case DiffType.Add:
indicator = "++";
break;
case DiffType.Subtract:
indicator = "--";
break;
}
Console.WriteLine("{0}{1}", indicator, e.LineValue);
}
当调用 RunDiff 时，最重要且最耗时的代码部分会被执行一次。这就是我们为两个数组计算 LCS 矩阵的地方。但在那之前，作为一种优化，有一些代码会查找差异数组开头或结尾的任何潜在跳过的文本。我们可以安全地这样做的原因是，如果相同的行从两端删除，并且对中间部分计算 LCS，那么我们可以加回修剪的内容以获得原始数组对的 LCS。如果这还不清楚，请考虑以下两个字符串（想象我们在比较字符而不是字符串）：
abchijkxyz and abchujkwxyz
如果我们从左边删除 *abc*，从右边删除 *xyz*（针对两个字符数组），我们会得到：
hijk and hujkw.
这两个字符数组的 LCS 是 *hjk*。现在将删除的项加回到两端，我们得到：
abchjkxyz
这就是原始字符数组对的 LCS。我在这里应用了相同的概念。此方法计算可以跳过内容开头的任何项：
/// <summary>
/// This method is an optimization that
/// skips matching elements at the start of
/// the arrays being diff'ed
/// </summary>
private void CalculatePreSkip()
{
int leftLen = _left.Length;
int rightLen = _right.Length;
while (_preSkip < leftLen && _preSkip < rightLen &&
_compareFunc(_left[_preSkip], _right[_preSkip]))
{
_preSkip++;
}
}
现在计算了跳过后的部分（小心避免与跳过前的部分重叠，这进一步提高了性能）。
/// <summary>
/// This method is an optimization that
/// skips matching elements at the end of the
/// two arrays being diff'ed.
/// Care's taken so that this will never
/// overlap with the pre-skip.
/// </summary>
private void CalculatePostSkip()
{
int leftLen = _left.Length;
int rightLen = _right.Length;
while (_postSkip < leftLen && _postSkip < rightLen &&
_postSkip < (leftLen - _preSkip) &&
_compareFunc(_left[leftLen - _postSkip - 1],
_right[rightLen - _postSkip - 1]))
{
_postSkip++;
}
}
接下来我们计算 LCS 矩阵：
/// <summary>
/// This is the core method in the entire class,
/// and uses the standard LCS calculation algorithm.
/// </summary>
private void CreateLCSMatrix()
{
int totalSkip = _preSkip + _postSkip;
if (totalSkip >= _left.Length || totalSkip >= _right.Length)
return;
// We only create a matrix large enough for the
// unskipped contents of the diff'ed arrays
_matrix = new int[_left.Length - totalSkip + 1, _right.Length - totalSkip + 1];
for (int i = 1; i <= _left.Length - totalSkip; i++)
{
// Simple optimization to avoid this calculation
// inside the outer loop (may have got JIT optimized
// but my tests showed a minor improvement in speed)
int leftIndex = _preSkip + i - 1;
// Again, instead of calculating the adjusted index inside
// the loop, I initialize it under the assumption that
// incrementing will be a faster operation on most CPUs
// compared to addition. Again, this may have got JIT
// optimized but my tests showed a minor speed difference.
for (int j = 1, rightIndex = _preSkip + 1;
j <= _right.Length - totalSkip; j++, rightIndex++)
{
_matrix[i, j] = _compareFunc(_left[leftIndex], _right[rightIndex - 1]) ?
_matrix[i - 1, j - 1] + 1 :
Math.Max(_matrix[i, j - 1], _matrix[i - 1, j]);
}
}
_matrixCreated = true;
}
内联注释应该是不言自明的。有趣的是，我对 JIT 优化器会处理什么的假设被证明是相当不准确和模糊的。当然，我没有进行足够详细的测试来得出任何严肃的结论，但为了安全起见，最好自己进行一定程度的优化，而不是总是想着，“嘿，JIT 优化器会处理那个”。一旦 LCS 计算完成，剩下要做的就是遍历矩阵并根据需要触发事件，同时还要记住遍历任何跳过的条目。
for (int i = 0; i < _preSkip; i++)
{
FireLineUpdate(DiffType.None, _left[i]);
}
int totalSkip = _preSkip + _postSkip;
ShowDiff(_left.Length - totalSkip, _right.Length - totalSkip);
int leftLen = _left.Length;
for (int i = _postSkip; i > 0; i--)
{
FireLineUpdate(DiffType.None, _left[leftLen - i]);
}
我没有花太多时间优化 ShowDiff ，因为我的性能分析显示它不像 LCS 计算那样耗时。执行时间的 87% 花在了 LCS 矩阵循环上。
/// <summary>
/// This traverses the elements using the LCS matrix
/// and fires appropriate events for added, subtracted,
/// and unchanged lines.
/// It's recursively called till we run out of items.
/// </summary>
/// <param name="leftIndex"></param>
/// <param name="rightIndex"></param>
private void ShowDiff(int leftIndex, int rightIndex)
{
if (leftIndex > 0 && rightIndex > 0 &&
_compareFunc(_left[_preSkip + leftIndex - 1],
_right[_preSkip + rightIndex - 1]))
{
ShowDiff(leftIndex - 1, rightIndex - 1);
FireLineUpdate(DiffType.None, _left[_preSkip + leftIndex - 1]);
}
else
{
if (rightIndex > 0 &&
(leftIndex == 0 ||
_matrix[leftIndex, rightIndex - 1] >= _matrix[leftIndex - 1, rightIndex]))
{
ShowDiff(leftIndex, rightIndex - 1);
FireLineUpdate(DiffType.Add, _right[_preSkip + rightIndex - 1]);
}
else if (leftIndex > 0 &&
(rightIndex == 0 ||
_matrix[leftIndex, rightIndex - 1] < _matrix[leftIndex - 1, rightIndex]))
{
ShowDiff(leftIndex - 1, rightIndex);
FireLineUpdate(DiffType.Subtract, _left[_preSkip + leftIndex - 1]);
}
}
}
哈希说明
许多 C++ 实现会在比较项之前计算其哈希值。在我们的例子中，因为我们正在使用 .NET，这实际上是一种性能下降，因为我们会失去字符串驻留的好处。在大多数情况下，大部分行都是相同的（在实际场景中，文件版本之间只有一小部分行发生了更改）。而且由于我们使用 Object.Equals，它首先进行引用比较，并且由于相同的字符串被驻留，因此此比较速度极快。我们变慢的地方是当我们比较可能在行末尾只差一个字符的长行时 - 这将给我们最坏情况下的误比较时间。
结论
我最初曾考虑用 C++/CLI 编写，这样我就可以混合类型 - 这在创建数组时特别有用。 .NET 数组的一个大缺点是它是零初始化的，虽然这是任何 CPU 通常可以执行的最快操作之一，但由于数组的大小很大，它仍然很耗时。通过使用本机数组，我可以避免这种情况。但几分钟后，缺乏 IntelliSense 让我抓狂，我放弃了，回到了 C#。也许如果我有时间，我会编写另一个版本，它可能会在本机代码中执行部分计算，而 C# 代码可以 P/Invoke 它，尽管这本身可能会带来效率问题。无论如何，任何建议和批评都非常欢迎。
历史
- 2009 年 8 月 20 日
- 文章首次发布
- 2009 年 8 月 24 日
- 添加了二进制下载
- 添加了计时/内存使用统计