高云澤， 王莉莉， 董文睿， 馮紫君， 胡祖容， 趙中楠

（哈爾濱理工大學 計算機科學與技術(shù)學院， 哈爾濱 150080）

0 引 言

國際大學生程序設計競賽（ACM／ICPC）是由國際計算機協(xié)會（ACM）主辦的比賽，其宗旨是展示大學生的創(chuàng)新能力、團隊精神，以及在壓力環(huán)境下通過編寫程序進行分析和解決問題的能力。

目前，在國內(nèi)ACM 賽事的訓練過程中發(fā)現(xiàn)一些急需解決的問題。 根據(jù)1995 ～2018 年中國大陸高校入圍ACM-ICPC 全球總決賽統(tǒng)計數(shù)據(jù)可知，大部分高素質(zhì)人才集中在名校，入圍高校中只有5 所是非985／211。 其次，有些高校的投入力度不夠，很多學校ACM 活動僅由社團、協(xié)會或團委以課余活動的形式開展，在資金、師資、設備、場地等方面受到一定的限制，影響了發(fā)展規(guī)模。 還有一些學校起步比較晚，經(jīng)驗不足，只能通過去友校參觀學習、摸著石頭過河等方法去積累經(jīng)驗，需要很多拓荒者。 在此過程中，會遇到許多困難，比如訓練內(nèi)容繁多復雜，短期內(nèi)看不到成績、感覺不到自己的進步等等，慢慢會感到枯燥、迷茫，甚至放棄。 造成這些問題的另一個重要原因，是缺少一個好的學習輔助平臺，以及系統(tǒng)的學術(shù)交流平臺來提供指導和幫助。 對于參加ACM 競賽的學生來說，訓練過程中迫切地需要相應的科學指導；對于學校的ACM 組織來說，也需要一個高效的團隊管理系統(tǒng)。 因此，開發(fā)一個集能力分析、訓練指導、團隊管理和學術(shù)交流平臺于一體的智能管家系統(tǒng)尤為必要。

本文針對此問題研發(fā)了ACM 智能管家系統(tǒng)，該系統(tǒng)通過爬蟲技術(shù)獲取題目信息，通過機器學習中的分詞技術(shù)，歸納出題目的標簽，建立智慧題庫，讓用戶更方便地選擇適合自己能力的題目；通過爬蟲技術(shù)抓取用戶歷史刷題記錄，并將可視化展示給用戶，讓用戶更好地在系統(tǒng)中感受到自己的成長。 該系統(tǒng)還具有好友通信、復盤總結(jié)等功能來輔助用戶更好地提升ACM 競賽能力。

1 系統(tǒng)分析

1.1 需求分析

系統(tǒng)用戶共有兩類，分別為普通用戶和管理員用戶。 管理員爬取國內(nèi)外OJ 系統(tǒng)的題目信息，再通過關(guān)鍵詞搜索，結(jié)合分詞技術(shù)補全題目相應的算法標簽，從而構(gòu)建一個大而全的智慧題庫，使用戶可以更好地篩選題目進行專項練習；同時通過用戶綁定的信息，可以獲取用戶在各大做題平臺上的做題記錄，然后再對所有做題記錄進行聚合分析，并最終整合為圖表展現(xiàn)給用戶，從而使用戶的成長記錄可視化。

用戶可發(fā)布團隊或者個人定時訓練賽，訓練賽題目可由用戶選擇，或者規(guī)定范圍由系統(tǒng)進行推送。 在用戶訓練過程中，系統(tǒng)會記錄用戶提交的記錄以及瀏覽記錄，并將這些信息轉(zhuǎn)化為圖表展現(xiàn)給用戶，方便用戶進行復盤總結(jié)。

日志主要用于滿足用戶即想即記的需求，并且采用多級分類結(jié)構(gòu)，可以讓日志的管理更為便捷。在通信方面，通過WebSocket 建立長連接，滿足用戶間實時通信的需要。

