这里有一个相当有效的解决方案 - 我认为它大致是O(n)，但这取决于添加和删除的分布。内存消耗非常低，但也取决于连续添加和删除的数量。
限制：
1.该算法不会保留补丁行与原始文件中的顺序相同；如果这很重要，则可以使用Dictionary来跟踪添加和删除的行，其中键是该行，值是原始行号，而不是使用HashSet。
2.目标（“新”）文件必须与源（“旧”）文件相似。具体来说，所有未更改的行必须按相同顺序出现在源和目标中。如果不满足此条件，算法将表现不佳。
3.每行必须对于其附近的行是唯一的，“附近”的意思是在源和目标之间未更改的最近行之间。如果不满足此条件，算法将错过更改。
4.此实现不考虑修改后的行。我认为您可以通过将==比较替换为用于检测两行是否为“相同”行的任何操作，然后将它们写入到补丁中，如果它们是内容发生更改的“相同”行，则可以添加该功能。
该算法使用一对“添加”和“删除”缓冲区来跟踪在运行过程中可能添加和删除的行。当文件之间的行不匹配时，这些行会被暂时标记为“添加”或“删除”。当在其中一个文件中找到了一个被标记为暂时标记的行（如果在目标文件中找到了一个“删除”行，或者在源文件中找到了一个“添加”行），这是一个信号，表明所有在另一个缓冲区中的行都属于那里，因此将刷新另一个缓冲区到补丁文件中，然后读取器在找到匹配行的文件中向前移动一行。
例如：
源 目标 添加 删除
A-------A _ _
B-------X +X +B
C-------B 刷新 X -B
D--\ \-C _ _
E-\ \---E +E +D
F \----F -E 刷新 D
以下是代码：
public void Diff(
string sourcePath,
string targetPath,
string patchPath,
string addedSuffix,
string removedSuffix)
{
using(var sourceReader = new StreamReader(sourcePath))
using(var targetReader = new StreamReader(targetPath))
using(var patchWriter = new StreamWriter(patchPath, append:false))
{
var sourceLine = sourceReader.ReadLine();
var targetLine = targetReader.ReadLine();
var added = new HashSet<string>();
var removed = new HashSet<string>();
do{
if(sourceLine == targetLine)
{
sourceLine = sourceReader.ReadLine();
targetLine = targetReader.ReadLine();
}
else
{
if(removed.Contains(targetLine))
{
removed.Remove(targetLine);
Flush(patchWriter, added, addedSuffix);
added.Clear();
targetLine = targetReader.ReadLine();
}
else if(added.Contains(sourceLine))
{
added.Remove(sourceLine);
Flush(patchWriter,removed, removedSuffix);
removed.Clear();
sourceLine = sourceReader.ReadLine();
}
else
{
removed.Add(sourceLine);
added.Add(targetLine);
sourceLine = sourceReader.ReadLine();
targetLine = targetReader.ReadLine();
}
}
} while(sourceLine != null || targetLine != null);
Flush(patchWriter, added, addedSuffix);
Flush(patchWriter, removed, removedSuffix);
}
}
public void Flush(StreamWriter writer, IEnumerable<string> lines, string suffix)
{
foreach (var line in lines.Where (l => l != null))
{
writer.WriteLine("{0} {1}", line.Trim(), suffix);
}
}
这是我用来生成测试文件的一些代码：
var path = ;
var sourcePath = Path.Combine(path, "source.txt");
var targetPath = Path.Combine(path, "target.txt");
var expectedPath = Path.Combine(path, "expected.txt");
var rnd = new Random(10);
using(var sourceWriter = new StreamWriter(sourcePath))
using(var targetWriter = new StreamWriter(targetPath))
using(var expectedWriter = new StreamWriter(expectedPath))
{
var limit = 10.0 * 100000;
for (int i = 0; i < limit; i++)
{
if(i % 10000 == 0) Console.Write("{0:P0} ...", i / limit);
var guid = Guid.NewGuid().ToString();
var r = rnd.Next(0,10);
var removed = 3;
var added = 6;
if(r >= 0 && r < removed)
{
sourceWriter.WriteLine(guid);
expectedWriter.WriteLine(guid + " 0");
}
else if(r >= removed && r < added)
{
targetWriter.WriteLine(guid);
expectedWriter.WriteLine(guid + " 1");
}
else if(r >= added)
{
sourceWriter.WriteLine(guid);
targetWriter.WriteLine(guid);
}
}
}
看到任何错误或问题了吗？这是你要找的内容吗？
