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) どのブランチに行くかを真剣に考えずに最初の bisect 範囲を自由に拡張できるかどうかを理解することです。私は、すべてのテストの後に、次のマージを超えて拡張するように求められ続けたため、手順全体が本質的に O(n) であった、高分岐の bisect 状況にありました。最初の「良い」マーカーを、あまり考えずにマージのネストを過ぎて投げることができるかどうか、そしてそれが時間を節約して正しい結果をもたらすかどうか疑問に思っています。

4

1 に答える 1

3

Mercurial: The Definitive Guideから引用するには:

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 に答える