对拍：科学的排错方法

导语

　　在做习题时，常常会遇到一类非常棘手的情况：自己写的算法能通过样例数据，提交后却总是WA。通常的原因可能是忽视处理边界情况、样例的数据过弱使非正确算法也能得到正确解、算法存在细节性错误等等。

　　当遇到这种情况时，通常的想法是自己设计一些测试数据以对算法的各个模块依次进行排错，或是检查边界情况是否被考虑到以及一些常见的编程失误（如未清零临时变量以及某个变量的标识符打错等等……）。

　　自己设计测试数据往往并不是一件轻松的事，对于复杂的算法更是如此，人的抽象思维能力毕竟有限。所以，这样排错的效果往往不够好。

　　于是，本文正是要向读者介绍一种科学的，比自己构造样例数据更为高效和可靠的排错方法：对拍。

原理

　　“对拍程序，顾名思义，一个输入给两个程序分别跑一遍，看看对不对的上。”

　　这位博主对“对拍”一词的解释已经比较简洁而清晰了，但仍有些地方需要稍微解释一下。

　　首先，“一个输入”并不是自己徒手构造出的测试数据，而是指利用随机函数生成的有效的数据。
请注意这里使用的形容词是“有效”，或者用更专业的术语来说，“合法”。“有效（合法）”在此处仅指输入数据在形式及数值上符合输入数据的限制。

　　细心的读者可能会想到，如果数据仅仅是有效，那很可能依然无法发现边界情况的问题。很好。如你所见，“有效（合法）”只是对测试数据最基本的要求。而一个精心设计出的题目，其测试数据往往会对各种边界情况或特殊情况进行考察，以此来测试算法编写者逻辑上的完备性以及所使用的算法本身的性能。这样的测试数据不仅仅是“有效（合法）”的，更是“有意义”的。

　　那么，对拍是如何使得仅仅是“有效（合法）”的输入数据就能够检验出算法对“有意义”的输入产生的错误呢？

　　没错，答案很简单，关键在于随机化与重复。随机函数使得测试数据“有意义”的情况可能发生，而重复测试进一步提升了其概率。实践表明，在多次随机数据的输入下，算法的错误点很容易就会表现在输出数据的细微差异上。

　　这里我们可以进一步思考重复输入随机数据这一行为的实质：在对算法进行检测时，我们本身在做的就是一种黑盒测试，即不再试图从内部、从逻辑或数学上严密地论证算法的正确性及效率，而是仅仅通过观察其表现（包括输出数据与所需的时间以及占用的空间以及其跟随数据量的增长等等）对其进行评估。这一方法与科学研究时使用的最广泛而直接的方法——观察实验并统计实验数据——不谋而合。所以笔者称有着这样类似于科学方法的排错方法为：科学的排错方法。

　　回过头来，再来思考随机化与重复这一技巧。直觉上很容易理解的一点就是，多次的随机性测试等效于系统性测试。（具体的论证应该需要大量的数学基础，很遗憾笔者还没有这样的功底，等大学数学学得比较好了我会再回来补上。）原来这就是使得“对拍”威力大增的魔法。

　　其次是“两个程序”。这里的两个程序分别是指存在错误的程序和能够得到正确结果的程序。在日常训练过程中，后者往往是他人公布的可AC代码，而在赛场上，后者则可以是无脑爆搜的算法。总而言之，对第二个程序或者说“标准程序”的要求，只剩下了准确性一项。

　　而所谓的“对不对的上”，意思就是检测错误程序与标准程序的差异之处，并以此推导出程序的错误之处（当然也可以拉出这一组随机生成的测试数据，分环节或模块对两个程序进行进一步的排错）。

　　有了以上的理论基础，我们就可以开始编写对拍程序了。

实现

　　具体实现网上一搜到处都有，此处笔者不再赘述。笔者比较喜欢的是一种利用批处理的管道操作符的版本。笔者将其展示在此处。

@echo off  
:loop  
    rand.exe > in.txt
    my.exe < in.txt > myout.txt
    std.exe < in.txt > stdout.txt
    fc myout.txt stdout.txt
if not errorlevel 1 goto loop  
pause
goto loo

结论

　　让我们总结一下本文的观点：

　　1. 对拍程序是将大量随机生成的“有效（合法）”数据分别输入待排错的程序与正确的程序，而后找出其输出结果上的差异的程序。

　　2. 随机化原则与重复使得仅仅“有效（合法）”的输入数据很可能“有意义”。

　　3. 其原因是多次的随机性测试等效于系统性测试。

　　4. 这一原则同样被应用于科学研究领域，因此利用对拍程序差错具有“科学性”的特点。

　　最后，笔者希望所有阅读这篇文章的人都能有所收获，无论是完全没有试过对拍的读者还是已经试过对拍却对其原理不甚理解的读者。祝各位在练习时都能精神抖擞，并在赛场上取得佳绩。