GOJ系統(tǒng)的研究與實現(xiàn)

李偉光 陳希

摘 要：隨著ACM-ICPC（國際大學(xué)生程序設(shè)計競賽）在世界各地的廣泛舉辦，競賽中使用的OJ（在線評判系統(tǒng)）也成為各大高校內(nèi)部訓(xùn)練、舉辦競賽的必備系統(tǒng)。為適應(yīng)民辦高校進(jìn)行ACM選拔和備賽的需要，開發(fā)了GOJ（光華在線評判）系統(tǒng)。該系統(tǒng)包括前臺Web網(wǎng)站（B/S架構(gòu)）、后臺評判系統(tǒng)（C/S架構(gòu)）和數(shù)據(jù)庫3部分，在Windows下的.NET平臺進(jìn)行開發(fā)。評判程序是軟件模擬的一個C/S架構(gòu)程序，這樣不僅節(jié)省了評判服務(wù)器的成本，在安全方面也將風(fēng)險降至最低。

關(guān)鍵詞：GOJ B/S C/S .NET

中圖分類號：TP31 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2015）10（a）-0046-03

ACM-ICPC是由國際計算機界歷史最悠久、最具權(quán)威性的組織ACM（Association for Computer Machinery，計算機學(xué)會）主辦的國際大學(xué)生程序設(shè)計競賽，是世界上公認(rèn)的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計競賽。

競賽中使用的OJ（在線評判系統(tǒng)）也成為各大高校內(nèi)部訓(xùn)練、舉辦競賽的必備系統(tǒng)。Online Judge系統(tǒng)（簡稱OJ）是一個在線的評判系統(tǒng)。用戶可以在線提交程序多種程序（如C、C++、JAVA）源代碼，OJ系統(tǒng)對源代碼進(jìn)行編譯和執(zhí)行，并通過預(yù)先設(shè)計的測試數(shù)據(jù)來檢驗程序源代碼的正確性。一個用戶提交的程序在Online Judge系統(tǒng)下執(zhí)行時會受到比較嚴(yán)格的限制，包括運行時間限制、內(nèi)存使用限制、安全限制等。用戶程序執(zhí)行的結(jié)果將被Online Judge系統(tǒng)捕捉并保存，然后再轉(zhuǎn)交給一個裁判程序。該裁判程序比較用戶程序的輸出數(shù)據(jù)和標(biāo)準(zhǔn)輸出樣例的差別，或者檢驗用戶程序的輸出數(shù)據(jù)是否滿足一定的邏輯條件，然后返回給用戶一個狀態(tài)，如通過（Accepted，AC）、答案錯誤（Wrong Answer，WA）、超時（Time Limit Exceed，TLE）等等，因此一個好的OJ系統(tǒng)對于ACM-ICPC是非常重要的 [1]。

1 GOJ系統(tǒng)構(gòu)成

整個GOJ系統(tǒng)分為3個部分：（1）前臺Web網(wǎng)站，供用戶查看題目、提交程序，供管理員管理整個OJ系統(tǒng)。（2）后臺評判系統(tǒng)，這是GOJ系統(tǒng)的核心部分，它用來對用戶進(jìn)行練習(xí)或者比賽所提交的代碼進(jìn)行評判，其檢測過程非常嚴(yán)格。（3）GOJ系統(tǒng)所使用的后臺數(shù)據(jù)庫系統(tǒng)。

GOJ系統(tǒng)的整個實現(xiàn)過程是：用戶通過前臺B/S架構(gòu)的Web網(wǎng)站提交程序代碼至數(shù)據(jù)庫中，然后由后臺C/S架構(gòu)的評判程序發(fā)現(xiàn)數(shù)據(jù)庫中用戶提交的代碼，并對其進(jìn)行編譯、運行、評判，最后由評判程序更新數(shù)據(jù)庫中用戶提交的程序狀態(tài)，并將該結(jié)果顯示在前臺網(wǎng)站。

2 需求分析

2.1 基礎(chǔ)部分功能需求