系統(tǒng)用例如圖1 所示。

圖1 系統(tǒng)用例圖Fig. 1 Use case diagram of system

1.2 系統(tǒng)框架

該平臺基于B／S 的開發(fā)模式，利用前后端分離技術(shù)，實現(xiàn)系統(tǒng)的高內(nèi)聚低耦合，減少后端服務器的并發(fā)／負載壓力。 前端使用Electron 和Vue 框架搭建，基于組件化思想來提高各個組件復用，降低耦合度。 后端使用Django 框架搭建，利用各種數(shù)據(jù)庫訪問插件，大大提高了數(shù)據(jù)庫訪問的效率。 用戶操作用戶界面向后端發(fā)送對應事件，后端收到事件，通過方法查詢對應數(shù)據(jù)并整理后送給前端，前端收到結(jié)果集后，將數(shù)據(jù)整理并渲染展示給用戶。 系統(tǒng)結(jié)構(gòu)如圖2 所示。

圖2 系統(tǒng)結(jié)構(gòu)圖Fig. 2 Structure of system

1.3 系統(tǒng)基本策略

該系統(tǒng)研究的主要問題如下：

（1）如何在抓取題解后使用合適的文本分詞來劃分題目標簽，并提高題目標簽的準確性；

（2）系統(tǒng)需要隨時執(zhí)行抓取題目，獲取用戶做題信息，處理題目標簽等任務，系統(tǒng)如何在保證高效的情況下執(zhí)行這一系列操作，無論是用戶信息或者題庫信息都會存在變動，系統(tǒng)如何實時并同步更新這些信息；

（3）如何保證用戶間實時通信和消息推送。

根據(jù)以上分析，本系統(tǒng)的基本策略如下：

（1）對目前的算法標簽種類進行整理，獲取一個全集計數(shù)表。 對于一份題解進行分詞處理后，提取所有題目標簽，在全集表中對相應的題目標簽進行計數(shù)。 在查詢獲取一定題目的標簽后，統(tǒng)計全集表中計數(shù)最大的題目標簽，并以此標簽作為該題目的標簽；

（2）利用Redis 作為消息隊列來處理耗時的異步操作。 主服務器向Redis 中的對應任務隊列分發(fā)任務；后臺服務器通過隊列的優(yōu)先級別，由高到低不斷獲取隊列中的任務并在主服務器中運行。 同時主服務器可以向Redis 中下發(fā)定時任務，后臺服務器按照消息隊列的任務優(yōu)先級來調(diào)度處理。 在處理完單個任務之后，按需將結(jié)果返回給主服務器。 任務處理機制如圖3 所示；

圖3 任務處理機制Fig. 3 Task processing mechanism diagram

（3） 對比常用實時通信方法， 本文選擇WebSocket 協(xié)議。 用戶成功登錄后，與后端服務器建立雙向通信通道。 當用戶間進行實時通信時（如聊天、發(fā)信息等），系統(tǒng)會將消息即時推送給同時在線的用戶，或者將消息緩存到數(shù)據(jù)庫中，直到對方下次登錄時再進行推送；此外服務器也可以在特定時機，主動將消息推送給用戶。

1.4 系統(tǒng)數(shù)據(jù)組成

本系統(tǒng)數(shù)據(jù)主要由3 個部分組成：

（1）用戶在系統(tǒng)內(nèi)的行為數(shù)據(jù)。 其中包括用戶的基礎信息、團隊信息、訓練記錄以及相關(guān)日志信息；

（2）用戶在其他訓練平臺的歷史做題記錄，主要用于將用戶的成長過程進行可視化展現(xiàn)；

（3）系統(tǒng)題庫數(shù)據(jù)是系統(tǒng)的核心數(shù)據(jù)，這部分數(shù)據(jù)主要通過爬蟲的方式，去獲取主流做題訓練平臺的題庫信息，再通過關(guān)鍵詞搜索加分詞技術(shù)補全題目相應的算法標簽。

