京公网安备11010502063487号myers、patience、histogram 这几个 diff 算法到底差在哪?会不会真的给出不同的补丁?哪个更快?这篇用随机搜出的反例、300 次随机编辑的统计和 20 万行文件的计时来回答,结论可能和流传的说法有些不同。
旧: '} else {' 'y();' '{' '}' '} else {' 'return;' 'x();' 'return;'
新: '} else {' 'y();' '} else {' '}' '}' '}' '} else {' 'return;' '{' 'x();' 'if (a) {' 'x();' 'return;'
[myers] +6 -1 1 个 hunk
} else {
y();
-{
+} else {
+}
+}
}
} else {
return;
+{
+x();
+if (a) {
x();
return;
[minimal] +6 -1 1 个 hunk
} else {
y();
-{
+} else {
+}
+}
}
} else {
return;
+{
+x();
+if (a) {
x();
return;
[patience] +8 -3 1 个 hunk
} else {
y();
+} else {
+}
+}
+}
+} else {
+return;
{
-}
-} else {
-return;
+x();
+if (a) {
x();
return;
[histogram] +6 -1 1 个 hunk
} else {
y();
-{
+} else {
+}
+}
}
} else {
return;
+{
+x();
+if (a) {
x();
return;四种算法给出的补丁都能把旧文件变成新文件。差别在于怎样对齐:myers 找(近似)最短的编辑脚本,patience 先对齐在两个文件里都只出现一次的行,histogram 是 patience 的改进。
算法 改动行数合计(+ 和 −) hunk 数合计 改动行数最少的次数 myers 10,741 1,608 300 minimal 10,741 1,608 300 patience 10,823 1,604 290 histogram 10,763 1,610 294 300 次里有 14 次四种算法给出的改动行数不全相同;minimal 保证每次都是最少的(它的“最少次数”应该是 300)
在随机搜出的反例里,patience 的补丁反而更长(+8 −3,对比 myers 的 +6 −1);在 300 次随机编辑的统计里,myers 与 minimal 的改动行数最少,patience 略多。patience 的好处是在“有很多相同的括号、空行”的代码里更容易读,而不是更短。
myers 54.3 ms minimal 54.0 ms patience 56.1 ms histogram 63.4 ms
20 万行、约 2% 改动的文件上,四种算法耗时都在 54~63 ms,差别不到 20%。
$ git config --get diff.algorithm || echo "diff.algorithm 未设置(默认 myers)"; git config diff.algorithm histogram; git diff --stat | tail -1; git diff --diff-algorithm=myers --stat | tail -1 diff.algorithm 未设置(默认 myers) 1 file changed, 6 insertions(+), 1 deletion(-) 1 file changed, 6 insertions(+), 1 deletion(-) $ git diff --patience --stat | tail -1; git diff --histogram --stat | tail -1; git diff --minimal --stat | tail -1 1 file changed, 8 insertions(+), 3 deletions(-) 1 file changed, 6 insertions(+), 1 deletion(-) 1 file changed, 6 insertions(+), 1 deletion(-)
diff.algorithm 设置默认算法(不设就是 myers),命令行 --patience、--histogram、--minimal、--diff-algorithm= 可随时覆盖。选哪个看可读性。