英文:
Could someone explain what an SVN bisect algorithm is? Theoretically and through code snippet
问题
我想了解什么是 SVN bisect / git-bisect 算法..我已经尝试在网上搜索资源，但无法获得清晰的问题陈述和解决方案。
英文:
I want to understand what an SVN bisect / git-bisect algorithm is..I have tried to search online resources but unable to get a good problem statement and solution.
答案1
得分: 1
简单来说，二分查找的思想是一种二分搜索方法。
二分查找的思想基于几个假设：
- 存在特定的应用行为（为了简单起见，我们称之为“缺陷”），您希望找到其原因。
- 代码分析和调试需要太多的工作。
- 构建任何版本并针对其运行测试比代码分析和调试容易得多。
- 您知道过去的某个代码修订版没有此缺陷。
一种直接的方法是构建先前的修订版本并测试是否存在此缺陷。如果有，那么测试前一个修订版本。您继续这样做，直到找到引入此错误的修订版本。您知道此提交中的所有更改。这就是为什么更容易找到确切导致缺陷的更改。此外，调试可能会更容易，因为您可以关注（通常是）少量更改。
但是，如果已知没有缺陷的修订版本是在最近的修订版本之前的200个修订版本，您可能需要重复“构建和测试”过程200次（如果没有运气的话）。
我们将没有缺陷的修订版本命名为R0，有缺陷的修订版本命名为R200。
二分查找允许加快此过程。您“告诉”二分查找哪个修订版本有缺陷，哪个修订版本没有缺陷。然后，二分查找计算这些修订版本之间的提交数量。在我们的案例中，这是200个提交。二分查找选择一个在有缺陷的修订版本之前100个修订版本的修订版本，并将其检出。这意味着，它检出修订版本R100。您构建并测试它。然后，您“告诉”二分查找此修订版本是否包含缺陷。如果有缺陷，那么它意味着它是在版本R0和R100之间引入的。如果没有缺陷，这意味着缺陷是稍后引入的，介于修订版本R100和R200之间。
假设您告诉二分查找在R100中存在缺陷。然后，二分查找选择范围R0 - R100的中间版本。这将是修订版本R50。二分查找检出它。您构建并测试，并将结果告诉二分查找。
假设R50没有缺陷。意味着它是在修订版本R50和R100之间引入的。二分查找再次选择中间版本，修订版本R75。您构建并测试。
假设R75有缺陷。意味着它是在修订版本R50和R75之间引入的。二分查找检出修订版本R63。依此类推。
总共需要log(200) = 8个步骤。如果您要检查每个版本，您将构建并测试高达200个修订版本，这将花费更长时间。
在Git的情况下，您首先使用命令启动二分查找过程：
git bisect start
然后您检出具有缺陷的修订版本并运行命令：
git bisect bad
然后您告诉二分查找哪个修订版本没有缺陷：
git bisect good R0
通过此命令，Git二分查找将找到中间版本R100，并将其检出。您构建并测试它，如果它包含缺陷，则运行命令：
git bisect bad
否则，运行命令：
git bisect good
并依此类推，直到找到引入缺陷的修订版本。
英文:
Briefly, the idea of bisect is a binary search.
The idea of bisect is based on several assumptions:
- There is a particular application behaviour (for simplicity, let's call it "defect") and you want to find its reason.
- Code analysis and debugging needs too much efforts.
- Building any version and running tests against it is much easier than code analysis and debugging.
- You know some code revision in the past without this defect.
A straight forward approach is to build the previous revision and test if it has this defect. If has, then test one revision earlier. You continue until you find the revision that introduced this bug. You know all the changes in this commit. That's why it is easier to find what change exactly caused the defect. Also debugging can be much easier, because you can focus on (usually) a few changes.
But if the revision known to have no defect is 200 revisions in the past before the recent revision, you may need to repeat "build and test" procedure 200 times (if you have no luck).
Let's name the revision without defect R0, revision with defect R200.
Bisect allows to make it faster. You "tell" bisect what revision has defect and what revision has no defect. Then bisect calculate the number of commits between these revisions. In our case these are 200 commits. Bisect takes a revision that is 100 revisions before the revision with defect and checks it out. Means, it checks out revision R100. You build it and test. Then you "tell" bisect if this revision contains defect or not. If there is defect, then it means it was introduced between versions R0 and R100. If there is no defect, it means that defect was introduced later, after revision R100, between R100 and R200.
Suppose you told bisect there is defect in R100. Then bisect takes the middle of the range R0 - R100. This will be revision R50. Bisect checks it out. You build it and test and tell the result to bisect.
Suppose R50 has no defect. Means, it was introduced between revisions R50 and R 100. Bisect takes again the middle, revision R75. You build it and test.
Suppose R75 has defect. Means it was introduced between R50 and R75. Bisect checks out R63. Ans so on.
In total you need log(200) = 8 steps. If you would check every version, you would build and test up to 200 revisions, which would take much longer.
In case of Git, you first start bisect procedure with command
git bisect start
Then you check out revision with defect and run command
git bisect bad
Then you tell bisect what revision was without defect:
git bisect good R0
By this command Git bisect will find the middle, R100, and check it out. You build and test it and, if it contains defect, run command
git bisect bad
Otherwise command
git bisect good
And thus continue until you the revision found that introduced the defect.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论