2 系統(tǒng)主要模塊設計

2.1 智慧題庫模塊

智慧題庫模塊由爬蟲獲取的信息實現(xiàn)，爬蟲能力占據(jù)該模塊的主體。 模塊中所需要爬取的信息可分為兩類：一類為題目信息，另一類為用戶做題記錄信息。 系統(tǒng)將這兩類信息的爬取任務交給后臺主線程執(zhí)行，主線程將任務分發(fā)到不同的任務棧中，對任務棧初始化后，由子進程來執(zhí)行任務棧中的任務。在子進程處理任務期間，若遇到異常則及時拋出，當所有任務棧中的任務執(zhí)行完畢后，后臺主線程結(jié)束。爬蟲框架如圖4 所示。

圖4 爬蟲框架Fig. 4 Spider framework

2.1.1 系統(tǒng)題庫搭建

本系統(tǒng)主要獲取國內(nèi)外最主要的三大實體OJ題庫信息，分別為CodeForces、HDU，以及POJ。 題庫中，除Codeforces 可以直接通過爬蟲抓取題目標簽以外，其余題庫題目均為從題目標簽層面來對題目進行劃分。 因此，系統(tǒng)題庫的實現(xiàn)首先必須滿足以下條件：

（1）獲取題庫原始數(shù)據(jù)；

（2）對于原始題庫中缺乏的數(shù)據(jù)進行補全。

為了搭建系統(tǒng)題庫，首先通過爬蟲來獲取各個題庫的題目信息，存入題庫后再由后臺分發(fā)對應的任務存入到Redis 服務器中。 當后臺服務器處理到任務時，通過爬蟲抓取對應題庫的題目信息。 對于已有標簽的題目則直接存入系統(tǒng)題庫，對于沒有標簽的題目再進行第二次爬蟲。 第二次爬蟲基于題目信息來爬取題目的題解，在html 頁面獲取題解內(nèi)容后，通過文本分詞劃分高頻標簽，并進行計數(shù)統(tǒng)計，以計數(shù)最高的標簽作為該題目的標簽并存入題庫。 題目處理流程如圖5 所示。

圖5 題目處理流程Fig. 5 Flow chart of problem handling

2.1.2 用戶成長記錄模塊

支持用戶成長記錄模塊的數(shù)據(jù)，主要來自題庫內(nèi)獲取到的用戶做題信息及題目信息。 當用戶使用該系統(tǒng)時，可以選擇希望綁定的OJ。 系統(tǒng)在綁定OJ后，會對該用戶的做題記錄進行爬取，將爬取的題目映射到系統(tǒng)題庫內(nèi)的題目，并對這些題目進行時間、題庫以及題目標簽上的劃分，使用ECharts 來處理這些數(shù)據(jù)并整合為圖表展示給用戶，讓用戶對自己做題的數(shù)量、類型和周期有一個直觀的了解。

（1）用戶信息抓取：當用戶登錄管家系統(tǒng)后，系統(tǒng)會向用戶申請綁定OJ 賬號，當賬號綁定成功后，系統(tǒng)將利用爬蟲模擬用戶登錄并獲取用戶提交過的題目id。 這個過程具有一定的時間間隔，該任務會被放到定時任務中，在特定的時刻對任務進行爬取并執(zhí)行。 在完成模擬登錄以及獲取題目id 后，系統(tǒng)將此部分的題目id 與系統(tǒng)題庫內(nèi)的id 進行映射對比，獲取此部分的題目信息集合，將該部分內(nèi)容的時間、題目來源和題目標簽等信息進行抽離，并形成圖表所必須的信息集合；

（2）用戶數(shù)據(jù)可視化：用戶可視化需要使用到用戶信息集合，將用戶信息集合按照做題時間、題目來源、題目標簽進行劃分后，在ECharts 的模型層，將對應的JSON 數(shù)據(jù)注入到對應的圖表信息中，并在視圖層對圖表樣式進行配置。 之后，在控制層對事件展示進行控制，最后將用戶的做題信息以圖表的形式展現(xiàn)給用戶。

