BOP 2016 SEMI 结束之结束

#72:可以看到,作者使表示最终排名23。无缘决赛。

感谢在此期间陪伴着我的队友 RyanChen 和 feilengcui008 。

代码仓库: https://bitbucket.org/CXuesong/juniper

其他团队的部分代码仓库在文末。

以及大概整理了一下 Rank#1 团队 Euterpe 的源代码。

小结

造成这次失败的原因主要是最后一周的优化其实并无卵用。最后一周我一直都在跑 Profiler ,但忘了在此之前一直十分在意的一个事实

网络通信是用时最长的环节。

所以我并没有发现,在通信状况良好的情况下(例如服务器上) ,其实不分页要比分页快得多。因此基本上没有必要使用 offset 属性。实际上,在此之前我一直是 1000 条记录一分页的。

如果当初自己能静下心来做个实验对比一下的话,应该也不会这么惨了 🙁

不过还是有一些收获的,比如

  • 不要自己造轮子,不然很有可能会死。
  • 在这种比赛中,注重代码的优雅和重构很可能会导致作死。
  • 使用 服务器GC 可以提高应用程序的吞吐能力。

其他团队的代码仓库

根据聊天记录,由本人手工整理。如有错误,请在评论区留言。

这次前十五貌似有很多用 Python 的。看了一些代码,突然开始有点喜欢这种粗暴而又有效的代码结构了。虽然以后不一定会用 Python ,但我觉得,在比赛中,代码表现这种细节问题还是不要太过在意的好。

Rank Team Link Powered by
1 Euterpe https://gitHub.com/Elecky/BOP2016 C#
3 Mania https://github.com/a3616001/Mania Python
4 蛋黄麻薯 https://github.com/RainVision/BOP2016-semifinal Python 2.7
10 FDU_Beginners https://github.com/chenkaiyu1997/2016BOP_semifinal Java
11 yaoyao https://github.com/dyslove123/2016_bop_semifinal Python 2.7

在晚上的恍惚之余,看看他们的代码吧。

Euterpe

使用 C#, .NET Framework 4.5 搭建。终结点使用 ASP.NET Web API。

终结点入口: FinalController.Get

求解函数入口: Solver.Solve

FinalController.Get

这是一个普通的控制器。调用 Solver.Solve ,然后把返回的 Json 字符串直接传出去。如果遇到任何问题,返回一个空的数组,这样万一两个节点之间本来就没有任何联系,那么还能得满分。机智。(好吧我够)

#43:值得注意的是,在请求处理结束后,程序强行来了一波垃圾回收。恐怕是为了防止正在进行大量运算的时候,突然 stop-the-world ,然后收垃圾去了。这里的调用等价于

根据MSDN的说明, GCCollectionMode.DefaultGCCollectionMode.Forced 是等价的,也就是

A blocking collection is performed as soon as possible. If a background collection is in progress and generation is 0 or 1, the Collect(Int32, GCCollectionMode, Boolean) method immediately triggers a blocking collection and returns when the collection is finished. If a background collection is in progress and generation is 2, the method waits until the background collection is finished, triggers a blocking generation 2 collection, and then returns. [1]

如果当前运算量比较大,产生了很多垃圾的话,#43 的调用会发生阻塞。

Solver.Solve

这只是一层壳,用于按照不同的Id对类型,将请求分别交给三个独立的类: Au_AuAu_IdId_Id 进行处理。

#28:在求解函数入口,作者调用 MAGHelper.CombinedAuthTest,在确定 Id1Id2的类型的同时,也会下载作者的所有论文。这意味着对于 AuId-AuId 的情况,程序会将两侧作者所写的所有文章全部下载下来。

#72:可以看到,作者使用 JsonConvert.SerializeObject 完成 JSON 字符串的生成。个人觉得如果使用  StringBuilder 强行生成一波 JSON ,说不定性能会更好。

MAGHelper.CombinedAuthTest

^ Tuple 狂魔(够)

可以看到,作者使用了一个静态类 Queries 来处理所有查询表达式的生成逻辑,在拼接完一个查询表达式后,直接扔给了 MAGClient.Evaluate 进行查询。顺带一提,此函数返回的是 string 而不是其它的对象模型。所以随后的工作就是用 JObject 对返回的 JSON进行解析。注意到有些作者可能写了很多文章,所以查询得到的论文量还是挺大的。

经过处理之后,此函数返回了两个节点对应的论文(包括作者、期刊等信息)或作者(包含其所写的所有论文)。对于作者,返回的 Tuple 中包含了 List<Paper> ,而在 Author 中维护了一个所有论文 Id 的集合。

