我想了解什么是 SVN bisect / git-bisect 算法。我尝试搜索在线资源，但无法获得好的问题陈述和解决方案。
问问题
331 次
1 回答
1
简而言之，二分法的思想是二分查找。
bisect 的概念基于几个假设：
- 有一个特定的应用程序行为（为简单起见，我们称其为“缺陷”），您想找到它的原因。
- 代码分析和调试需要付出太多的努力。
- 构建任何版本并针对它运行测试比代码分析和调试要容易得多。
- 你知道过去的一些代码修改没有这个缺陷。
一个直接的方法是构建以前的版本并测试它是否有这个缺陷。如果有，则提前测试一个版本。您继续，直到找到引入此错误的修订版。您知道此提交中的所有更改。这就是为什么更容易找到究竟是什么变化导致了缺陷。调试也容易得多，因为您可以（通常）专注于一些更改。
但是，如果已知没有缺陷的版本是最近一次修订之前的 200 次修订，您可能需要重复“构建和测试”过程 200 次（如果您没有运气）。
让我们将没有缺陷的修订版命名为 R0，将有缺陷的修订版命名为 R200。
Bisect 可以让它更快。你“告诉”什么版本有缺陷，什么版本没有缺陷。然后 bisect 计算这些修订之间的提交次数。在我们的例子中，这些是 200 次提交。Bisect 会在有缺陷的修订之前 100 个修订进行修订并将其检查出来。意味着，它检查修订版 R100。您构建它并进行测试。然后你“告诉”这个版本是否包含缺陷。如果有缺陷，则表示它是在 R0 和 R100 版本之间引入的。如果没有缺陷，则表示该缺陷是后来引入的，在 R100 修订版之后，介于 R100 和 R200 之间。
假设您告诉 bisect R100 存在缺陷。然后 bisect 取 R0 - R100 范围的中间值。这将是修订版 R50。Bisect 进行检查。你构建它并测试并告诉结果平分。
假设 R50 没有缺陷。意思是，它是在 R50 和 R 100 版本之间引入的。Bisect 再次采用中间版本 R75。您构建它并进行测试。
假设 R75 有缺陷。表示它是在 R50 和 R75 之间引入的。Bisect 检查 R63。以此类推。
总共需要 log(200) = 8 个步骤。如果您检查每个版本，您将构建和测试多达 200 个修订版，这将花费更长的时间。
在 Git 的情况下，您首先使用命令启动 bisect 过程
git bisect start
然后你检查有缺陷的修订并运行命令
git bisect bad
然后你告诉 bisect 什么版本没有缺陷：
git bisect good R0
通过这个命令，Git bisect 将找到中间的 R100，并检查它。您构建并测试它，如果它包含缺陷，请运行命令
git bisect bad
否则命令
git bisect good
并因此继续，直到您发现引入缺陷的修订。
于 2020-05-30T06:08:28.730 回答