`git diff –patience`和`git diff –histogram`有什么区别？

这个较早的问题要求提供4种不同的Git diff策略之间的差异，但唯一解释的差异是myers和patience之间的差异，这在其他地方很好解释。

histogram策略如何工作？ 它与patience什么区别？ git-diff手册页只是说它“把耐心algorithm延伸到”支持低出现的共同元素“。 其他网页提到它更快，它来自JGit，但是它们没有解释它的algorithm或结果在哪里或如何与patience不同 。

在哪里可以find与patiencealgorithm相关的histogramalgorithm的描述 ，与Bram Cohen对patiencealgorithm的原始描述具有相同的细节水平？

（如果只是执行性能问题，没有任何情况会产生不同的结果，为什么它不是作为patience的新后端来实现？

Answer 1

这个直方图策略是在git 1.7.7（2011年9月）中引入的，具有以下描述（如OP所述）

“ git diff ”学到了一个“ --histogram ”选项来使用--histogram不同的差异生成机器，这可能会带来更好的性能。

JGit包含src/org/eclipse/jgit/diff/HistogramDiff.java和tst/org/eclipse/jgit/diff/HistogramDiffTest.java

这里的描述相当完整：

HistogramDiff

Bram Cohen的耐心差异algorithm的扩展forms。

这个实现是通过使用Bram Cohen博客中概述的4个规则得出的 ，然后进一步扩展到支持低出现率的通用元素。

该algorithm的基本思想是为序列A的每个元素创build出现的直方图 。 然后依次考虑序列B的每个元素。 如果该元素也存在于序列A中，并且具有较低的出现次数，则该位置被视为最长公共子序列（LCS）的候选者。
在B的扫描完成之后，select发生次数最less的LCS作为分割点。 该区域在LCS周围分裂，并且该algorithmrecursion地应用于LCS之前和之后的部分。

通过始终select出现次数最less的LCS位置，只要两个序列之间存在唯一的公共元素，该algorithm的行为与Bram Cohen的耐心差异完全相同。
如果不存在唯一元素，则select最低发生元素 。
这提供了比标准Myers'O O(ND)algorithm产生的更简单的可读差异。

为了防止algorithm运行O(N^2) ，直方图桶中唯一元素的数量上限由#setMaxChainLength(int)configuration。
如果序列A具有比这多个散列到相同散列桶的元素多的algorithm，则algorithm将该区域传递给#setFallbackAlgorithm(DiffAlgorithm) 。
如果未configuration故障预置algorithm，则该区域将作为replace编辑发出。

在扫描序列B的过程中，即使在两个序列之间是共同的，对于LCS匹配位置也不会考虑发生超过#setMaxChainLength(int)倍的A的任何元素。 这限制了序列A中必须考虑查找LCS的位置数量，并有助于保持较低的运行时间界限。

只要#setMaxChainLength(int)是一个小常量（如64），algorithm运行在O(N * D)时间，其中N是input长度的总和， D是所得EditList中编辑的数量。
如果提供的SequenceComparator具有良好的散列函数， MyersDiff即使其理论运行时间相同，该实现通常也会执行MyersDiff 。

这个实现有一个内部限制，可以防止处理超过268,435,456（2 ^ 28）个元素的序列

---

请注意，这种algorithm已经用于pack_check，早在2006年（git 1.3） ，用于git-verify-pack -v 。 它被重用在git 1.7.7中的索引包

---

提交8c912ee实际上介绍了--histogram差异：

将JGit的HistogramDiffalgorithm转换为C.粗数字（TODO）表明它比它的 – --patience表亲以及默认的Meyersalgorithm更快。

这个实现已经被改写为使用结构体和指针，而不是位掩码，从而消除了JGit的2^28行限制 。

为了方便起见，我们还使用xdiff的默认哈希表实现（ xdl_hash_bits()和XDL_HASHLONG() ）。

提交8555123（git 1.7.10，2012年4月）补充说：

8c912ee（教 – diff ，2011-07-12）声称直方图差异--histogram和耐心更快。

我们已经整合了一个性能testing框架，因此添加一个testing来比较真正的“ log -p ”工作负载中执行的各种diff任务。
这确实表明，直方图差异稍微击败迈尔斯，而耐心比其他人慢得多。

最后， 提交07ab4de（git 1.8.2，2013年3月）添加

config：引入diff.algorithmvariables

一些用户或项目比其他用户更喜欢不同的algorithm，例如对迈尔斯或类似的耐心。
但是，每次使用diff时指定适当的参数是不切实际的。 而且，创build一个别名与基于diff的其他工具（例如git-show ）并不能很好地兼容。

因此，需要能够设置特定algorithm的configurationvariables。
现在，这四个值被接受：

• ' myers '（其效果与不设置configurationvariables相同），
• ' minimal '，
• “ patience ”和
• ' histogram '。

Commit 07924d4同时添加了--diff-algorithm命令行选项。
正如OP Stuart P. Bentley 在评论中提到的那样 ：

你可以configurationGit默认使用直方图 ：

 git config --global diff.algorithm histogram 

---

更新：Git 2.12（2017年第1季度）将会退出在某些特定情况下出现灾难性性能问题的“快速哈希”。

见Jeff King（ peff ）的 提交1f7c926 （2016年12月1日） 。 ^{（由Junio C gitster合并- gitster -在承诺731490b ，2016年12月19日）}

xdiff ：drop XDL_FAST_HASH

xdiff代码散列diff的两边的每一行，然后比较这些散列以查找重复项 。 整体性能取决于我们可以计算散列的速度，也取决于我们看到多less散列冲突。

XDL_FAST_HASH的思想是加快哈希计算。
但生成的哈希碰撞行为更差。 这意味着在某些情况下，它的速度差异很大（在git.git上运行“ git log -p ” git.git提高git.git ~8% ），但在其他情况下，速度可能会减慢。 一个病理案例超过了100倍的放缓 。

可能有一个更好的散列函数，涵盖了两个属性，但与此同时，我们最好使用原始散列。 常见病例稍慢，但病例较less，