MAGClient.Evaluate

#48:说实话,我觉得这样做很暴力。但没想到其实很有效。

#58,#64:而且下载是同步调用的。

#55:以及大体的意思是,如果出现异常,我就死磕,直到下载成功为止。对于 HttpClient.GetAsync ,如果域名无法解析、主机连接不上,则异步任务会扔异常;如果收到标准的 HTTP 状态码,会将其放到 Response 中。

Au_Au

整个类都异常地简单。我甚至可以直接把代码贴在下面

考虑了三种情况:

  • Au-Af-AuAu-Id-Au :直接取 Id 的交集即可。
  • Au-Id-Id-Au :因为在前面已经收集过了两侧作者的所有论文,所以直接对查找论文的引用情况即可。

Au_Id.AuToIdPath

^ 我觉得其实参数 id == paper.Id 。估计是后来加上的。

对于双向连接,作者使用辅助线程进行查找操作。(终于看到了多线程!)然后在主线程中考虑单向的连接情况。

  • AuId1 - Id3 - Id2 :直接查 Id3 的所有引用文献即可。
  • AuId1 - Id3 - Id4 - Id2 :这里稍微麻烦一点,首先展开   Id3 的所有引用文献,填入 HashSet ,然后交给 aAGHelper.IdsRefOther 进行查询判断。注意这里需要访问 Oxford API 。

在  BothDir 中,作者考虑了以下情况。注意到下面的关系都是可以反转过来的。

  • AuId1 - Id2 :这个就不多说了吧。
  • AuId1 - Id3 - CId/JId/FId/AuId4 - Id2 :真 TM 暴力,我喜欢(够)。前面已经把 Id3 对应的所有文献下载下来了。很明显,这些情况下,只要 Id3Id2 之间存在某些共同点,那么就算是一条路径了。
  • AuId1 - AfId3 - AuId4 - Id2 :这个稍微麻烦一些。

^ 其中, auth : AfId1, paper : Id2
^ 唔……C风格的返回方式。不过这样免去了合并列表的开销。以及反正多线程环境下, ConcurrentBag<T> 是很耐++的。

差不多就是这个意思。需要上网寻找所有的与 AuId1 在同一组织的论文,然后看看在这些论文中有没有出现  Id2 的的某些作者。因为前面已经收集了 AuId1 的所有文章,所以我们已经知道其所在的所有组织了。除此之外,还要限定这些论文的作者必须在  Id2  的作者列表中,于是就可以返回一波文章了。

#168:使用 Queries.Group 来将查询中的 AfId3 限定分组,以使得每一组生成的请求字符串长度都刚好达到 Oxford API 服务器允许的上限。当然,每一组请求都有作者必须包含 AuId1 的限定。

#170:我们只需要论文的 IdAuIdAfId ,这样还可以节省网络流量。

#180:使用 Parallel.ForEach 把生成的所有 URL 都扔进去向 API 服务器发送请求。

#194:还是那句话, ConcurrentBag<T> 很耐++ 😉

Au_Id.IdToAuIdPath

首先,和 AuIdToIdPath 类似,启动并行线程查找双向边,然后处理下面的单向边的情况

  • Id1 - Id3 - AuId2 :直接查就可以了。
  • Id1 - Id3 - Id4 - AuId2 :稍微麻烦一点。在这里写了个子函数。大致的策略是,先展开所有的 Id3 ,然后使用 MAGHelper.PapersByOrExprs 下载所有的 Id3 论文,再将返回的 List<Paper>RId 进行展开,最后按照是否在 AuId2 的论文列表中进行筛选。满足要求的论文ID就是我们需要的 Id4

Id_Id.IdToIdPath

这应该是最复杂的类了。整个文件大概有300多行(和 MAGHelper 差不多)。

考虑了以下情况

  • Id1 - Id2 :不用多说了吧。
  • Id - CId/FId/AuId - Id :也不用多说了吧。使用 IdId2Hop 函数。
  • Id1 - Id3 - Id2 :#44,展开 Id1 的所有引用文献,然后启动辅助线程,在 refedPapers 中下载这些文章的信息。

    注意,这里下载了所有 Id3 的论文信息,是为了在 #46 中可以在此基础上筛选 3-hop 。顺带一提,在 forward 函数中处理了以下情况

    • Id1 - Id3 - Id2 :此时论文已经下载完了,直接根据 Id3RId 进行筛选即可。
    • Id - Id - CId/FId/JId/AuId - Id :使用 IdId2Hop 函数。

