如何写一个简单的对拍

最近很多同学问我

  • “数据结构的某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

电影爬虫日记 之 豆瓣网爬虫记录

2017年9月29日

最近接到了一个小任务,要求爬取豆瓣、时光网等网站的电影信息并进行少量的数据处理。爬电影确实不是一个难的东西,不就是选择一个相对简单的目标url,写一个脚本进行访问。但是,要想要为何不借此机会,好好研究一下python中的异步以及多线程机制呢?说不定还就写出一个像scrapy一样的爬虫框架了呢!

爬取豆瓣电影列表这件事,也不算什么复杂的工作,因为豆瓣电影本身没有反爬虫机制。

电影列表抓取

方案A

网址:https://movie.douban.com/tag/2017

里面有2017年的所有电影,但是其中有混杂很多的电视剧啥的,总数也仅仅只有4000个。


2017年9月30日

方案B

网址:https://movie.douban.com/typerank?type_name=剧情&type=11&interval_id=100:90&action=

倘若枚举每一个分类的每一个得分档次的每一页,就可以得到大约20000个电影。这可以说非常全面了。


2017年10月7日

电影信息抓取

豆瓣对于每一个电影都有一个自己的id,这个在之前爬取爬虫列表的部分就已经预处理出来了。

页面链接就是普通的电影页面:https://movie.douban.com/subject/26425068/

然而,当我尝试开始使用诸如多线程爬虫时……

豆瓣把我给封掉了……

现在可以确认的消息是

  1. 通过urllib.request.urlopen进行访问,单线程会在几千次左右被封
  2. 通过多线程访问可以在一分钟内被封
  3. 通过IP代理暂时没有看出效果

首先我尝试的是直接将爬取的数据写入数据库,但是感觉比较迷……因为容易被封IP,需要在八小时后自动重新启动。判重等问题非常难处理。

另一种尝试则是通过在ID对应文件中写入数据。网上的爬虫用的是第二种,但是感觉第一种可能会方便一些……吧……

 

湯を沸かすほどの熱い愛

回北京的飞机上看的一部电影。中译名:滚烫的爱,台译名:幸福汤屋。

还好飞机上使用了台译名,幸福汤屋,给人以朴素温暖之感,否则恐怕得和这个电影擦肩而过了。

最近看的日本电影,总有一种温暖与纯真,我的前一篇影评花火,也是这样的一部日本电影。而这种温暖与纯真,译为“滚烫的爱”确实有所不妥。以我这个半吊子日文的感受来看,日文名有沸腾之意,与“汤”双关,而中文的滚烫则没有这一层意思,故显得有些过度。

这部电影的第一个关键词“时间”,生命只剩下两个月的女主,听到拓海埋怨时间太多时的无奈与痛苦。在幸野摆出金字塔与狮身人面像时,一遍遍哀求想活下去。不过,在命运与疾病面前,这种哀求也终归是徒劳了。

第二个关键词“命运”,命运是既定的,但选择确又有所不同。女主拒绝在诊断绝症后进入安宁病房。因为在这个既定的命运中,她希望拥有更多的选择,用剩下的两个月时间,修复了家庭,指引了他人。同样对应命运的,还有每个人物所有的各种缺陷,以及混乱的人物关系。女主在最后几个月中,将这些一一解决。也许比较夸张,不过也给人以震撼。

第三个关键词“死亡”,电影没有怎么提及,却非常引人深思。毕竟,死亡,确实是一个不近不远的话题了。人们想来回避这个词汇,却又逃不出他的魔爪。死亡,意味着你存在的意义永远确定。你究竟带给这个世界什么,在死亡的那一刻,就永远的固定下来。而生的时候,是为了死后对于社会的意义来衡量,亦或是仅仅乐享当下呢?

总之,又一部温暖、感动的电影!