2016“編程之美“挑戰賽復賽整理

2019-11-06 06:07:09

字體：大中小

來源：轉載

供稿：網友

比賽概述初賽的網絡平臺為 Code Hunt平臺，初賽時間為4月23日至4月24日，每天進行一場，時間為14:00-16:00。每場晉級1500人，共決出3000人晉級復賽。復賽采用團隊賽的形式，基于云計算平臺在實際大數據的基礎上展開人工智能等前沿課題的較量。時間安排這里寫圖片描述

賽題介紹Microsoft Academic Graph (MAG) 是一個巨大的異構圖譜，圖譜中包含多種實體：作者、論文、期刊、會議以及他們之間關系。微軟為此次比賽提供了 Academic Knowledge API . 具體的實體屬性定義如下這里寫圖片描述

賽題的核心問題在于，尋找從給定的起點到給定的終點的路徑。其中起點和終點可以是實體Id或者作者AuId，路徑中的節點間指向關系如下圖所示，路徑的長度為小于或等于3。

這里寫圖片描述

對于每個測試用例，REST服務將接收到一個HTTP請求，請求數據中包含一個JSON數組，數組中有一對實體標識符，其中標識符是64位整型數字，如[123,456]。REST服務的最長響應時間為300秒。

響應中的JSON數組中應該包含一個路徑列表[path1, path2, …, pathn] 其中pathi都是實體標識符。例如，如果你的程序找到了1個1跳路徑，兩個兩跳路徑和一個三跳路徑，結果就類似于[[123,456], [123,2,456], [123,3,456], [123,4,5,456]]，這個結果里邊的數字都是實體標識符。初始方案初始階段，我們試圖從起點開始，根據節點關系從前向后拓展，直至找到終結點或跳數超過限制。這是一種“大一統”的算法，如果存在可行方案，當跳數限制修改時，此算法仍舊實用。為此我們繪制了如下狀態轉移圖這里寫圖片描述

這里寫圖片描述

經過初步設計，我們根據這個示意圖編寫出了第一版的代碼，然而跑出來的結果卻讓人很不滿意，有些測試用例根本沒有計算出結果或者計算超時。于是，我們開始討論原因以及解決方案。主要原因：當我們以id或auid為查詢條件查詢時，獲得的數據量并不大，但當我們以FId(研究領域Id)、JId(期刊Id)、Cid(會議Id)為查詢條件時，獲取的數據量卻是巨大的。大到我們根本無法處理。所以才會出現無法繼續探路的情況。

解決方案：從兩端出發，而不是單純的從一端出發，即從start和end同時向中間匯聚。不去進行FId、JId、FId的查詢。

改進版本根據從兩端出發的指導思想，以減少請求次數為設計目標，分別為Id-Id/Id-AuId/AuId-Id/AuId-AuId四種情況進行了如下設計這里寫圖片描述

經過這次設計，整個思路就非常清晰了，自然程序也就水到渠成。項目架構?RESTFul架構：選擇SPRingMVC框架作為RESTFul架構實現方式。 ?JSON解析：FastJSON ?Http請求：Apache HttpClient ?Web服務器：Tomcat ?項目構建：Maven項目優化多線程優化：采用CachedThreadPool線程池對程序優化，實驗發現，CachedThreadPool要優于FixedThreadPool。Http請求優化：這部分有所欠缺，由于疏忽，這部分并未進行優化，可以建立TCP長連接，以減少連接創建消耗。相關類的解讀

AA.java：Auid/Afid的包裝類

C.java：Cid的包裝類

F.java：Fid的屬性包裝類

J.java：Jid的屬性包裝類

Entity.java：實體的包裝類，包含ID/AA/C/F/J等屬性

PathNode.java：路徑類，包含currentId/nextNode/stepNums等屬性

RequestChainNode.java：包裝類，包含currentId/requestType/parent/nextNodes/stepNum屬性

EvaluateResult.java：包裝類，包含(RequestChainNode)from/(String)expr/entities屬性

HttpClientUtil.java：定義http請求相關方法，根據id類型及參數查詢，得到返回結果

RequestMode.java：針對上述http請求方法，標識調用哪一個

RequestType.java：定義請求的id類型

SearchCallable.java：搜索回調類，根據RequestType和RequestMode選擇調用的HttpClientUtil中的方法。