维基百科

User:小老虎3018/沙盒/编辑备用

< User:小老虎3018 | 沙盒

在线评测系统（英語：Online Judge，缩写OJ），是一种能完全自动地根据用户上交的源代码、二进制可执行文件或是纯文本输出内容，来实时评测其能否满足指定任务要求的系统。早在1961年，斯坦福大学就已经有了一套成形的利用测试数据检验源代码执行指定任务的系统，但不能明确指出错误在哪出现。[1][2]；而世界范围熟知的第一个在线评测系统，由西班牙Valladolid大学的Ciriaco García de Celis开发的UVa线上解题系统也于1995年诞生[3]；但这一概念在2001年才被首次定义[4]。自2000年开始，在线评测系统的想法开始广为传播并实践，如Codeforces、POJ等一大批不同定位的评测网站也如雨后春笋般地出现。如今的在线评测网站除了提供评测服务外，还会举行挑战性编程比赛，并涉及教育培训、招聘评判等各方面；而组织程序设计比赛的主办方，也会建立公开的评测系统供选手练习。

可满足算法竞赛中根据准备好的数据，自动评价选手提交的有特定任务的源程序。[5]

(x)近年来（2016年或更早）亦出现一些针对求职面试的在线评测系统。许多OJ网站会自发组织一些竞赛。此外，OJ网站通常会设立用户排名，以用户的提交答案通过数多少或某个题目执行时间快慢为排名依据。[6]

历史

评测系统已有愈半世纪的 （和acm/ioi关系）

构成

一般的在线评测系统除需满足基本的评测功能外，还需要能清晰显示任务的具体要求，并给予评测的反馈。评测系统还会提供额外的与评测紧密相关的功能，如Hack。当然，也有部分评测系统着眼于源代码的编译环节，并支持多种语言的在线编译；社区功能也是大多数在线评测系统所拥有的。

评测

严格。其中，评定测试中使用的数据一般由网站或出题人预先准备，而无需用户自行上传，这种评测方法又被称作黑盒测试。[7]

原理与实现

一般可以认为，评测分为提交代码、评定测试、计分反馈三个步骤，而这些步骤应该能够自动化或半自动化完成。

提交代码时，如果是需要编译才能运行的源代码，需由评测系统先编译生成可运行程序，再使用程序或直接读取解释型代码进行检测，验证其能否在测试环境下运行。能正常运行而开始评定测试时，依照指定的输入输出形式（一般有标准输入输出和文件输入输出），利用指定题目的测试数据检测程序；只有当其运行时不出现导致程序崩溃的计算等错误，过程中不超出时间和空间限制，并且输出的答案符合题面要求时，某个特定的测试数据对应的测试点才可被认为通过。随后，根据各测试数据的评测情况和题目要求对用户的解法评分。[8]

部分题目由于解法不能在短时间内求解等原因，需要根据下发的数据在本地生成输出，并交由在线评测系统对比，该过程于提交代码有一定的区别，一般称为“提交文件”。

在具体的操作过程中，一般是评测系统通过调用链接动态库

评测反馈

（改） 在提交程序之后，在线评测系统会根据题目的测评情况，返回评测结果。只有返回“Accepted”状态，才表示题目通过，选手才会获得成绩。不同OJ评测结果略有出入，但常见的评测结果大致分为以下三类。

等待评测 Pending 系统繁忙，用户的解答程序正在排队等待。 Pending Rejudge 因为数据更新、比赛后重测或其他原因，系统将重新判定你的答案。
Compiling 对于需要编译的源程序文件，正在将其编译为可执行文件。 Running & Judging 正在运行提交的程序并与标准数据进行比较。
评测不通过 Wrong Answer WA 答案错误。 Runtime Error RE 运行时错误，程序崩溃。
Compile Error CE 编译错误。 Time Limit Exceeded TLE 运行超出时间限制。
Memory Limit Exceeded MLE 超出内存限制。 Output Limit Exceeded OLE 输出的长度超过限制。
Presentation Error PE) 答案正确，但是输出格式不符合题目要求。在一些要求比較嚴格的比賽中，格式錯也會被視為答案錯誤
评测通过 Accepted AC 程序通过了某个或所有测试点的评测。
括号内代表常用简称。参考来源：[7]


在測試過程中，只有未發生以上幾種錯誤的情況下才算做通過。

  • （簡稱AC）：程序通过。

<->挑战性编程>另外，在整場比賽中通過了所有題目又俗称「AK」或是「破臺」。

一些比賽的測試點可以給出「部分分」，例如答案正確但不够优，或者選手沒有完全完成題目所給的任務等。[7]

题目数据

题目应该有解。算法正确性。笑嘻嘻数据强度：


安全问题

用户可能会提交与解决题目无关的代码让评测系统执行，甚至多次对设定时限较大的题目提交代码运行死循环语句，或在编译时进行头文件攻击，直接读取机器随机输出造成无限编译，占用时间；直接输出过大的文件，或利用源代码在编译时出过大的可执行程序，占用空间；直接调用系统指令或文件让系统敏感数据泄露，或使评测机无法再受理其他提交，例如system("shutdown now");。这些攻击亦可被划分为为编译和运行攻击。[9]

