如何写一个简单的对拍

最近很多同学问我

  • “数据结构的某PA交上去WA了怎么办,我明明过了样例的呀!”
  • “我如何才知道我的程序在大数据下跑的多块?小数据什么算法都看不出差别?”
  • “求救,我已经盯着我的程序看了两个小时了”

其实这种东西都可以通过一种叫做对拍的方式解决。对拍的核心思路是:写一个程序造数据,写一个程序暴力跑数据,然后和你的正解程序的输出进行比较。

这里面涉及到了三个程序:

  • 数据生成程序gen.py/.cpp
  • 暴力程序std.cpp
  • 对拍程序check.py/.sh/.bat

gen.py

全称generator.py,他的作用是你调用一次这个程序,自动给你生成一个随机输入数据,我们以PA4为例,我们可以写一个这样的程序。

将这个程序写入 gen.py 中,则每次调用 python3 gen.py 都可以在 input.txt 文件中生成一组规模100000的数据!

到这里,我们已经可以解决不清楚程序运行速度的问题了:你最大规模数据都有了,为啥还不能看出来呢?

std.cpp

对于大部分题目,我们都能找到一种不那么好的解法,比如PA4,我们实际上可以讲每天的区间即权值,放到一个struct数组里面,对于每一个时刻,查询包含该时刻的区间权值最大值。

放代码恐怕我就要被邓公请去喝茶了,所以大家自己写咯。

目标是写一个程序,交到网站上不会WA,只会TLE的那种。

check.py

现在一个比较直接的方式是:每次运行一边generator,在运行一边std,比较输出文件。但是这样非常慢。为什么我们不能将这个过程自动化呢?

这里需要科普几个终端命令:

首先,我们可以通过bash/bat等批处理文件实现,不过看在读者基本都不会愿意再学一门新语言,我们直接用我们会的python实现,python的 os.system() 可以调用一个系统命令,并且返回结果。

大概程序长成这样,调用 python3 check.py 就自动无线循环造数据测试啦。

这里我们需要修改 gen.py 里的数据范围,使得刚好到你的暴力程序能两三秒跑出来的规模。这样一分钟你就可以测试三四十组数据了。

 

这就是一个最简单的对拍程序。对拍对于数据结构的题简直是神器,因为这类问题总是会存在一个非常暴力,但是不容易写错的解法。而且熟练之后,三个程序加起来也就是二十分钟的事。

*注,上面的代码都是手打的,没有测试过哦……错了评论一下就好了,思路是对的

问:写这个耗费时间啊!

答:你盯着代码不动更费时间。

问:不会写暴力,或者暴力我也可能写错怎么办

答:找A了的同学的代码当std

发表评论

电子邮件地址不会被公开。 必填项已用*标注