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中的方法。