LPTextFileDiff：另一个文本文件比较实用程序。
4.89/5 (38投票s)
我的作品，参加精简高效编程竞赛。
|
|
|
Content
引言
这是我提交给 The Code Project 的 精简高效竞赛 的参赛作品，旨在编写一个高效的文本差异工具。
问题描述如下：给定两个文本文件 file1 和 file2，其中 file2 是 file1 的一个小版本。编写一个程序，生成并显示差异描述，即生成如何将 file1 转换为 file2 的指令，并以最经济的方式实现，包括经过时间和内存使用（指定为 .NET 启动所需内存之外的数据量）。
我的解决方案基于 LCS 算法，并进行了两项个人修改，以及一些精简高效的编程技巧。生成的程序紧凑且速度非常快，并且可以完美地处理任意大小的文件。
初步分析
为了简单起见，我们将逐行进行比较，并将文本行表示为一个字母；相同的行表示为相同的字母，不同的行表示为不同的字母。
一个简单的方法是同时读取两个文件，并逐行进行比较；只要两个文件中的行相同，我们就可以毫无问题地继续。然而，一旦出现不匹配，我们就会陷入困境，因为我们必须决定 file1 中的当前行是否已消失，或者 file2 中的当前行是否已插入，或者一行已编辑成为另一行。
示例
file1 = A B C D E F
file2 = A B X Y D E F Z
我们识别 A=A，B=B，然后遇到 C 和 X；现在我们应该决定 C 是否已被删除，或者 X 是否已被插入，或者 C 是否已修改为 X（这可以通过删除 C 并插入 X 来实现）。根据所使用的算法，如果我们做出一个不幸的决定，我们可能会永远无法同步，并完全错过两个文件中的 DEF 周围的共同点。
在上面的例子中，file1 和 file2 的共同部分（在两个文件中按相同顺序出现）将是“ABDEF”。file1 = A B C D E F
file2 = A B X Y D E F Z
LCS = AB DEF
edit = AB -C +X +Y DEF +Z
所以编辑指令可以是“AB -C +X +Y DEF +Z”，它的意思应该是：从 file1 开始，复制行直到没有加号或减号；在减号后面删除该行，在加号后面插入该行。显然可以有多种等效的解决方案，在示例中，序列 -C +X +Y 可以有多种方式重新排列，只要 X 在 Y 之前即可。
我们必须得出结论，仅仅扫描文件一次，不向前看，注定会失败。而且情况会更糟，甚至更糟，当存在重复行时，如下例所示
file3 = ABACADA
file4 = AAAAACADAEA
如果我们匹配 file4 的前四个 A 与 file3 的所有 A，那么在到达 C 之前，我们将用完 A，因此我们无法发现共同的“CADA”序列。所以贪婪算法不一定会产生最佳解决方案。
现状
这个问题当然不是新的，它已经被反复研究过。也许这个领域中最知名的算法是 LCS 算法，其中 LCS 是“最长公共子序列”的缩写。我不会在这里重复理论，它在很多地方都有很好的 记录。
LCS 算法使用一个二维矩阵，有 N1 行和 N2 列，其中 N1 和 N2 是文件中的行数，所以它可能非常大。基本上，矩阵是一个游乐场，你必须从左上角（两个文件的开头）移动到右下角（两个文件的结尾），通过向右、向下或对角线（向下和向右）移动一步，分别对应于删除、插入和复制操作。当然，只有当两个文件在此位置的行相同时，才能进行对角线移动（“复制”）。N1*N2 矩阵是基于 N1*N2 字符串比较计算的，顺序正确，并累积中间结果。
一旦矩阵被填充，就需要根据一些规则从左下角回溯到右上角，并记录下所走的路径。然后这些记录按相反的顺序播放，得到一个类似于
edit = AB -C +X +Y DEF +Z
我们之前看到的字符串。
[自 V1.1 起新增段落] 还有一篇著名的 Eugene W. Myers 的文章，题为“O(ND) 差异算法及其变体”。我还没有详细研究过它；乍一看，它看起来非常详尽，但对于手头的问题来说有点大材小用。
实际分析，以及第一次改进
“精简高效”挑战的解决方案应该是非常经济的（包括 CPU 周期和内存字节），并且具有良好的可伸缩性，因此我们将尝试避免
- 将所有文本一次性加载到内存中；
- 使用一个二维矩阵，其维度随着文件大小的增长而增长（这对于 LCS 等算法来说很典型）。
此外，为了获得最佳性能，我们将尝试
- 只读取文件一次；
- 使用“滑动窗口”技术，即根据部分文件内容（当前位置周围的行）而不是完整文件内容（由于我们的选择 #1 和 #3，我们从未拥有完整文件内容）做出决策。
- 并实时输出结果。
因此，第一个挑战是推导出某种“局部 LCS 算法”。这是主要改进 #1。下面是它的工作原理
- 我们固定一个“窗口大小”（或简称 WS），即我们愿意为每个文件存储的（最大）行数；
- 我们设置一个 WS*WS 矩阵，与 LCS 算法的做法完全一样（稍后会有转折）；
- 我们从左下角回溯到右上角，记下路径，然后执行它，也就是说，我们只生成编辑指令，直到还有匹配（即对角线步）。一旦达到最后一个匹配，我们不会发出剩余的删除和插入，而是同时推进两个文件。
上面的方法应该效果很好，只要匹配之间的距离**永远**不超过 WS，即选定的窗口大小。“效果很好”的意思是，如果矩阵中只有一个匹配项，我们也不会考虑其他匹配项，因此 file3-file4 示例就会出现问题（这需要窗口大小为 2！）。通过选择比我们预期的最大差异高两倍的窗口大小，我们解决了大部分局部问题。
总结一下：我们从两个文件中读取 WS 行，在上面应用局部 LCS，并生成相应的编辑指令；但是，一旦我们到达当前窗口对中的最后一个匹配项，我们就推进两个文件，直到我们再次拥有两个文件的 WS 行，从我们停止发出指令的地方开始。然后我们重复这个过程，直到所有文件数据都被消耗完，此时我们不会在最后一个匹配项处停止，而是根据文件数据继续进行剩余的删除和插入。
注意：我们必须包含一个明显的改进；当两个窗口以几行匹配开始时，我们立即将它们称为匹配，然后继续，因为为这些行计算 LCS 矩阵数据没有意义。这相当于在我们的第一个示例中直接接受“AB”作为编辑指令的开头。
第二次改进
常规 LCS 中有一些愚蠢的事情：我看到的所有实现（好吧，只有几个），都是从左上角到右下角构建矩阵，然后回溯到左上角记录笔记，然后处理这些笔记（这对应于另一个从左上角到右下角的旅程）。所以从某种意义上说，矩阵被遍历了三次。
显然，文件差异算法基本上是对称的，你也可以从文件的末尾开始，然后向上移动到它们的开头。最终结果可能不同（即不相同），但它同样经济，因为有很多好的解决方案（记住我们在“-C +X +Y”中可以选择的排列）。
所以第二个改进是：从右下角到左上角构建 LCS 矩阵（再次，由于我们使用滑动窗口，它是从窗口底部到窗口顶部）；然后我们从上到下“回溯”，但是我们不再需要存储任何东西，因为我们可以立即按正确的顺序生成编辑指令。显然，这可以节省一些存储空间、一些周期和一些代码。
设计和实现
我基本上创建了三个类
- 一个 Document 类，表示一个文本文件，并实现一个具有有限长度的文本行列表；Document 可以从 0 到 WS-1 索引，并生成滑动窗口中可见的文本行。所以它基本上是一个通用的字符串列表，知道如何通过读取文件来填充自己。
- 一个 LPTextFileDiff 类，实现实际的文件比较；
- 一个 LPTextFileDiffTester 类，提供一个控制台应用程序的 Main 方法，我们需要测试所有内容的正确性和性能。
整个应用程序的源代码只包含两个文件：一个用于 Document 和 LPTextFileDiff（约 360 行代码）；另一个用于 LPTextFileDiffTester（约 140 行代码）。
编码风格一如既往地符合我的习惯，避免不必要的空格以及大多数空白行或仅包含一个左大括号的行。我更喜欢在单个屏幕上看到尽可能多的代码。
以下是一些编码细节，其中一些可能被认为是有点“精简”的
- Document 类实现了 IDisposable，所以如果你使用 `using` 语句创建 Document 实例，文件将被自动关闭；由于我们需要两个实例，并且它们可以在一个类型声明语句中声明，我们将两个 `using` 语句合并成一个，如下所示：`using (Document doc1=new Document(...), doc2=new Document(...)) {...}`
- LPTextFileDiffTester 类使用 `Stopwatch` 实例来测量执行时间，具有毫秒级分辨率和类似的精度。
- LPTextFileDiffTester 类使用 `Process.PeakWorkingSet64` 来获取迄今为止的峰值工作集。因此，在调用比较之前和之后，都会有一段代码像这样。
Process process = Process.GetCurrentProcess(); process.Refresh(); long peakWorkingSet64=process.PeakWorkingSet64;
这样，我们就可以确定由于比较引起的工作集增加，而与 .NET 启动所需的内存量无关。顺便说一句，我还调用了三次 `GC.Collect()`，以确保我没有持有任何仍可收集的内存，因为这会使测量结果失真。 - 比较器代码中也埋藏了一些 `GC.Collect()` 调用。在那里有它们并非必需（通常我始终建议不要显式调用 GC.Collect()），但是它们允许将平衡从最高速度稍微移向最小内存占用。我将在下面再次讨论这一点。
与我通常的行为相反，我没有走得太远，将二维数组打碎成一维数组；我也没选择使用指针。我确信滑动窗口和颠倒的 LCS 技术已经足够好了。
Document 类非常简单
public class Document : IDisposable {
private int windowSize;
private static int counter=0;
private int docNumber;
private StreamReader sr;
private List list;
private int lineNumber=0;
public Document(int windowSize, string filename) {
this.windowSize=windowSize;
docNumber=++counter;
sr=File.OpenText(filename);
list=new List(windowSize);
}
public bool ReadMoreLines() {
bool someLinesAdded=false;
while (list.Count<windowSize) {
string s=sr.ReadLine();
if (s==null) break;
list.Add(s);
someLinesAdded=true;
}
return someLinesAdded;
}
public int Count { get { return list.Count; } }
public string this[int index] { get { return list[index]; } }
public string DropLine(out int lineNumber) {
string text=list[0];
list.RemoveAt(0);
lineNumber=++this.lineNumber;
return text;
}
public void Dispose() {
if (sr!=null) sr.Close();
}
}
LPTestFileDiff 类包含一个大的构造函数，没有公共方法，以及一些生成输出的小型私有方法；小型方法非常明显，可以在下载文件中找到。然而，大部分代码都在公共构造函数中。基本上有一个主要的 for 循环，它会遍历文件，然后是一些代码来重新填充滑动窗口，然后是 LCS 构建、回溯以及编辑指令的生成。
public class LPTextFileDiff {
private StreamWriter streamWriter;
private int lastReport;
private bool logMatchingLines;
private int linesMatched;
private int linesRemoved;
private int linesInserted;
public LPTextFileDiff(string file1, string file2, int windowSize, StreamWriter streamWriter, bool logMatchingLines) {
this.streamWriter=streamWriter;
this.logMatchingLines=logMatchingLines;
output2("File1="+file1);
output2("File2="+file2);
output2("window size="+windowSize+" lines");
using (Document doc1=new Document(windowSize, file1), doc2=new Document(windowSize, file2)) {
bool slidingWindowTooSmall=false;
for (int loop=1; ; loop++) {
bool moreDataLoaded1=doc1.ReadMoreLines();
bool moreDataLoaded2=doc2.ReadMoreLines();
bool moreDataLoaded=moreDataLoaded1 || moreDataLoaded2;
details("loop="+loop+" more="+moreDataLoaded1+" "+moreDataLoaded2);
if ((loop & 0x3)==0) GC.Collect(); // trade best speed for smallest working set
// compare using LCS algorithm and matrix
int NW1=doc1.Count;
int NW2=doc2.Count;
if (NW1+NW2<=0) break;
bool matchedSome=false;
// if multiple matches, remove them all but one
while (doc1.Count>=2 && doc2.Count>=2 && doc1[0]==doc2[0] && doc1[1]==doc2[1]) {
reportCopy(doc1, doc2);
matchedSome=true;
}
if (!matchedSome) {
int[,] LCS=new int[windowSize+1, windowSize+1];
bool[,] match=new bool[windowSize+1, windowSize+1];
// calculate LCS matrix backwards, starting at (NW1-1,NW2-1)
// add a dummy bottom row and right column, initialized to zero
for (int i2=0; i2<=NW2; i2++) LCS[NW1, i2]=0;
for (int i1=0; i1<=NW1; i1++) LCS[i1, NW2]=0;
for (int i1=NW1-1; i1>=0; i1--) {
for (int i2=NW2-1; i2>=0; i2--) {
if (doc1[i1]==doc2[i2]) {
LCS[i1, i2]=LCS[i1+1, i2+1]+1;
match[i1, i2]=true;
} else {
// largest neighbour (bottom or right) without Math.Max
LCS[i1, i2]=LCS[i1, i2+1]>LCS[i1+1, i2]?LCS[i1, i2+1]:LCS[i1+1, i2];
}
}
}
// now "backtrack" forward and emit results
int matchingLines=LCS[0, 0]; // bottom left element equals number of matching lines
if (matchingLines==0) {
// not a single match, so output one line of each, and try again
while (doc1.Count!=0) reportRemoval(doc1);
while (doc2.Count!=0) reportInsertion(doc2);
if (!moreDataLoaded) break;
if (!slidingWindowTooSmall) {
slidingWindowTooSmall=true;
output2("ERROR: difference too large for sliding window");
}
} else {
for (int i1=0, i2=0; ;) {
// first test diagonal step, as this corresponds to a line match;
// if no match try either an insert or a delete
if (match[i1, i2]) {
reportCopy(doc1, doc2);
i1++;
i2++;
if (--matchingLines<1) break; // no more matches in current window
} else if (matchingLines==LCS[i1, i2+1]) {
reportInsertion(doc2);
i2++;
} else {
reportRemoval(doc1);
i1++;
}
}
}
}
}
// make sure all remaining text gets processed
do { while (doc1.Count!=0) reportRemoval(doc1); } while (doc1.ReadMoreLines());
do { while (doc2.Count!=0) reportInsertion(doc2); } while (doc2.ReadMoreLines());
}
output2("");
output2("Statistics: "+linesMatched+" lines matched, "+linesRemoved+" removed, "+
linesInserted+" inserted");
}
}
我认为解释所有细节没有多大意义；如果你必须了解，一旦你熟悉了直接的 LCS，并且应用了我之前解释的修改，你就可以自己弄清楚。
我不会在这里展示 LPTextFileDiffTester 的代码；它都很直观，并且可以在下载文件中找到。
[自 V1.1 起新增段落] 注意：此处显示的代码来自 V1.0，是理解一切如何工作的最佳起点；下载中的实际代码由于进一步的增强（主要是动态窗口大小调整）和一些新的性能优化而略有不同。
动态窗口大小调整
[自 V1.1 起新增章节] 固定窗口大小的想法可能有点吓人；太小的值会导致无法找到最佳编辑路径；太大的值会浪费 CPU 周期和工作集内存。但是，没有什么能阻止我们动态调整窗口大小。因此，这是对 LCS 的第三个改进：从一个小窗口大小开始，并在需要时增加它。增加窗口大小非常简单，只需读取更多文本行，并执行更大的 LCS 算法。因此，我们决定实现一个可以将其初始窗口大小加倍，最多八次，所以最大窗口大小固定为原始大小的 256 倍（这仍然是用户可选的，并且默认值为 30 行）。我们没有实现自动窗口大小缩减，因为这可能有点棘手，而且其优点可能微乎其微：一旦两个文件存在较大的差异块，它们很可能还有更多的差异块，并且峰值工作集已经增长。
当然，现在关键部分是决定何时将窗口大小加倍。这也有一个简单的解决方案：我们定义一个最小（或阈值）值 T，表示滑动窗口中必须存在的匹配行数。T 本身是用户可选的，并且默认值为 10。因此，默认情况下，我们读取两个文件的 30 行；我们跳过所有相同的行，所以窗口中的第一行已知是不同的，然后我们执行 LCS，并要求最佳解决方案至少包含 T 行匹配。如果不是，我们就将窗口大小加倍并重新执行 LCS，直到成功为止；在极罕见的情况下，如果我们从未获得足够数量的匹配行，我们将生成删除和插入所有这些行的编辑指令，然后继续。
注意：动态窗口大小调整的实现不存在于上面的代码片段中；然而，它可以在下载的代码中找到。
已知限制
比较类旨在正确处理各种情况，因此输出结果必须是正确的；这一点毋庸置疑。大多数设计决策都受到了挑战中设定的典型用法以及提供的测试示例的启发。因此，在影响性能（周期和字节）的决策中，假设两个文件相当相似。
[列表在 V1.1 中更新] 这是我目前已知的限制列表
- 整个应用程序是面向行的，行要么相同，要么不同。没有花费精力去发现行之间的可能相似性，也没有去描述如何将 file1 中的一行编辑成 file2 中的一行。所以所有的输出都是：复制行，删除行，插入行。
- 该应用程序需要换行符来将输入文件分割成文本行；当没有回车符/换行符时，整个文件被解释为一行文本，唯一的结果是两个文件是否相同。
- 动态窗口大小调整是启发式的，不是严格的科学，所以没有 100% 的保证。生成的编辑指令预计始终是正确的，并且大多数情况下是最佳的；在特殊情况下，它们可能不是最优的，也就是说，描述的步骤比将 file1 转换为 file2 所必需的步骤更多。这些情况取决于差异块的高度（以及可能的距离），所有这些都相对于当时的窗口大小。虽然严格来说阈值 1 就足以获得良好的行为，但我将其默认值设置为 10，以便大多数时候都能获得最佳结果。只有通过大量测试用例使用该应用程序的经验才能确认上述陈述的有效性。
一些亮点
我坚信即使是一个精简高效的应用程序也应该有一个良好的用户界面；一点舒适性对开发者和用户都有好处。所以测试应用程序有一个命令行解析器，内置帮助，以及一些选项。帮助信息显示如下：
LPTextFileDiff version V1.1, by Luc Pattyn, August 2009
Compares two text files
usage: LPTextFileDiff [ /option ...] file1 file2
options:
/B = create big files (expand by 10, 100, 1000)
/N = generate an output file and open it with Notepad
/M = also list matching lines to the output file
/Q = wait for the user to hit a key before quitting
/S = optimize for speed (no GC.Collect)
/Tdd = change threshold to dd matching lines (minimum 1, default 10)
/Wdd = change initial sliding window size to dd lines (min 5, def 30)
其中一个选项启用了输出文件的生成，并在完成后使用记事本打开它；拥有一个真正的输出文件比必须从 DOS 窗口中选择所有内容并复制要舒适得多。另一个选项允许选择滑动窗口大小，所以当两个文件差异很大时，仍然可以使用更大的窗口大小进行尝试；我用窗口大小为 100 进行了测试，没有注意到执行速度有明显影响，但是工作集确实增加了。大文件选项生成六个文件，每个文件包含原始输入文件内容 10 到 1000 倍；这使得测试可伸缩性（见末尾）变得容易。
为了让开发者（也就是我）的生活更轻松，我还包含了一些额外的调试语句，以及几个控制它们的定义。这是一个例子，说明它是如何完成的：
#define WITHOUT_DETAILS_LOGGED // choose WITH or WITHOUT (default is WITHOUT)S
...
#if WITH_DETAILS_LOGGED
output2(s);
#endif
我本来可以使用命令行选项实现类似的功能，但这会使用户界面复杂化，并导致运行时检查，而当可能涉及大量数据时，我希望避免这种情况。
输出
该应用程序为每次插入或删除生成一行文本，并在序列中的每次更改（编辑指令的更改或行号的跳转）处插入一个空行。默认情况下，它不显示未更改的行。对于测试数据，会生成以下内容：
Jitted in XYZ msec
File1=grid1.html
File2=grid2.html
+++ 00041 : <H2>Version 2
+++ 00042 : <p>This is the modified version. There are 5 changes
+++ 00043 : <ul>
+++ 00044 : <li>A visible addition</li>
+++ 00045 : <li>A visible deletion</li>
+++ 00046 : <li>A visible text change</li>
+++ 00047 : <li>A linebreak removal</li>
+++ 00048 : <li>A non-visible change to the underlying HTML markup.</li>
+++ 00049 : </ul>
+++ 00050 : <p>Find them all as fast and as efficiently as you can.</p>
+++ 00172 : <TD><CODE lang="Text">gridctrl.cpp, gridctrl.h</CODE></TD>
00162 --- : <TD><CODE>gridctrl.cpp, gridctrl.h</CODE></TD>
+++ 00191 : <TD noWrap><CODE>GridDropTarget.cpp, GridDropTarget.h</CODE><...
00181 --- : <TD noWrap><CODE>GridDropTarget.cpp, GridDropTarget.h</CODE><...
00182 --- : <TD>Grid control OLE drag and drop target. Only necessary if ...
01241 --- : <TD noWrap><CODE>void SetShadedPrintOut(BOOL bEnable = TRUE)<...
01242 --- : <TD class=smallText width="100%">If TRUE, colored cells will ...
01243 --- : FALSE, all text prints as black on white.</TD></TR>
01244 --- : <TR vAlign=top>
Statistics: 1777 lines matched, 7 removed, 12 inserted
Window sizes: initial=30, final=30; threshold=10, minimum matches=20
LPTextFileDiff done (used XYZ msec and working set increase of XYZ KB)
文本行前面有两列，包含行号或符号。第一列保存 file1 中行的行号（对于不存在的行则为 +++）；第二列保存 file2 中行的行号（对于不存在的行则为 ---）。所以 `+++ 00172 : gridctrl...` 表示删除第 162 行。当选择 /M 选项时，匹配的行将显示两个行号（仅在可选输出文件中显示，不在控制台上显示，因为这会导致大量滚动和减速）。
注意：在控制台上，行会被截断，以便长行不会因为换行而导致额外的滚动；在可选的输出文件中，不会进行截断。
性能数据
显然，性能测量结果取决于许多因素。为了获得最佳条件，必须
- 使用发布版本，而不是调试版本；
- 在 Visual Studio 之外运行；我建议创建一个批处理文件并双击它；我通常包含
echo off
LPTextFileDiffTester.exe
LPTextFileDiffTester.exe grid1.html grid2.html
pause
因此，第 2 行显示帮助信息，第 3 行执行实际测试，第 4 行在关闭“DOS 窗口”之前等待用户确认（可选的 /Q 也会这样做）。
- 应该给 DOS 窗口足够的高度，以确保它不需要滚动，因为这可能会完全破坏性能。或者，可以通过在 DOS 命令后面附加 `>outfile.txt` 将输出重定向到一个文件。
以下是结果：在一台功能相当强大的笔记本电脑（Dell Inspiron 1720，Vista），配备 2400 GHz 的 Intel Core 2 Duo T8300 处理器上，LPTextFileDiffTester 仅需
6.4 毫秒（经过时间）和324 千字节（工作集增加），不带 /S 选项
6.1 毫秒（经过时间）和928 千字节（工作集增加），带 /S 选项
不包括经过的 JIT 编译时间8.4 毫秒
[列表在 V1.1 中重新制作] 更多评论
- 经过时间会有些波动；有必要执行几次运行才能对实际耗时有正确的印象。
- 经过时间的重要部分花在向控制台写入，这似乎是一个相当慢的设备；其速度可能取决于其窗口高度、缓冲区高度、颜色深度等，所有这些都是目标机器的特征；可以通过将输出重定向到一个文件来消除控制台时间，但是这违反了计算和显示差异的要求。
- 如果这段代码要用在网站上，它可能需要每次都进行 JIT 编译，在这种情况下，JIT 和运行时间的总和更相关；这将产生不到 15 毫秒的总经过时间。
GC.Collect() 调用用于用一些 CPU 周期换取更小的工作集；它们的使用是可选的，指定 /S 选项会禁用它们。- 该算法在文本行数上基本是线性的：对于任何给定的窗口大小，将输入文件大小加倍，LPTextFileDiff 的运行时间应该翻倍，不多不少；内存需求应该是恒定的（假设有一些 `GC.Collect()` 调用，否则它会一直增长直到 GC 自动运行）。作为测试案例，我将测试文件连接了 1000 次（生成两个 90MB 文件，参见 /B 选项），并在不到 2.3 秒的时间内进行了比较（输出已重定向），工作集增加量仍然不超过 440KB。读取所有文本行或计算完整 LCS 矩阵的算法在此测试中需要数十兆字节或数百兆字节。
事后分析
当一切都运行良好并且看起来不错时，我显然又进行了一次分析，以检查我可能忽略的任何内容。
我最初没有研究的一个维度是多线程：在多核 CPU 上，只有一核会贡献文件比较，但 Windows 可能会按需预取文件。总之，使用多个线程会相当困难，因为所有内容本质上都必须按顺序进行：填充 LCS 矩阵、回溯矩阵、生成编辑指令、滑动窗口。它们总是要互相等待，没有多少并行处理的机会。所以起初我放弃了这个想法。
[自 V1.1 起新增段落] 我后来进行了一些实验；首先我验证了一个完整的握手往返线程切换在我的 PC 上大约需要 10 微秒。所以如果我只需要几百次这样的往返，我就可以节省几毫秒，这意味着我每次需要加载和存储大约 20 行文本。或者，我可以假设总会有一个多核 CPU，为什么不让另一个核心免费做一些工作呢。我实现了两种这样的方案，但它们从来没有比单线程的简单方法更快。主要问题仍然是算法固有的顺序性：一旦一些行从列表中删除，我就需要新的文本行来计算 LCS。实际上这并不完全正确：我可以在行进来的时候开始填充 LCS 矩阵，但这会极大地破坏程序结构，所以我又放弃了这个想法。
第二个令人担忧的问题是我使用的数组：我实现 LCS 的方式，我需要一个整数数组来计算匹配数，以及一个布尔数组来标记匹配（即对角线步）。这里的困境是：我应该为 for 循环的每次迭代创建新的数组，还是应该只创建一次并重复使用它们，从而节省 GC 的一些工作（并保持峰值工作集更小），但需要不时重新初始化。经过简单的实验，我没有看到太大的差异，所以我选择了新的数组，因此在这方面，代码比以前更精简，而不是更“精打细算”。
[自 V1.1 起新增段落] 当两个文件相当相似时，大部分时间都花在 LCS 算法本身之外，因此数组在性能方面并不那么重要。在测试示例中，LCS 部分只运行了三次（处理 90 行，总共 1700 多行，假设窗口大小为 30）。
结论
我认为，任务已经完成。文件比较的性能非常好；我所有的初始目标都已实现。并且由于执行时间严格是线性的，你可以使用这个类和应用程序来比较包含数百万行的超大文件。
历史
- LPTextFileDiff V1.0 (2009 年 8 月 27 日；首次发布)。
- LPTextFileDiff V1.1 (2009 年 8 月 31 日；第二次发布)。
- 添加了目录；
- 添加了关于换行符的注释；
- 删除了关于对称性的含糊不清且相当不相关的注释；
- 添加了动态窗口大小调整（一些逻辑，以及一个新的阈值选项 /T）；
- 使 GC.Collect 可选（一些逻辑，以及一个新的速度选项 /S）；
- 进行了一些性能改进；
- 进行了多线程实验并报告了它们被拒绝。
© . All rights reserved.