评测系统多会对用户提交的源代码实施过滤，但宏定义可有效绕过这种防范方式。将评测进程放入类似Docker的沙盒中以进行隔离，或限制评测进程对无关文件的访问，也是一种常用的解决途径。[10]

将进程、对代码进行哈希以防止抄袭和重复提交等。（+）

效率、稳定问题

要注意的是，出于公平考量，对于一道同样的题目，或是同一比赛、同一平台的评测，应该在相同的测试环境下进行，并能保证评测环境稳定，反馈信息可靠。[5]

Hack

编译

社区功能

抄袭和重复提交

（->需要更多资料） 其中，Virtual Judge/Remote Judge是一种特殊的在线评测系统。与其他在线评测系统不同的是，Virtual Judge系统本身并没有任何测试数据，而是通过在其他在线评测系统中注册的机器人账号进行测试并抓取测试结果。因此可以在只有题目而没有测试数据的前提下建立竞赛。[11][12]

分类

时至今日，仍没有能被广为接受的针对在线评测系统的分类。


实例

在线评测系统是由西班牙Valladolid大学的Ciriaco García de Celis于1995年开发的，当时用于该校参加ACM/ICPC西南欧区域赛选拔队员。[3]

现在较为著名的在线评测系统有西班牙的UVaOJ、俄罗斯的SGU、Timus、Codeforces、波兰的SPOJ、美国的TopCoder、中国的POJ（北京大学）、ZOJ（浙江大学）、HDOJ（杭州电子科技大学）等。[7]

（改） 不同群体中不同OJ使用的频率也不同，学生中常会因为教师的要求使用公开/校内OJ，为此，许多公开OJ也提供了个性化服务，如Vijos中的“域”服务[13]，OpenJudge、洛谷、Vjudge中的团队服务。

在特定群体中亦有一些流行的在线评测系统，例如中國初中[來源請求]选手中流行的Vijos、进阶选手使用的BZOJ（现称“大视野在线评测”）、hihocoder、美国求职者中流行的LeetCode等。

Codeforces是近年来比较知名的在线评测网站，它有向全世界用户提供周期性的比赛，并同时有英文和俄文两个版本。每次参与完比赛后，用户的分数便会根据类似于等级分的评判标准变化。[14][15]网站会根据用户分数划分为三个层次的比赛，比赛过程中或赛后会提供Hack功能，该功能后来也被其他在线评测网站效仿。

局限性

参见

[16]

参考文獻

  1. ^ doi:10.1.1.31.3506
    {{cite doi}}已停用，请参见{{cite journal}}。
  2. ^ George E. Forsythe, Niklaus Wirth. Automatic grading programs. Communications of the ACM. 1965-05-01, 8 (5): 275–278 [2019-06-25]. doi:10.1145/364914.364937. 
  3. ^ 3.0 3.1 Miguel A. REVILLA; Shahriar MANZOOR; Rujia LIU. Competitive learning in informatics: the UVa online judge experience (PDF) (2008,2). Olympiads in Informatics: 131–148 （英语）. 
  4. ^ Andy Kurnia, Andrew Lim, Brenda Cheang. Online Judge. Computers & Education. 2001-05, 36 (4): 299–315 [2019-06-25]. doi:10.1016/S0360-1315(01)00018-5 （英语）. 
  5. ^ 5.0 5.1 Szymon Wasik, Maciej Antczak, Jan Badura, Artur Laskowski, Tomasz Sternal. A Survey on Online Judge Systems and Their Applications. ACM Computing Surveys. 2018-01-04, 51 (1): 1–34 [2019-06-25]. doi:10.1145/3143560 （英语）. 
  6. ^ Programming Challenges (Skiena & Revilla) ISBN 0387001638, ISBN 978-0387001630
  7. ^ 7.0 7.1 7.2 7.3 劉汝佳. 算法競賽入門經典. 清華大學出版社. 2014-06. ISBN 978-7-302-35628-8. 
  8. ^ 李定才,瞿绍军,胡争,段兵,成幸毅,唐强. 基于Windows的在线评测系统的安全性研究. 计算机技术与发展. 2011-09, (2011年第9期): 204–207. 
  9. ^ 阮行止. OJ技术思考：评测安全. 知乎. 2017-05-18 [2019-03-15]. 
  10. ^ 引用错误：没有为名为aq的参考文献提供内容
  11. ^ Virtual Judge. （原始内容存档于2016-09-20）. （英文）
  12. ^ Welcome to NEUQ Virtual Judge. （英文）
  13. ^ 帮助 - Vijos. vijos.org. [2017-06-06] （中文（中国大陆））. 
  14. ^ Open Codeforces Rating System [updated on October 2015]. Codeforces. 2015-11-01 [2019-01-18] （英语）. 
  15. ^ Codeforces Rating System. Codeforces. [2019-01-18] （英语）. 
  16. ^ Online Judge系统的优化. [2019-06-25]. doi:10.3969/j.issn.1003-3254.2011.08.025. 


检索自“https://zh.wikipedia.org/w/index.php?title=User:小老虎3018/沙盒/编辑备用&oldid=54960869”