2.1.3 用戶個性化題庫模塊

用戶個性化題庫模塊負責將后端采集到的題目信息展現(xiàn)給用戶。 其中包括用戶是否通過、題目名稱、算法標簽以及該題目的通過數(shù)，并提供篩選功能。 用戶可以通過輸入題目進行模糊匹配，選擇特定平臺的題庫或者根據(jù)特定的算法標簽進行篩選。

鑒于題庫中題量較大，且需要滿足用戶的精準查詢，系統(tǒng)將需精準搜索的平臺題庫和標簽做了一層緩存，將用戶每次的查詢都放入緩存里，從而提升用戶使用的流暢度。

2.2 訓練與復盤模塊

訓練賽模塊支持個人訓練以及團隊訓練，用戶可在本地完成代碼，通過管家系統(tǒng)的接口進行提交。通過訓練模塊中的任意題目，用戶均可打開提交界面，該界面會接受用戶傳輸?shù)脑创a并將代碼打包發(fā)送到對應OJ 平臺進行提交。

用戶在選題時，可以手動輸入題庫平臺和題目ID 來添加題目，也可以選擇一些過濾條件，通過隨機方式自動添加一些所有參與者均沒有通過的題目。

用戶在結(jié)束訓練賽后，可以進入當前比賽的“復盤模塊”。 當用戶第一次進入這個模塊時，系統(tǒng)自動給用戶生成一個復盤文檔的模板，用戶可以回顧整個比賽的過程，并寫下自己的收獲。

2.3 日志模塊

在日志模塊中，用戶可創(chuàng)建多級日志用于賽后復盤總結(jié)，每頁日志最多可存儲2 Mb 的數(shù)據(jù)。 當用戶完成日志的構(gòu)建后，后臺會校驗日志數(shù)據(jù)合格性，通過校驗后存入數(shù)據(jù)庫，同時將用戶日志的緩存更新，保持數(shù)據(jù)一致性。 日志編輯框支持markdown 語法，用戶可在日志中添加文字、圖片、鏈接等一系列內(nèi)容來完成賽后總結(jié)或刷題記錄，并將日志以二進制文件的方式存入數(shù)據(jù)庫中。 在用戶進入系統(tǒng)時由子進程查詢?nèi)罩灸夸浗Y(jié)構(gòu)，并將這些內(nèi)容放入緩存中。 當用戶點擊對應日志時，系統(tǒng)進行解析，交給前端渲染，同時在緩存中添加此內(nèi)容。

（1）數(shù)據(jù)結(jié)構(gòu)：日志模塊中創(chuàng)建多層級的日志，創(chuàng)建的日志目錄會直觀的展示給用戶，但是為了保持數(shù)據(jù)的穩(wěn)定性以及查詢效率，整體目錄最多向下延伸3 個層級。 對于任意日志均存在兩種指針：一種指向其父節(jié)點，用于子日志后回溯父日志；另一種指向子日志，用于快速展示目錄。 用戶目錄會在第一次加載后進行緩存，之后用戶刷新界面都使用緩存中獲取的目錄，直到更新目錄后臺時再次獲取新的日志目錄，并更新用戶界面，同時將新的用戶目錄傳入緩存；

（2）日志內(nèi)容：用戶可使用markdown 語法來完成日志的添加。 文字和鏈接將以html 文件的形式存入數(shù)據(jù)庫，圖片也保存至數(shù)據(jù)庫。 每次加載日志時，會從數(shù)據(jù)庫匯總獲取并解析，解析后的內(nèi)容會存入緩存，下次進入頁面時不再重新加載和渲染。 當用戶修改日志內(nèi)容后，系統(tǒng)直接將用戶修改后的html文件存入數(shù)據(jù)庫，同時將緩存中的內(nèi)容同步修改。

