系列文章

  • #1 : 根底介绍 & 事例 1 线性提交
  • #2 : 事例 2 之 “含兼并提交”
  • #3 : 事例 3 之 “含回退型兼并提交”
  • #4 : 扩展指令 : 使用进程中的一些扩展问题
  • #5 : 算法解析 : 中位 commit 的选取 <== 本篇文章
  • #6 : 结合 bisect, 评论代码协作工作流中的最佳实践

导言

前面几篇文章，主要站在使用层面上对 bisect 进行评论，本文章开端对底层进行解析。

进入正题前，不敢不先呈现一个文章 :

  • 英语原文 : Fighting regressions with git bisect from Christian Couder
    • 你也可看 git 官网中不同排版的同内容文章 : git-bisect-lk2009
  • 中文译文 ( 质量为 “机翻”…… 但假如英语不太好，仍是能够比对着看看的 )

这篇文章，是本系列文章，最重度依靠的一个引证。不管在读本系列文章之前，或是之后，十分推荐一定要再找机会过一下。

所以，怎么二分定位一个 commit ?

关于这个问题，原文章已经解说的很清楚，可是其叙述视点，更像是 “探索验证完毕，反过来提供正确答案并证明”。

因而，咱们测验从另一个视点来打开阐明，假定咱们不知道当时的最优解，给定 git bisect 的根底设定，咱们怎么在给定提交信息 (Good commits & Bad commit) 时，选取出一个 commit 以供下一次的查验呢?

Let’s start

留意，关于一些 bisect 的根底设定，假如不清楚，推荐仍是回忆一下之前的榜首篇文章了解一下 :

git bisect 的根底介绍

线性提交的场景

要找到二分定位最佳 commit 的算法，咱们先构造一个最简略的场景 : 彻底线性的提交历史记录。

Git bisect 命令解析 #5 : bisect 的算法解析

这种场景下要二分定位一个 commit 的话，应该十分简略，不假思索，毫无疑问，脱口而出地联想到 :

// 找中点
COMMIT_INDEX = floor( (FIRST_UNKNOWN_INDEX + LAST_UNKNOWN_INDEX) / 2 )

Git bisect 命令解析 #5 : bisect 的算法解析

留意 :

  • 如上的数字为 : commit 的虚构出来的 index
  • floor 是为了处理 index 为整数的处理 ( 当核算出 x.5 时，x 或 x+1 是等价的最优 commit )

有兼并提交的场景

线性场景挺简略，可是骨感的现实是，咱们会有各式各样的分支，导致真实到手的总不太抱负，更或许是一个契合 git 尿性的有向图，而不是一根骨感的线。

Git bisect 命令解析 #5 : bisect 的算法解析

这种场景下，原来的中位 index 核算就不好施行了。咱们需求其他更合理的处理模型，用于理解和核算。

先回到线性场景中，咱们来考虑一下 “当选中一个 commit”，意味着什么?

Git bisect 命令解析 #5 : bisect 的算法解析

  1. 选取出一个 commit 之后，接下来便是要对其进行 “查验”，看看这个 commit 归于好提交，仍是坏提交。
  2. 承认完其状况之后，咱们会利用 bisect 的设定，对当时剩下 commit 规模进行裁剪，剩下无法承认好坏的部分，则作为下一轮二分查找的规模
  3. 循环以上进程，直至咱们承认榜首个坏提交，或者出现问题终止

假定选取一个 commit，那么它有或许是好的，也或许是坏的。假定假如是好提交，依据规矩，下一轮剩下 X 个提交。坏提交的话，剩下 Y 个提交 (如下图)

Git bisect 命令解析 #5 : bisect 的算法解析

那么咱们为了避免进入最坏状况，咱们会希望经过这轮查验之后，X 要尽或许接近 Y，也便是要尽或许地 “平衡” (全规模被二分)。那么咱们或许得出如下的定论 :

假如每个 commit 被赋予一个数值 A，代表 : MAX( X, Y ) - MIN( X, Y )
那么, 被选取出来的 commit 的 A 要尽或许的小

以上的定论，也等同于如下两个版别 :

// 版别 a。
假如每个 commit 被赋予一个数值 A, 代表 : MAX( X, Y )
那么, 被选取出来的 commit 的 A 要尽或许的小
// 版别 b。
假如每个 commit 被赋予一个数值 A, 代表 : MIN( X, Y )
那么, 被选取出来的 commit 的 A 要尽或许的大

如下图所示 :

Git bisect 命令解析 #5 : bisect 的算法解析

这几个不同的逻辑版别，能够用更直观的含义进行理解 :

类别 含义
MAX – MIN 取最小 选取最平衡的 => 避免最坏状况
MAX 取最小 最坏状况下，选取 “剩下数量” 最少的
MIN 取最大 最坏状况下，选取 “裁剪掉的数量” 最多的