GOJ系統(tǒng)基礎(chǔ)部分應(yīng)具有以下功能：第一，具有能夠提交題目，給出提交結(jié)果的功能。第二，答題結(jié)果由GOJ用戶提交，因此，應(yīng)具有用戶的注冊和登錄功能。第三，應(yīng)具有排名功能，方便教師了解學(xué)生在系統(tǒng)上的訓(xùn)練情況，也能促進(jìn)學(xué)生學(xué)習(xí)的熱情。排名功能可以有：每日排名、每周排名、每月排名和總排名。第四，提交情況應(yīng)可以方便查看，而且提交情況應(yīng)具有篩選功能。第五，每個題目應(yīng)具有提交狀態(tài)分析功能，即根據(jù)提交狀態(tài)表統(tǒng)計出每個題目的通過數(shù)、答案錯誤數(shù)等數(shù)據(jù)，讓用戶了解該題目的難易程度。

2.2 競賽部分功能需求

GOJ的開發(fā)主要就是為了用其舉辦ACM賽事，因此賽事部分應(yīng)具有以下功能：第一，競賽應(yīng)分類型，包括內(nèi)部賽和公開賽兩種。內(nèi)部賽只允許使用內(nèi)部發(fā)放的帳號，公開賽在競賽之前、競賽過程中用戶可以登錄GOJ的Web網(wǎng)站進(jìn)行注冊參賽。第二，要具有判斷本場比賽的狀態(tài)功能。比如，比賽若未開始，不允許任何用戶進(jìn)入比賽查看題目，而比賽一旦結(jié)束，不允許任何用戶提交題目。第三，賽事題目不允許重復(fù)提交，每個隊伍提交成功的題目不允許再次提交。第四，要具有參賽隊伍排名功能，這也是ACM競賽最重要的部分。按照提交成功的題目數(shù)、提交耗時為所有參賽隊伍排名。其中，參賽隊伍要分組，包括標(biāo)準(zhǔn)參賽隊伍和觀摩隊伍。排名表也要足夠詳細(xì)，能夠看出參賽隊伍每道提交題目耗費的時間和提交次數(shù)。第五，提交題目的統(tǒng)計功能。要能夠統(tǒng)計出整場競賽，每個題目的通過數(shù)、答案錯誤數(shù)等數(shù)據(jù)，用來觀察題目的難易程度，方便賽后分析題目。

2.3 管理部分功能需求

GOJ的用戶應(yīng)至少分成3種：第一種是普通用戶，第二種是管理員，第三種是超級管理員。其中超級管理員具有最高權(quán)限，能夠管理GOJ所有功能。管理員能夠管理GOJ部分功能和普通用戶。普通用戶只能管理自己的用戶，即修改個人信息和密碼，以及其它基礎(chǔ)操作。超級管理員或管理員登錄后，能看到進(jìn)入GOJ管理頁面的鏈接，而普通用戶則無法進(jìn)入GOJ管理界面。

GOJ管理部分應(yīng)具有以下功能：第一、賽事管理功能，包括添加、修改、刪除賽事。第二、題目管理功能，包括GOJ基礎(chǔ)題庫管理和賽事題目管理。題目管理包括題目的添加、修改、刪除功能。第三、用戶管理功能，要能夠管理GOJ基礎(chǔ)部分的所有用戶，包括用戶信息的查看、修改，以及競賽參賽用戶的添加、查看、修改功能。由于參賽用戶往往很多，并且由管理員一人添加，所以參賽隊伍要具有批量添加功能，參賽隊伍的密碼要能夠隨機生成。參賽隊伍瀏覽頁面要具有為參賽隊伍隨機排列座位的功能。第四、用戶提交代碼的查看功能。要能夠查看用戶提交的源代碼，為以后的打印功能做準(zhǔn)備。

3 設(shè)計部分

GOJ的基礎(chǔ)部分模塊設(shè)計如圖1所示。在這里我們把Web網(wǎng)站的頁面設(shè)計成英文界面，并且使用OJ中最常見的詞匯，讓用戶在使用我們的GOJ之后也可以快速的適應(yīng)其它OJ。

圖1中第2行模塊將在網(wǎng)站的菜單欄直接顯示。其中“Online Judge”模塊包括“Home”（返回主頁）和“FAQ”（進(jìn)入FAQ頁面）兩部分?！癈ontests”按鈕將鏈接至賽事列表。Contests下面的分支是由點擊Contests按鈕進(jìn)入賽事列表選擇一場賽事之后的菜單欄顯示?！癙roblem”包括“Problem List”（題目列表）、“Status”（提交狀態(tài)頁面）和“Submit”（提交頁面）3部分。從“Problem List”進(jìn)入題目列表，選擇題目之后可以瀏覽題目，以及具有查看題目提交情況和提交本題目代碼的鏈接?！癆uthors”包括“Ranklist”（總排名）、“Day Ranklist”（每日排名）、“Week Ranklist”（每周排名）和“Month Ranklist”（每月排名），供用戶查看排名情況。Member模塊登錄之后字模塊將變成“Modify Information”，“Modify Password”，“Logout”3個子模塊，菜單欄上的Member字樣將會被用戶的用戶名所替代。如果登錄用戶具有管理員權(quán)限那么菜單欄上Member之后將會增加一個“OJ管理”按鈕，點擊之后進(jìn)入GOJ管理系統(tǒng)。

GOJ的管理系統(tǒng)模塊設(shè)計如圖2所示。

由于管理系統(tǒng)是由內(nèi)部工作人員使用，在這里為了使用方便將更多的使用中文。其中“Online Judge”用來返回OJ首頁。賽事管理用來瀏覽當(dāng)前的賽事列表，在列表選中賽事之后可以修改和刪除賽事。題目管理包括OJ基礎(chǔ)部分題目的添加、修改、刪除以及賽事題目的添加、修改、刪除。用戶管理模塊，包括添加參賽隊伍，其中添加參賽隊伍要能夠批量添加參賽隊伍，隊伍密碼隨機生成。管理參賽隊伍能夠編輯和刪除參賽隊伍，并且能夠隨機排列座次。OJ用戶管理要能夠管理OJ所有的用戶信息，包括修改用戶信息和刪除用戶。如果是超級管理員登錄，將會多增加一個“管理員管理”的子模塊。代碼查看包括賽事提交代碼、OJ提交代碼，用來查看用戶提交的源代碼，也為以后的打印功能預(yù)留下擴(kuò)展空間。GOJ管理系統(tǒng)的母板頁將會增加用戶權(quán)限檢查的功能，用戶如果未登錄或者不是管理員將無法進(jìn)入GOJ管理系統(tǒng)。

數(shù)據(jù)庫[2]設(shè)計如下所述。

用戶要能夠提交題目就一定要有一個表來存儲題目，并且這個表的字段要包括題目的信息，那么我們?yōu)檫@個表起名為tb_Status（狀態(tài)表），狀態(tài)表的主鍵應(yīng)該是一個自增主鍵，其它字段應(yīng)包括提交的題目號、題目提交的狀態(tài)（默認(rèn)值為Waiting）、提交語言，還有等待更新的運行時間、內(nèi)存使用，提交既有的代碼長度、提交者、提交時間、提交代碼，這張狀態(tài)表將是OJ的核心表格，前臺Web用戶通過向此表添加代碼，后臺評判程序更新此表狀態(tài)等字段來向前臺用戶反饋出用戶提交代碼的運行結(jié)果。

狀態(tài)表中需要題號和提交者兩字段，因此還需要題目列表和用戶表。

用戶表一定要有用來登錄的用戶ID和用戶密碼，同時也要有用戶的個人信息，包括用戶名、電話號和email等。狀態(tài)表的提交者字段應(yīng)該是用戶表中用戶ID在狀態(tài)表的外鍵。用戶有管理員、超級管理員和普通用戶之分，由于管理員只是少量用戶所以我們單獨建立一張管理員表，包括兩個字段即可，一是管理員ID，用來引用用戶表的用戶ID，另外一個是管理員級別。

在題目表中，能唯一標(biāo)識一道題目的就是題號，所以題目表中的主鍵就是題號。在這里題號也可以設(shè)置為一個自增主鍵方便添加題目。其它字段包括題目標(biāo)題、題目時間上限、題目內(nèi)存上限、題目總提交數(shù)、通過數(shù)、題目描述、題目輸入描述、題目輸出描述、輸入用例、輸出用例以及用來評判用的并且是用戶不可見的評判輸入、輸出用例。

GOJ系統(tǒng)最核心的用途就是安排一場ACM競賽，那么每場競賽就要有其自己的屬性。因此我們建立賽事列表，為了方便使用賽事列表的主鍵我們使用自增主鍵，其它字段應(yīng)包括賽事標(biāo)題、賽事開始時間、賽事時長以及賽事類型。參加ACM競賽的角色應(yīng)該是一只隊伍，因此要建立參賽隊伍表。首先要標(biāo)識此隊伍參加了哪場競賽，所以一定要使用賽事列表中的賽事ID主鍵在這里，同時也要標(biāo)識這場競賽中的隊伍，那么我們在這里把賽事ID和隊伍ID設(shè)置為聯(lián)合主鍵，共同決定隊伍表中一條記錄。參賽隊伍要有登錄用的密碼、隊伍類型、隊伍所在學(xué)校、隊伍名稱、教練姓名、隊員1姓名、隊員2姓名、隊員3姓名以及座位號。ACM競賽最終要使用的就是競賽排名，排名是根據(jù)每個隊伍在競賽中所取得的成績排列的，那么每個隊伍的成績就是每個隊伍應(yīng)該具有的屬性，因此將標(biāo)識成績的屬性添加到隊伍列表中包括提交總數(shù)、耗時總時間、每道題目的耗時、每道題目的提交次數(shù)。

對于賽事題目列表，在基礎(chǔ)部分的題目列表基礎(chǔ)上要增加賽事ID和題目顏色（ACM競賽中每道題目對應(yīng)一種氣球的顏色），題號和賽事ID作為聯(lián)合主鍵。賽事提交狀態(tài)表也是要增加一個賽事ID，由于狀態(tài)表中的主鍵是自增主鍵，在這里也不需要再設(shè)置聯(lián)合主鍵了。

4 結(jié)語

通過對GOJ系統(tǒng)的設(shè)計與開發(fā)，得出以下結(jié)論。

（1）系統(tǒng)架構(gòu)方面：一個完整的系統(tǒng)不一定是C/S架構(gòu)或B/S架構(gòu)。如果需要可以同時使用兩個架構(gòu)，各取其優(yōu)進(jìn)行組合。

（2）開發(fā)平臺方面：GOJ沒有像以往的在線評判系統(tǒng)一樣在Linux平臺下開發(fā)，而是在Windows下的.NET[3]平臺進(jìn)行開發(fā)。.NET平臺有著高效的開發(fā)和維護(hù)效率，圖形化界面方面也要優(yōu)于Linux。并且，在前臺網(wǎng)站、評判程序和數(shù)據(jù)庫三大模塊的相互調(diào)用方面可實現(xiàn)無縫連接。

（3）軟件模擬方面：在開發(fā)需要考慮成本和安全性方面的項目時，軟件模擬是一種有效的實現(xiàn)方法。在GOJ中評判程序是軟件模擬的一個C/S架構(gòu)程序，這樣不僅節(jié)省了評判服務(wù)器的成本，在安全方面也將風(fēng)險降至最低。

參考文獻(xiàn)

[1] 李文新，郭煒.北京大學(xué)程序在線評測系統(tǒng)及其應(yīng)用[J].吉林大學(xué)學(xué)報（信息科學(xué)版），2005（23）：170-177.

[2] 邵超，張斌，張巧榮.數(shù)據(jù)庫實用教程——SQL Server 2008[M].北京：清華大學(xué)出版社，2009.

[3] 旁婭娟，房大偉，呂雙.ASP.NET從入門到精通（第二版）[M].北京：清華大學(xué)出版社，2010.