2

如果 bisect 范围包括多个分支，hg bisect 的搜索是如何工作的。它是否有效地将每个子分支一分为二（我认为这将是低效的）？

例如，感激地借用这个相关问题的答案中的图表，如果二等分首先到达“好”右侧分支上的变更集 7 会怎样。

@  12:8ae1fff407c8:bad6
|
o  11:27edd4ba0a78:bad5
|
o    10:312ba3d6eb29:bad4
|\
| o  9:68ae20ea0c02:good33
| |
| o  8:916e977fa594:good32
| |
| o  7:b9d00094223f:good31
| |
o |  6:a7cab1800465:bad3
| |
o |  5:a84e45045a29:bad2
| |
o |  4:d0a381a67072:bad1
| |
o |  3:54349a6276cc:good4
|/
o  2:4588e394e325:good3
|
o  1:de79725cb39a:good2
|
o  0:2641cc78ce7a:good1

然后它会看起来只在 7 到 12 之间，错过我们关心的真正的第一坏吗？（因此使用“哑”数字顺序）或者它是否足够聪明以使用完整的地形并知道第一个坏可能在右侧分支上低于 7，或者仍然可能在左侧分支上的任何位置。

我的问题的目的是（a）只是为了更好地理解算法，以及（b）理解我是否可以自由地扩展我的初始平分范围，而无需认真考虑我去哪个分支。我一直处于高分支平分情况，每次测试后它一直要求我扩展到下一次合并之外，因此整个过程基本上是 O(n)。我想知道我是否可以将第一个“好”标记扔回一些合并巢而不考虑太多，以及这是否会节省时间并给出正确的结果。

4

1 回答 1

3

引用Mercurial：权威指南：

hg bisect 命令知道 Mercurial 项目修订历史的“分支”性质，因此它在处理存储库中的分支、合并或多个头时没有问题。它可以通过一个探针来修剪整个历史分支，这就是它如此高效运行的方式。

完成这项工作的代码在hbisect.py中，实际上是查看来自已确定状态的每个节点的后代树和祖先树。

在我看来，选择测试的变更集是通过在尚未测试的图表中加权“中心程度”来选择的（即按祖先与非祖先一分为二，而不是按年表）：

108     x = len(a) # number of ancestors
109     y = tot - x # number of non-ancestors
110     value = min(x, y) # how good is this test?
于 2012-11-02T16:07:30.680 回答