如何写一个简单的对拍

最近很多同学问我

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

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

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

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

gen.py

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

from random import * #randint随机生成整数


if __name__ == '__main__':
    with open('input.txt','w') as f:
        n = 100000 #数据规模
        f.write("%d\n"%n)
        totIn = 0 #当前没有删去的股票个数
        totOut = n #当前所有没有加入的股票个数
        for i in range(n*2):
            if totIn==0 or (totOut>0 and randint(0,1)==1): #加一个股票
                f.write('%d %d\n'%(randint(1,100),randint(1,10000)))
                totOut -= 1
                totIn += 1
            else: #删一个股票
                f.write("%d\n"%randint(1,100))
                totIn -= 1

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

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

std.cpp

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

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

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

check.py

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

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

diff A.txt B.txt 比较A.txt B.txt文件差别,这个diff函数在文件不同的时候返回非零值
./std 执行该目录下std这个程序
./std <input.txt >output.txt 将input.txt作为std的标准输入,output.txt反之

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

import os

if __name__ == '__main__':
    while True:
        os.system('python3 gen.py')
        os.system('./std <input.txt >out1.txt')
        os.system('./prog <input.txt >out2.txt')#自己的程序
        if os.system('diff out1.txt out2.txt'):
            print("GG")
            break
        print("Good!")

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

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

 

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

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

问:写这个耗费时间啊!

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

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

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

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据