#49, #52:从这里开始进行判断,如果指向  Id2 的引用文献(Citation)数量少于 5000 篇,则使用 backCombo  函数,从右向左查询;否则从左向右查询。它们用来寻找以下连接

  • Id1 - CId/FId/JId/AuId3 - Id4 - Id2
    • 从右向左:下载所有指向 Id2 的引用文献( idRefs2),然后就可以愉快地根据下下来的文献的属性来进行筛选了。
    • 从左向右

      嘛大概就是这个样子,区分了五种情况。前四种大同小异,而且都需要上网查找。例如 Id1 - CId3 - Id4 - Id2 的情况,我们已经知道了 Id1 和对应的 CId3 ,需要限定 CId3 和 RId 中包含 Id2 ,然后调用 Oxford API 检索所有满足要求的 Id4 。
      Id1 - Id3 - Id4 - Id2 的情况在下面提到。
  • Id1 - Id3 - Id4 - Id2
    • 从右向左:还记得前面的 Id1 - Id3 - Id2 吗?等那里的 Id3 论文下完,这里就可以直接拿着 Id3RId1idRefs2 对着看了。
    • 从左向右:同样地,等前面的 Id1 - Id3 - Id2 那里把所有的  Id3 论文下完,这里就可以直接拿着 Id3RId1idRefs2 对着看了。(喂喂这段代码貌似和 backCombo 中类似的逻辑重复了……)

总结

作者直接考虑了1-hop、2-hop和3-hop中所有的情况,并分别提出解决方案。其中,合并处理以下情况

  • AuId - Id - CId/JId/FId/AuId - Id
  • Id - CId/JId/FId/AuId - Id - AuId
  • Id - CId/FId/AuId - Id
  • Id - Id - CId/FId/JId/AuId - Id
  • Id - CId/FId/JId/AuId - Id - Id

网络通信。以下情况需要访问 Oxford API

  • 在所有的情况下,都会下载 AuId1 和 AuId2 的所有文章。
  • AuId1 - Id3 - Id4 - Id2  :为了得到所有的  Id4 及其详情。
  • Id1 - Id3 - Id4 - AuId2 :为了得到所有的 Id3 的详情。
  • AuId1 - AfId3 - AuId4 - Id2 (或者反向):为了得到 AuId4 的所有组织,以判断其是否和 AuId1 同组织。
  • Id1 - Id3 - Id2 :为了得到所有的 Id3 的详情。
  • Id1 - CId/FId/JId/AuId3 - Id4 - Id2 :在采取从左向右的查找方法时,需要访问四次网络,以寻找满足要求的 Id4 文章。

也就是说,在不考虑查询分组的情况下,一次  Solver.Solve 最多访问 1[CombinedAuthTest] + 5[Id – Id,从左向右] = 6 次网络,最少访问1[AuId – AuId]次网络。

我只想说,当初不该自作聪明地去用 offset 分页的。

还有一些其他的应试体会

  • 不要把函数过分地概括化。如果已经写出来的函数不能满足某些要求,大不了再写一个几乎重复的函数了事。
  • 解决问题要有全局观。这样还可以对全局方面的一些指标(例如访问网络的次数)有一个概念。妄图通过面向对象继承和多态将大问题分解为小问题地方法很可能会GG。它会使得全局优化寸步难行。
  • 想到就要去试试。到底是把一个可能会返回大量结果的请求使用 offset 分页,还是应该直接把大量的结果一口气下载下来,需要去服务器上跑一遍才知道。很可惜我没有摆脱教育网的阴霾,把一些精力放在错误处理和超时处理上了。

细节

我只是忍不住所以想说几句……求轻喷。

我看到了 MAGClient.CalcHistogram ,但此函数并未被使用。实际上,经过考虑,我认为 Oxford 提供的 CalcHistogram 在这里并无卵用,因为它不能同时查询多个作者所属的所有机构——结果会混在一起。

所有的 long 全部是 Int64 。让我有一种强迫症犯了的感觉(够)。

使用 new Tuple<T1, T2, ...>(item1, item2, ...) 而不是 Tuple.Create(item1, item2)

调用 MAGHelper.ParsePaperJToken 转换为 Paper 对象——其实可以使用 JsonConvert 的。不知道作者之前是否有考虑过。但在 Solver.cs#72 中,作者使用了 JsonConvert.SerializeObject 。估计是当时为了达到目的来不及想太多了。

发布者

CXuesong

CXuesong

给我一点点考虑的时间。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*