调试和二进制搜索

Question

第2列("AHA!算法")中的"编程珍珠"讨论了二进制搜索如何帮助各种过程,如排序,树遍历.但它提到二进制搜索可以用于"程序调试".有人可以解释一下这是怎么做的吗？

Answer 1

二进制搜索是在排序列表中查找项目的有效方法.例如,如果您正在寻找书中的特定页面(例如,第147页),您可以在中间附近打开书籍,并确定打开的页面是在您要查找的页面之前还是之后.然后你选择你缩小它的部分并重复这个过程:将它分成两半并确定哪一半包含第147页.更好的是,你可以猜到第147页的距离 - 如果这本书是非常长,接近一本短篇小说的结尾 - 并将该猜测作为第一个分割点.二元搜索的这种变化称为插值搜索.

因此,如果你有一个bug和它可能隐藏的排序列表,插值搜索通常是压缩它的方法.其他答案解释了在一系列行或源代码提交中隐藏的错误的常见情况.但该技术可以应用于其他情况:

• 日志搜索

  在一个长期运行的系统上,尤其是处理如此多数据的系统,你必须每天轮换你的日志,今天看到几周/几个月/几年前很好的事情并不罕见.使用复杂的互锁系统,可以在不进行任何代码更改的情况下发现错误.找到硬件,网络,操作系统,配置(虽然应该与代码一起存储),输入,手动程序等的变化可能很困难,因为很多这些事情在很长一段时间内都会发生变化.对日志(无论是在表格还是在文件中)的全文搜索通常是不切实际的.

  在这种情况下,几乎没有任何选择,只能在中间某处打开日志,看看是否存在问题.然后剪切你知道bug隐藏的部分并再次查找bug.最终,您应该能够发现您的错误出现的第一时刻,这使得找到罪魁祸首变得更加容易.

• 输入搜索

  前几天,我注意到一个带有长文本的模糊"bug".追踪文本和破坏系统的文本之间的确切边界的最快方法是将文本切成两半,直到找到分界线.(原来我是个白痴,但我做香蕉的时候做得更好.)

• 概念过程步骤

  大多数人甚至不知道他们大多数时间都在使用二进制(或更好的插值)搜索; 这是解决问题的一种自然方式.在考虑包含潜在错误的一系列步骤时,首先检查其中一个中间步骤的输出通常是明智的,以避免检查整个代码,只是发现问题是在最后一步.

Answer 2

如果您不知道100行程序中的哪一行是错误的,那么您将尝试运行前50行并跳过其余行.如果问题出现,您就会知道第一个段包含错误.你接下来会尝试拆分它并运行前25行并查看问题是否存在等等,直到找到足够短的部分来查看.

二进制搜索背后的想法是识别/隔离一个有缺陷的小区域.但是,与所有方法一样,这并不适用于所有情况.例如:递归函数对于这样的工具来说非常笨重.当存在太多执行路径时,分割要运行的代码可能会变得困难.

Answer 3

另一种可能性是你有一个错误,你知道它在你的二月发行版中没有,但它是在你的四月发布(或者更确切地说,你的四月发布候选版本- 你永远不会向你的用户发送一个错误,对？).

您可以通过修订控制历史记录进行手动二进制搜索,以便在引入错误时缩小范围.首先检查两个版本之间的代码,构建它,然后查看是否存在错误.保持分区,直到找到它的介绍时间.如果你不知道从哪里开始寻找bug,这可能非常有效,特别是如果你做了相当小的提交.

这适用于Subversion,因为它具有存储库范围的修订号.如果您的二月发行版是533版本,而您的四月版本是rev 701,那么您将更新为版本617,测试它,然后从那里开始.(实际上,我通常会到600,所以我不需要在脑子里做那么多的数学运算.)一旦我开始缩小它,我开始查看提交注释并做出有根据的猜测("我真的没有认为这个提交会破坏它"),所以我通常不需要做所有log ₂(n)签出.

我从未使用过Git,但他们使用内置的" bisect "命令更进了一步.你给它一个起点(什么时候可以工作？)和结束点(你什么时候注意到它被打破了？),它会自动获得二进制搜索中间点的代码.然后在你构建并测试之后,你告诉它这个转速是通过还是失败; 然后它获取下一个中间点的代码.您甚至可以告诉它为每个rev运行一个命令,并使用命令的退出代码来确定rev是通过还是失败,此时它可以全自动运行.

Answer 4

二分搜索可以通过以下方式帮助调试：

1. 假设控制必须达到某个点，而您怀疑它没有达到。将打印语句放在第一行和最后一行代码中。假设您看到第一个但没有看到第二个语句的结果。将打印语句放在中间，然后再试一次。通过这种方式，您可以在代码行空间上使用二进制搜索将错误归零。
2. 假设您使用版本控制系统。版本 10 通过了所有测试。即将发布的 70 版未能通过一些测试。检查版本 40 并在其上运行测试。如果它工作正常，请尝试版本 55。如果版本 40 失败，请尝试版本 25。通过这种方式，您可以在程序版本空间上使用二进制搜索，以便将错误进入程序的第一个版本归零。