2.4 通信模塊

當用戶進行通信時，系統(tǒng)會在用戶之間建立一個長鏈接，用來保證信息可以實時進行傳輸。 使用長鏈接還可以在每次傳輸中復用TCP 鏈接，節(jié)約了信息傳輸時間。

通信協(xié)議遵守三層數(shù)據(jù)的規(guī)范，保證整體協(xié)議的規(guī)范化。 第一層包含具體對象、具體場景編號以及第二層數(shù)據(jù)；第二層包含好友編號和第三層數(shù)據(jù)；第三層包含具體要傳輸?shù)臄?shù)據(jù)。

當用戶編輯完消息后點擊發(fā)送鍵，后臺會將用戶編輯的信息進行序列化，并通過長鏈接將序列化后的數(shù)據(jù)傳輸給對應的好友。 對于收到的好友消息，后臺將遵守三層數(shù)據(jù)規(guī)范對數(shù)據(jù)進行解析，前端將反序列化的數(shù)據(jù)展示給用戶，至此完成了用戶之間的數(shù)據(jù)傳輸。 由于保持著長鏈接的存在，用戶進行數(shù)據(jù)傳輸?shù)倪^程中減少了鏈接的反復建立，可以很大程度上提高用戶間通信的實時性。

3 系統(tǒng)測試

3.1 用戶登錄主頁

用戶登錄后的個人頁面展示了用戶在各個OJ平臺中的做題信息，可以直觀的查看自己在特定時間內(nèi)做題的數(shù)量、標簽分類以及平臺分布。 圖6 是用戶在2021 年10 月份的做題情況。

其中，雷達圖用來展示不同標簽的做題量；餅狀圖用來展示不同題庫的做題量；柱狀圖用來展示當月每日的做題量。

3.2 題庫運行情況

訓練賽定制頁面如圖7 所示。 用戶可選擇團隊或個人的訓練方式，并且可以添加訓練賽題目：

圖6 用戶界面Fig. 6 User interface

圖7 題庫運行圖Fig. 7 Question bank

3.3 訓練賽定制和賽后復盤

訓練賽定制頁面如圖8 所示。 用戶可選擇團隊或個人的訓練方式，并且可以添加訓練賽題目。 隨機生成題目的過程如下。

（1）當用戶點擊“隨機”的時候，會檢驗當前所有的比賽參與者，個人訓練為1 人，團隊訓練為3人，并向服務端傳遞所有的參與者信息；同時服務端會通過異步的方式，篩選出所有參與者未通過的題目集合寫入緩存中；

（2）當用戶對過濾條件進行選擇并點擊“確定”時，會向服務端傳遞過濾條件，服務端根據(jù)過濾條件分別從緩存中提取滿足條件的題目集合，將這些題目集合的交集返回給用戶。

圖8 創(chuàng)建訓練Fig. 8 Create training match

用戶可以自定義個人／團隊的訓練賽，訓練賽后可以復盤比賽。 復盤模塊的目的是，引導用戶逐步建立起及時復盤的習慣。 復盤頁面如圖9 所示。

圖9 復盤界面Fig. 9 Match reply

3.4 用戶日志頁面運行圖

用戶可主動創(chuàng)建以及打開并編輯日志，所有日志都保存在用戶本地磁盤中。 日志運行界面如圖10 所示。

圖10 日志頁面Fig. 10 Log page

4 結(jié)束語

本系統(tǒng)實現(xiàn)了題目分析、訓練賽添加、信息可視化展示、好友實時通信、日志添加等功能，為用戶提供了一個全渠道的ACM 技能提升系統(tǒng)，目的在于提升用戶ACM 競賽水平。 本文對其功能實現(xiàn)和相關(guān)技巧進行了詳細闡述。 系統(tǒng)功能多樣、實用，交互性強，經(jīng)過各個模塊的測試，系統(tǒng)穩(wěn)定性也符合預期，是一款符合用戶需求的軟件。