debugging - 调试和二分查找

Question

第 2 栏（“啊哈！算法”）中的“编程珍珠”讨论了二分搜索如何帮助排序、树遍历等各种过程。但它提到二进制搜索可以用于“程序调试”。有人可以解释一下这是怎么做到的吗？

Answer 1

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

二进制搜索背后的想法是识别/隔离一个有问题的小区域。但是，与所有方法一样，这并非适用于所有情况。例如：递归函数对于这样的工具将非常笨拙。当执行路径太多时，对要运行的代码进行分段可能会变得很困难。

Answer 2

二进制搜索是在排序列表中查找项目的有效方法。例如，如果您正在寻找一本书中的特定页面（例如，第 147 页），您将在靠近中间的位置打开这本书，并确定打开的页面是在您要查找的页面之前还是之后。然后，您将选择已缩小范围的部分并重复该过程：将其分成两半并确定哪一半包含第 147 页。更好的是，您可以猜测第 147 页有多远——如果这本书是很长，接近一本短书的结尾——并用这个猜测作为第一个划分点。这种二分搜索的变体称为插值搜索。

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

• 日志搜索

  在一个长期运行的系统上，尤其是一个处理大量数据的系统上，你必须每天轮换日志，今天看到几周/几个月/几年前还好的东西坏掉的情况并不少见。使用复杂的联锁系统，可以在不更改任何代码的情况下发现错误。查找硬件、网络、操作系统、配置（尽管应该与代码一起存储）、输入、手动过程等方面的变化可能很困难，因为这些事情中的很多都在很长一段时间内发生变化。日志的全文搜索（无论是在表中还是在文件中）通常是不切实际的。

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

• 输入搜索

  前几天，我注意到一个带有长文本的晦涩“错误”。找出有效文本和破坏系统的文本之间确切边界的最快方法是将文本切成两半，直到找到分界线。（事实证明我是个白痴，但我数香蕉比较好。）

• 概念过程步骤

  大多数人甚至不知道他们大部分时间都在使用二进制（或更好的插值）搜索。这是解决问题的一种非常自然的方式。在考虑包含潜在错误的一长串步骤时，通常明智的做法是首先检查中间步骤之一的输出，以避免检查整个代码时才发现问题出在最后一步。

Answer 3

另一种可能性是您有一个错误，并且您知道它在您的 2 月版本中不存在，但它在您的 4 月版本中（或者更确切地说，您的 4 月版本候选- 您永远不会真正向您的用户发布错误，对？）。

您可以通过修订控制历史进行手动二进制搜索，以缩小引入错误的时间。首先检查两个版本之间的代码，构建它，看看是否存在错误。继续分区，直到你知道它是什么时候被引入的。如果您不知道从哪里开始寻找错误，这可能非常有效，尤其是在您进行相当小的提交时。

这对Subversion非常有效，因为它具有存储库范围的修订号。如果您的 2 月版本是 rev 533，而您的 4 月版本是 rev 701，那么您更新到 rev 617，对其进行测试，然后从那里开始。（实际上，我通常会四舍五入到 600，所以我不必在脑海中做太多的数学运算。）一旦我开始缩小范围，我就会开始查看提交评论并做出有根据的猜测（“我真的不认为这个提交会破坏它”），所以我通常不需要做所有的 log ₂ (n) checkouts。

我从未使用过Git ，但他们使用内置的“ bisect ”命令更进一步。你给它一个起点（什么时候知道它可以工作？）和终点（你什么时候注意到它坏了？），它会自动获取二进制搜索中途点的代码。然后在你构建和测试之后，你告诉它这个版本是通过还是失败；然后它获取下一个中点的代码。您甚至可以告诉它为每个 rev 运行一个命令，并使用命令的退出代码来确定 rev 是通过还是失败，此时它可以全自动运行。

Answer 4

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

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

Answer 5

假设您有一个错误，但您不知道它在哪里。您可以在代码中随机或单步放置断点，在每一站验证数据。然而，更好的策略是在您正在查看的代码块中间选择一个位置。如果那里存在问题，则在起点和当前点之间的中间选择一个点，然后再试一次。如果问题不存在，则在当前点和结束点之间选择一个点，然后重试。继续这种方式，直到您将代码量缩小到一个足够大的块，以便比停止/重新启动更有效地单步执行。这基本上是对您的代码进行二进制搜索。

Answer 6

完整的算法称为Delta Debugging，由信息学教授和《为什么程序失败》一书的作者 Andreas Zeller 开发。

但是，这不仅仅是二进制搜索。二进制搜索仅在开始时完成，一旦二进制搜索不再最小化输入，则采用另一种方法。

完整的算法并不难理解，其实很简单。但是，有时很难重现错误并应用问题是否已重现的决定。

除了这本书，还有关于Udacity的免费在线课程。如果您更喜欢简短版本，请阅读他的IEEE 论文

Answer 7

您可以注释掉代码、添加日志注释或简单地设置断点

非常适合没有错误但功能无法运行的代码，并且您充满了自我怀疑

首先在代码中间设置断点，如果一切顺利，那么你就知道问题不存在

然后将其设置为代码点的 75% - 如果问题出现在这里，那么您知道它在 50% 和 75% 之间的代码中

所以接下来你将它设置为 57%

如果问题仍然存在，那么你再次将其分成两半

基本上你可以在几分钟内找到问题，而不是花费数小时重新分析你的代码

然后它仍然由你来修复它。