大家好,我是 lucifer。明天给大家分享我的日常工作中罕用的 debug 杀器!
二分代码
当我发现一个难以了解和发现的 bug 的时候,我的 终极方法 就是二分代码。
比方先删去文件 a 的一半代码(大概),而后测试问题是否还在。
- 如果问题不在了,那么咱们就找到了出问题的代码。
- 如果问题还在,那么咱们持续应用同样的方法,持续删去文件 a 的一半代码(大概),而后测试问题是否还在。
- 反复上述步骤,直到找到出问题的代码
这个办法在我一时没有思路或者帮忙他人定位问题的时候十分有用。因为这种做法工夫复杂度大抵是 logn,因而只须要短短几次咱们就能够大抵定位到问题代码。相似地,咱们也能够在多个文件中同时进行二分。
二分提交
更多的时候,咱们是在两次公布之间发现了一个 bug。而这两个公布之间是有若干 commit 的,并且 commit 还不少(几十个甚至上百个)。
咱们也能够应用相似的办法。
- 先切换到两次公布之间的两头提交 x(即便得提交 x 绝对于两次公布之间的间隔差最小)。
实际上这个最小间隔差要么是 0,要么是 1
- 验证问题是否存在。如果不存在,咱们不能确定就是这个提交的问题,无妨先标记以后提交 c 为 good。如果存在,无妨标记以后提交 c 为 bad。
- 通过下面的标记,咱们就能够找到最早出现 bad 的那次提交,并且最要害的是复杂度为 logn,其中 n 为咱们须要验证的提交的总次数。显然,这个工作量比一一查看 commit 要快很多。
不了解其中原理?稍后咱们会讲。
Git 中的二分查找
git 的开发者也想到了这一点,因而提供了 bisect 命令来帮忙咱们做下面这个事件。
应用 bisect 进行问题查找次要依赖于上面的三个命令:
- git bisect start
启动一个查找,start 前面能够加上 good 和 bad 的提交点:
git bisect start [rev bad] [rev good]
如果不加 good 和 bad 的提交点,那么 git 将会等到咱们应用 good 和 bad 命令指定对应的提交点后开始进行查找
- git bisect good
用来标记一个提交点是正确的,前面能够加上 rev 来指定某个特定的提交点,如果不加,则默认标记以后的提交点。
- git bisect bad
用来标记一个提交点是蕴含问题的,如果 bad 后能够加上 rev 来指定某个特定的提交点,如果不加,则默认标记以后的提交点。
背地原理
咱们来补后面的坑。为什么通过这样的标记,咱们就能够找到第一个有问题(标记 bad)的提交?并且工夫复杂度为 $O(logn)$。
正好力扣有一道原理,咱们间接用它来讲吧。
题目地址(278. 第一个谬误的版本)
https://leetcode-cn.com/probl…
题目形容
你是产品经理,目前正在率领一个团队开发新的产品。可怜的是,你的产品的最新版本没有通过品质检测。因为每个版本都是基于之前的版本开发的,所以谬误的版本之后的所有版本都是错的。假如你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个谬误的版本。你能够通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个谬误的版本。你应该尽量减少对调用 API 的次数。示例 1:输出:n = 5, bad = 4
输入:4
解释:调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个谬误的版本。示例 2:输出:n = 1, bad = 1
输入:1
提醒:1 <= bad <= n <= 231 - 1
思路
能够看出,这个过程和咱们下面的形容是一样的。并且咱们的指标都是找到第一个出错的提交。
须要明确的是:
- 如果一个版本 x 是 good 的,那么 [1, x] 之间的所有提交必定都是 good 的,因而待检测版本变为 [x+1,n]
- 如果一个版本 x 是 bad 的,那么 [x, n] 之间所有的提交必定都是 bad 的。因为咱们要找到的是第一个有问题的版本,因而待检测版本变为 [1,x-1]
因而无论咱们检测的版本是 good 还是 bad,咱们都能够将待检测的版本数量变为一半,也就是说咱们能够在 $logn$ 次内找到第一个有问题的版本。
如果你看过我的二分专题,应该晓得这就是我总结的 最左二分。
- 二分专题(上)
- 二分专题(下)
代码
- 语言反对:Python3
Python3 Code:
class Solution:
def firstBadVersion(self, n):
l, r = 1, n
while l <= r:
mid = (l + r) // 2
if isBadVersion(mid):
# 膨胀
r = mid - 1
else:
l = mid + 1
return l
复杂度剖析
- 工夫复杂度:$O(logn)$
- 空间复杂度:$O(1)$
总结
二分大法在日常工作中利用还是蛮多的,二分找 bug 是其中一个很实用的技巧。最简略的二分找 bug 能够通过删除文件内容的形式进行。而如果文件很多,就很不不便了,这个时候咱们能够应用二分提交来实现。
其中的原理其实也很简略,就是一个奢侈的最左二分。如果大家对此不相熟,强烈建议看下文章中提到的二分专题,两万字总结相对让你有所播种。