線上評測系統

線上評測系統

線上評測系統(Online Judge,OJ)是一種在編程競賽中用來評測參賽程式的線上系統,也可以用於平時練習。近年來(2016年或更早)亦出現一些針對求職面試的線上評測系統。許多OJ網站會自發組織一些競賽。此外,OJ網站通常會設立用戶排名,以用戶的提交答案通過數多少或某個題目執行時間快慢為排名依據。

定義

線上系統是指針對系統用戶的可提供線上服務的一種系統,或指一個線上的評測系統。通過該系統對程式代碼進行編譯和執行。具體過程為使用者登入瀏覽器,將自己的程式代碼提交,系統後台對程式進行編譯和執行,之後系統使用設定好的輸入和輸出來比對,査看程式的正確性,其技術理論依據是軟體工程中的黑盒測試。所用的瀏覽器沒有具體的要求,如微軟公司的IE、谷歌公司的Chrome(不同瀏覽器會有不同的限制,這需要通過瀏覽器核心而定),系統可以判定的程式開發語言也是多樣的。

用戶通過瀏覽器線上提交自己的程式,考慮到系統安全因素,需要對程式代碼的編譯執行時間、對記憶體的使用占有進行一定的限制。首先,系統後台在收到用戶提交的程式後,對未知的程式進行編譯。編譯使命令可以使用CCC,其調用方法類似於調用Shell命令。編譯通過的程式接下來就要進行正確性檢測,測試程式正誤的方法是黑盒測試,使用根據程式而設計的測試數據即測試用例來進行輸入輸出比對,進而得到程式的正確性 。

原理

算法競賽通常採取黑盒測試,事先準備好一些測試數據,然後用它們來評測選手的程式。在線上評測系統中,用戶需要提交原始碼至伺服器,伺服器會編譯用戶的原始碼,然後執行原始碼生成的執行檔(或用解釋方式執行,或直接執行腳本檔案),得到其輸出的結果,並與正確結果比較。

為防止攻擊和惡意提交,伺服器必須採取一定的安全措施,例如對用戶提交的原始碼實施過濾、將進程放入沙盒以進行隔離、對代碼進行哈希以防止抄襲和重複提交等。

Virtual Judge是一種特殊的線上評測系統。與其他線上評測系統不同的是,Virtual Judge系統本身並沒有任何測試數據,而是通過在其他線上評測系統中註冊的機器人賬號進行評測並抓取評測結果。因此可以在只有題目而沒有測試數據的前提下創建競賽。

題目狀態

在提交程式之後,線上評測系統會根據題目的評測情況,返回評測結果。只有返回“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):程式通過。另外,在整場比賽中通過了所有題目又俗稱“AK”或是“破台”。

•一些比賽的測試點可以給出“部分分”,例如答案正確但不夠優,或者選手沒有完全完成題目所給的任務等。

示例

首次使用OJ系統進行計算化程式評測的是在2000年的新加坡國立大學,該學校把數據結構與算法的巧試運用在OJ系統中。但是該系統的使用率並不是很高,大多數的情況下還運學生將自己的作業使用FTP伺服器以及電子郵件的方式提交給老師,然後老師去逐個檢査學生的程式,利用該系統直接對學生程式進行評滿還不是很普遍。

Va線上評測系統是由西班牙瓦雅多利大學開發的自動化線上程式評判系統,包含了超過4300個程式設計問題並且開放給所有人註冊參與解題,有超過10萬名用戶。用戶可以使用C(C89)、C++(C++98)、Pascal、Java、C++11或是Python撰寫程式以解決題目中提出的問題,其中Java選項在2001年開放,C++11選項在2014年開放,Python選項在2016年開放。UVa同時也舉辦程式設計競賽,在競賽環境中用戶必須在限制的時間之內解決一組題目。TopCoder,是一家專門組織電腦程式設計競賽的公司。TopCoder 線上舉行算法競賽(SRMs)、組件設計競賽和組件開發競賽。算法競賽在世界上與ACM、Google Code Jam並稱為三大賽。

不同群體中不同OJ使用的頻率也不同,學生中常會因為教師的要求使用公開/校內OJ,為此,許多公開OJ也提供了個性化服務,如Vijos中的“域”服務[7],OpenJudge、洛谷、Vjudge中的團隊服務。在特定群體中亦有一些流行的線上評測系統,例如中國國中選手中流行的Vijos、進階選手使用的BZOJ、中國大學生使用的計蒜客,hihocoder、美國求職者中流行的LeetCode等。

相關詞條

熱門詞條

聯絡我們