小 tips : 同样，能够按照另一个视点来理解，比如说 “剩下数量” 最少，或 “裁剪掉的数量” 最多，等同于，查验选取出来的 commit 之后，能获得最大的信息量

为了让评论愈加聚焦，咱们采用上述说到的文章中的视点，运用 “裁剪掉的数量” 来进行评论。( 也便是 MIN( X, Y ) 这个权重值，方便起见，记为 M )。

于是问题能够进一步转换为 :

  • 为待定的一切 commit 承认这个权重值
  • 选取最大的权重值作为成果

另外，为了避免混杂，咱们和上述文章以及本系列的前面章节保持一致，挑选如下设定 :

  • 每一次进行二分法查找时，待选提交的规模包含 : “未知好坏的提交” (一个或多个) & “坏提交” (一个)
    • 当未知提交为零个时，阐明已经发生最后成果了，故不在评论规模
  • ancestors (祖先)，翻译为前置提交
  • descendants (后代)，翻译为后续提交

怎么承认 M ? ( 开始猜想 )

好的，有了一定的处理思路，那么 M 怎么被承认呢?

仍是回到线性场景中评论 :

Git bisect 命令解析 #5 : bisect 的算法解析

能够看到，不管选中的 commit 是好是坏，提交规模会被分为两组 :

  • 榜首组 : 选中提交本身 & 一切前置提交
  • 第二组 : 原规模内的一切后续提交 ( 含原坏提交 )

因而，先做一个猜想 :

M = MIN( 前置提交数量 + 1, 后续提交 )

但这个猜想对么? 别着急，继续扩展一下场景，验证一下。

考虑兼并场景，对 M 进行验证

以下用一个提交结构为例，这个比如简略，但可代表很多的相似场景。

Git bisect 命令解析 #5 : bisect 的算法解析

这里可通过两个区域 (区域 A, B) 进行分析，也便是选取的 commit 或许位于这两个区域的其间一个。另一个分支和区域 B 归于对称状况，故不必单独评论。

首要，看看选取的 commit 被判定为好提交的状况 (下图)。从图中可承认，在这种状况中，不管 commit 落在哪一个位置，被裁剪掉的数量，等于所选取 commit 的前置提交数量 + 1，契合上述的猜想。

Git bisect 命令解析 #5 : bisect 的算法解析

其次，再看看选取的 commit 被判定为坏提交的状况 (下图)。假如选取 commit 来自区域 A，那么契合后续提交数的猜想，但假如来自区域 B，裁剪掉的提交不仅仅是所选取 commit 的后续提交，而是连并行分支中的提交都能够排除掉。这个状况，与上述猜想不一致。

Git bisect 命令解析 #5 : bisect 的算法解析

事实上，上图中的 C1 ~ C4，并不能被承认是好提交仍是坏提交，仅仅依据 bisect 的根底设定，当咱们知道区域 B 某个提交为坏提交时，咱们并不需求关注他们的状况。如下图，咱们想要找的引进过错的提交，必定是存在于区域 B 或者区域 B 再往前的提交。因而，它们亦可被裁剪。

Git bisect 命令解析 #5 : bisect 的算法解析

利用上面的分析，推导出一个更合理的核算方法 :

M = MIN( 前置提交数量 + 1, 待选提交总数 - (前置提交数量 + 1) )

同时，这个公式在线性场景中，也是契合一切之前的要求。或者说，之前的猜想，等价于这个核算公式一种在线性场景中的 “特例”。

算法总结

综上分析，git bisect 的二分查找算法，可简化为如下的表述 :

  • 首要，对一切待查提交进行核算，得出每个提交的 M 值
    • 额定留意 : 能够有这么一个功能优化点，假如当核算进程，刚好得出 M 等于 待选提交总数 / 2，那么此刻能够即时中断，直接选取该提交 (因为不或许找到比这更适宜的提交了)
  • 然后，选取出 M 最大的提交 (或许是多个提交中任选其一)，并作为本次二分查找的成果返回
    • 额定留意 : 本系列 #4 使用进程的扩展问题 — 关于 untestable 提交的处理

参阅文章

  • 英语原文 : Fighting regressions with git bisect from Christian Couder
  • 你也可看 git 官网中不同排版的同内容文章 : git-bisect-lk2009
  • 中文译文 ( 质量为 “机翻”…… 但假如英语不太好，仍是能够比对着看看的 )

系列文章

  • #1 : 根底介绍 & 事例 1 线性提交
  • #2 : 事例 2 之 “含兼并提交”
  • #3 : 事例 3 之 “含回退型兼并提交”
  • #4 : 扩展指令 : 使用进程中的一些扩展问题
  • #5 : 算法解析 : 中位 commit 的选取 <== 本篇文章
  • #6 : 结合 bisect, 评论代码协作工作流中的最佳实践

作者信息

本文原作者 jsPop，欢迎留言沟通