git中的二分查找– git bisect
source link: https://hateonion.me/posts/18dec24/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
git中的二分查找– git bisect
二分查找是一种大家都熟悉的算法。这种算法由于套路非常的清晰，在程序开发中被广泛使用。很常见的一个例子就是使用二分查找去进行程序的debug，逐步缩小代码区间最终确定问题。循着这个思路，在多人合作的场景下，如果某次你pull代码之后发现某些代码不能工作了，你也可以通过二分查找的方式找出出问题的commit。而git bisect就是git内置的二分查找命令。
从二分查找说起
二分查找是一种很简单的算法，适用的对象是 已经排序的数组 。一个最简单的二分查找的实现如下。
/**
* @param {Array} sortedList 排好序的list
* @param {number} target 需要检索的值
* @return {number} 检索到的值的index，未检索到返回-1
*/
function binarySearch(sortedList, target) {
let left = 0;
let right = sortedList.length - 1;
let middle = parseInt((right+left) / 2);
while(sortedList[middle] !== target && left !== right) {
if(sortedList[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
middle = parseInt((right + left) / 2);
}
return sortedList[middle] === target ? middle : -1;
}
一个简单的递归实现如下
/**
* @param {Array} sortedList 排好序的list
* @param {number} target 需要检索的值
* @return {number} 检索到的值的index，未检索到返回-1
*/
function binarySearch(sortedList, target, left = 0, right = sortedList.length-1) {
const middle = parseInt((right + left) / 2);
if(sortedList[middle] === target || left === right) {
return sortedList[middle] === target ? middle : -1;
}
if(sortedList[middle] > target) {
return binarySearch(sortedList, target, left, middle - 1);
} else {
return binarySearch(sortedList, target, middle + 1, right);
}
}
这里是usfca做的一个二分查找的动画演示 https://www.cs.usfca.edu/~galles/visualization/Search.html
git中的二分查找
让我们进行一下思路的迁移，先看一看一条git branch上的commit记录。
其实很容易发现我们的git commit历史其实在某种意义上很像一个 已经排序的数组 ，所以当我们想找出某个有问题的commit时，二分查找很自然的成为了我们首选的搜索算法。
git bisect
git bisect 就是git内置的二分查找工具，具体用法如下。
git bisect start # 开始二分查找
git bisect bad [?index] # 标记错误区间右边界 index 可以是commit hash / tag等。如果不传index那么默认会标注HEAD为bad
git bisect good [index] # 标记错误区间左边界
# 最后错误区间为(good, bad]当确定区间之后，bisect会提示你区间内有多少个commit，并且最多几次查找可以查找完。同时你会被checkout到区间中心的那个commit上。
如果当前的commit仍是坏的commit, 你可以继续使用 git bisect bad 进行标注，git bisect会应用二分法帮你缩小区间并且checkout到区间中心的commit上，这个过程会一直持续直到二分查找结束。而你最后停下来的commit就是那个有问题的commit。
可视化这个过程大致如下
使用 git bisect run来自动标注
git bisect提供了 git bisect run 这条命令可以在某些情况下帮助我们进行自动化标注。
假设在某个commit中我们的测试挂掉了，我们想找出这个commit。我们使用git bisect的思路是在每次查找完后运行测试，根据测试结果去标注good/bad。
yarn test
git bisect good # or bad 取决于test结果以上两条命令可以合并成一条命令
git bisect run yarn testgit bisect run 后面接受的是一条shell命令，如果这条命令以 exit(-1) 终止， git bisect 会自动把当前commit标记成bad，否则标记成good。
一些有用的tips
- 在每一次步进的时候，你可以通过
git bisect visualize来预览当前的commit区间。 - 你可以通过
git bisect log来查看自己的每一次good/bad标注。 - 如果你记录了git bisect log, 你可以通过
git bisect replay [log-file]来重放你的git bisect操作。
- 本文作者: hateonion
- 本文链接: https://hateonion.me/posts/18dec24/
- 版权声明: 本站所有文章均采用 CC BY-NC-SA 4.0 协议进行许可。如需转载，请注明出处。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK