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

李偉光 陳希

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

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

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

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

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

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

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

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

2 需求分析

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

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

2.2 競賽部分功能需求

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

2.3 管理部分功能需求

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

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

3 設(shè)計(jì)部分

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

圖1中第2行模塊將在網(wǎng)站的菜單欄直接顯示。其中“Online Judge”模塊包括“Home”（返回主頁）和“FAQ”（進(jìn)入FAQ頁面）兩部分?！癈ontests”按鈕將鏈接至賽事列表。Contests下面的分支是由點(diǎn)擊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個(gè)子模塊，菜單欄上的Member字樣將會(huì)被用戶的用戶名所替代。如果登錄用戶具有管理員權(quán)限那么菜單欄上Member之后將會(huì)增加一個(gè)“OJ管理”按鈕，點(diǎn)擊之后進(jìn)入GOJ管理系統(tǒng)。

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

參考文獻(xiàn)

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

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

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