从零开始的代码评测系统设计与实践(序)

姐姐大人,姐姐大人,你用过在线代码评测工具吗?
蕾姆,蕾姆,用过呢,真好用,给我也整一个……

0x00 我为什么要开发OJ?

在线判题系统(Online Judge)是一种在编程竞赛中用来测试参赛程序的在线系统,也可以用于平时练习。

相信参加过ACM-ICPC、IO的童鞋们都对它不陌生吧,那个偶尔让你产生许许多多的小问号,想AC却又不停的WA,做题做到停不下来的系统。

五年前,作为前ACM校队队员,在深感自己太菜的技术后,一次突发奇想和老师讨论起了怎么把OJ用到教学中去,让学弟学妹们也被折腾一下(这句划掉),从此给自己挖了一个巨大的坑。

0x01 OJ是怎么工作的?

小学二年级的知识告诉我们,你输入的代码,会被OJ的判题机编译、运行。判题机将通过控制程序的标准输入流,模拟你的输入操作。当程序运行结束后,从标准输出流获取到的数据,即是你程序的答案,然后将它与标准答案进行比较。

当然,如果程序在一开始就错了,或者在运行过程中出现了错误,又或者超出了题目设定的资源限制,那么你也会得到相对于的错误提示,供你排查问题。

通常意义上,OJ的判断非常严格,错一个字都是错,少个空格也是错。所以很多时候,折腾了半天,结果跑完第一组数据过了,第二组数据又超时…

0x02 这就是我要整学弟学妹的理由?

没错,人要经历挫折,有挫折才会有成长,才会明白做啥都好不要做程序员啊

这种基于黑盒测试的代码评测模式在ACM-ICPC竞赛中最为常见,具有如下优点:

  1. 判题程序开发难度较低。
  2. 判题程序主要实现进程监控和数据直接比对,运行效率高,占用资源低。
  3. 测试数据易于构造和编辑,可以通过标程(相当于参考答案)生成。
  4. 兼容多语言多平台,扩展性强。

那么,具有以上优点的系统,又是为何被老师和同学边用边骂骂咧咧的呢?究竟是道德的沦丧,还是人性的弱点?不,是系统的缺点:

  1. 测试数据均为静态数据,仅使用“运行结果”来判定代码正误。判题太过于严格了,动不动就WA,同学们的心态都炸了。求A+B问题 数据输入:1 1 答案输出:2 同学:我输出文字『1+1=2』,为什么判我错? 判题机:你哪那么多废话呢,输出『2』不就好了?
  2. 无法进行代码分支预测,无法判定代码是否符合题目要求,无法检测暴力过题的情况。
  3. 系统设计初衷是面对编程初学者用户练习,黑盒测试不能直观反映代码存在一些问题,如:数组或变量未初始化、循环不能跳出和条件语句结构臃肿等等。

上述问题都解决了吗?好吧我承认,并不好解决,于是有了很多很多折中的方案。但这些并不是本系列文章想要讨论的事儿,如果上述问题在技术上有好的建议,非常欢迎你和我一起探讨。

0x03 问题都没解决,写啥系统呀?

问题来了,先有鸡还是先有蛋?系统都没有,解决啥问题?咱也不能老是下半年中美合拍呀就解决问题了呀,啥事都得自己搞搞才能进步嘛

万事开头难,但也最怕是遇到问题不百度直接自己闷声捣鼓的,对,说的就是不才的本人了。我才不会告诉你我当年的OJ整了好几次大版本,每次都是重新来过的(也就是把原来的技术方案否了)。

通过不断的积累,不断的试错,才有了今天的WeJudge系统的技术体系。也许在众多大公司开发的OJ相比起来,它像是一个初来乍到的新同学。我希望通过这篇文章,与你分享关于她的故事。

0x04 关于WeJudge

当年1个月时间开发出来的0.3,到半年后的1.0,再过一年的2.0,再到后面将近三年时间3.0正式发布。我从一个人孤军奋战到2.0,到现在3.0是我带两个学弟一起搞,前前后后经历了太多了。虽然她一分钱都没赚,靠的是学校提供的服务器和网络,基本上用爱发电,但我相信开发她的过程本身就是一种成长。

如果未来有一天,我们确实运营不起她了,也许会在github上看到她完整的样子,在此之前,我们依然在努力。

我在github上开源了判题机相关代码,未来也将会分享更多的东西。

判题机:https://github.com/LanceLRQ/deer-executor (参考dojiong/Lo-runner)

1.0版源程序:https://github.com/LanceLRQ/wejudge

3.0 网站:https://oj.bnuz.edu.cn ,未来计划重新用回 wejudge.net

0x05 未来我会谈谈什么呢?

很久很久以前就一直在想把自己的技术经验、经历写出来分享,也好回顾一下这些年走过的路。因为一些生活、找工作失利等诸多的原因,可能自己在心态有些不太好,感觉技术上停滞不前了。所以打算写一些文章,努力让自己回忆起那些年努力去为梦想奋斗的日子吧。

我将会围绕以判题机为中心,一步步阐述规划、设计和开发一套完整的在线判题系统所涉及到的问题,以及我的想法、看法、解法。新人一个,有说的不足的地方还请大神们多多指教。毕业快两年了,业余时间一直在参与这个项目开发。

如果你有兴趣阅读这个系列的文章,你需要有一些数据结构、算法和操作系统的基础,并了解C语言、Go语言或风格和C语言类似的语言的语法格式。文章主要是阐述思路,不会实际的业务代码,并且我也会尽量把原理说的简单一些。难免会有不专业的词汇或比喻,还请见谅。

0x06 实战回顾

2020年04月,顺利举办“2020年粤澳计算机程序设计大赛网络赛”。回顾参考:

https://www.zhihu.com/question/390424213/answer/1179758442