#72：可以看到，作者使表示最终排名23。无缘决赛。
感谢在此期间陪伴着我的队友 RyanChen 和 feilengcui008 。
代码仓库： https://bitbucket.org/CXuesong/juniper
其他团队的部分代码仓库在文末。
以及大概整理了一下 Rank#1 团队 Euterpe 的源代码。
TOC
小结
造成这次失败的原因主要是最后一周的优化其实并无卵用。最后一周我一直都在跑 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
// GET api/<controller>/5
public HttpResponseMessage Get(string id1, string id2)
{
BOP.Solver solver = new BOP.Solver();
try
{
string result = solver.Solve(Int64.Parse(id1), Int64.Parse(id2));
return new HttpResponseMessage()
{
Content = new StringContent(result, System.Text.Encoding.UTF8, "application/json")
};
}
catch (Exception ex)
{
return new HttpResponseMessage()
{ Content = new StringContent("[]", System.Text.Encoding.UTF8, "application/json") };
}
finally
{
GC.Collect(2);
}
}
这是一个普通的控制器。调用 Solver.Solve ，然后把返回的 Json 字符串直接传出去。如果遇到任何问题，返回一个空的数组，这样万一两个节点之间本来就没有任何联系，那么还能得满分。机智。（好吧我够）
#43：值得注意的是，在请求处理结束后，程序强行来了一波垃圾回收。恐怕是为了防止正在进行大量运算的时候，突然 stop-the-world ，然后收垃圾去了。这里的调用等价于
GC.Collect(generation, GCCollectionMode.Default, true);
根据MSDN的说明，GCCollectionMode.Default 和 GCCollectionMode.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_Au、Au_Id、Id_Id 进行处理。
#28：在求解函数入口，作者调用 MAGHelper.CombinedAuthTest，在确定Id1、Id2的类型的同时，也会下载作者的所有论文。这意味着对于AuId-AuId 的情况，程序会将两侧作者所写的所有文章全部下载下来。
#72：可以看到，作者使用 JsonConvert.SerializeObject 完成 JSON 字符串的生成。个人觉得如果使用 StringBuilder 强行生成一波 JSON ，说不定性能会更好。
MAGHelper.CombinedAuthTest
/// <summary>
/// 测试auId是否确实是AuId，同时顺手查询其作者信息以及所写文章信息
/// </summary>
/// <param name="auId">要查询的Id</param>
/// <returns>三元素的Tuple
/// 1: 是否是AuId
/// 2: 作者信息, 为 null 当auId不是AuId
/// 3: 作者所写的文章, 为 null 当auId不是AuId</returns>
internal Tuple<Tuple<bool, Author, List<Paper>>, Tuple<bool, Author, List<Paper>>>
CombinedAuthTest(Int64 auId1, Int64 auId2)
^ Tuple 狂魔（够）
可以看到，作者使用了一个静态类 Queries 来处理所有查询表达式的生成逻辑，在拼接完一个查询表达式后，直接扔给了MAGClient.Evaluate 进行查询。顺带一提，此函数返回的是 string 而不是其它的对象模型。所以随后的工作就是用 JObject 对返回的 JSON进行解析。注意到有些作者可能写了很多文章，所以查询得到的论文量还是挺大的。
经过处理之后，此函数返回了两个节点对应的论文（包括作者、期刊等信息）或作者（包含其所写的所有论文）。对于作者，返回的 Tuple 中包含了 List<Paper> ，而在 Author 中维护了一个所有论文 Id 的集合。
MAGClient.Evaluate
static internal string Evaluate(string expr)
{
string uriStr = Domain + "evaluate?expr=" + expr + "&count=1000000" + Key;
bool isSuccess;
string retVal = string.Empty;
do
{
try
{
//var start = Environment.TickCount;
var response = client.GetAsync(uriStr).Result;
isSuccess = true;
//var finish = Environment.TickCount;
//Console.WriteLine("http responds in {0} ms", finish - start);
if (response.IsSuccessStatusCode)
{
retVal = response.Content.ReadAsStringAsync().Result;
}
else
{
retVal = "{\"entities\":[]}";
}
}
catch (Exception)
{
isSuccess = false;
}
} while (!isSuccess);
return retVal;
}
#48：说实话，我觉得这样做很暴力。但没想到其实很有效。
#58,#64：而且下载是同步调用的。
#55：以及大体的意思是，如果出现异常，我就死磕，直到下载成功为止。对于 HttpClient.GetAsync ，如果域名无法解析、主机连接不上，则异步任务会扔异常；如果收到标准的 HTTP 状态码，会将其放到 Response 中。
Au_Au
整个类都异常地简单。我甚至可以直接把代码贴在下面
internal class Au_Au
{
internal Au_Au(MAGHelper _helper)
{
helper = _helper;
}
internal ConcurrentBag<Int64[]> AuToAuPaths(Author auth1, Author auth2, IEnumerable<Paper> paperByAu1)
{
ConcurrentBag<Int64[]> paths = new ConcurrentBag<long[]>();
// no 1-hop path
// 2-hop path
// AuId->AfId->AuId
// 这里暂且用auth1的Affiliations进行循环。实际上，用集合大小更小的进行循环大概更快一些
foreach (Int64 afId in auth1.Affiliations)
{
if (auth2.Affiliations.Contains(afId))
{
paths.Add(new Int64[] { auth1.AuId, afId, auth2.AuId });
}
}
// AuId->Id->AuId
foreach (Int64 id in auth1.Papers)
{
if (auth2.Papers.Contains(id))
{
paths.Add(new Int64[] { auth1.AuId, id, auth2.AuId });
}
}
AuId_Id_Id_AuId(auth1, auth2, paths, paperByAu1);
return paths;
}
/// <summary>
/// find and add all 3-hop paths of type AuId->Id->Id->AuId into paths.
/// </summary>
/// <param name="auId1"></param>
/// <param name="auId2"></param>
/// <param name="paths">container to which to write paths</param>
/// <param name="papers1">information of papers by author 2</param>
private void AuId_Id_Id_AuId(Author auth1, Author auth2, ConcurrentBag<Int64[]> paths,
IEnumerable<Paper> papers1)
{
// 目前使用的方法：
// 判断ID是否为AuId时顺手查询了他所写的文章信息，直接利用
foreach (Paper paper in papers1)
{
// 检查paper的引用
foreach (Int64 rId in paper.RIds)
{
if (auth2.Papers.Contains(rId)) // 如果这篇文章是auth2写的
{
paths.Add(new Int64[] { auth1.AuId, paper.Id, rId, auth2.AuId });
}
}
}
}
MAGHelper helper;
}
考虑了三种情况：
Au-Af-Au、Au-Id-Au：直接取 Id 的交集即可。Au-Id-Id-Au：因为在前面已经收集过了两侧作者的所有论文，所以直接对查找论文的引用情况即可。
Au_Id.AuToIdPath
// [AuId, Id]
internal ConcurrentBag<Int64[]> AuToIdPath(Author auth, IEnumerable<Paper> paperByAu1, Int64 id, Paper paper)
{
ConcurrentBag<Int64[]> paths = new ConcurrentBag<long[]>();
// undirected paths
// 查询id文章信息
//Paper paper = helper.PaperById(id);
// 启动新线程计算双向路径
Task undir = Task.Run(()=> BothDir(auth, paperByAu1, id, paths, paper));
^ 我觉得其实参数 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对应的所有文献下载下来了。很明显，这些情况下，只要Id3和Id2之间存在某些共同点，那么就算是一条路径了。AuId1 - AfId3 - AuId4 - Id2：这个稍微麻烦一些。// [AuId, AfId, AuId, Id] // 查id文章的作者里边，曾在auId的机构发过文章的那些 private void auId_AfId_AuId_Id(Author auth, Paper paper, ConcurrentBag<Int64[]> paths)
^ 其中， auth : AfId1， paper : Id2
^ 唔……C风格的返回方式。不过这样免去了合并列表的开销。以及反正多线程环境下， ConcurrentBag<T> 是很耐++的。
差不多就是这个意思。需要上网寻找所有的与 AuId1 在同一组织的论文，然后看看在这些论文中有没有出现 Id2 的的某些作者。因为前面已经收集了 AuId1 的所有文章，所以我们已经知道其所在的所有组织了。除此之外，还要限定这些论文的作者必须在 Id2 的作者列表中，于是就可以返回一波文章了。
// [AuId, AfId, AuId, Id]
// 查id文章的作者里边，曾在auId的机构发过文章的那些
private void auId_AfId_AuId_Id(Author auth, Paper paper, ConcurrentBag<Int64[]> paths)
{
if (auth.Affiliations.Count == 0 || paper.AuIds.Count == 0)
return;
List<string> cons = new List<string>();
foreach (Int64 aid in paper.AuIds)
{
foreach (Int64 afid in auth.Affiliations)
{
cons.Add(Queries.PaperByAuAtCond(aid, afid));
}
}
string cond = Queries.Or(cons);
List<string> urls = new List<string>();
if (cond.Length > MAGClient.MaxExprLen)
{
List<string> auConds = new List<string>();
foreach (Int64 auId in paper.AuIds)
{
auConds.Add(Queries.PaperByAuIdCond(auId));
}
foreach (var cGp in Queries.Group(auConds, MAGClient.MaxExprLen, 5))
{
urls.Add(Queries.LinkAttrib(Queries.Or(cGp), false, false, false, false, true, true, false));
}
}
else
{
urls.Add(Queries.LinkAttrib(cond, false, false, false, false, true, true, false));
}
HashSet<Tuple<Int64, Int64>> pairs = new HashSet<Tuple<long, long>>();
// 已经并行化
Parallel.ForEach(urls, (url) =>
{
string responce = MAGClient.Evaluate(url);
foreach (JToken pT in JObject.Parse(responce)["entities"].Children())
{
if (pT["AA"] != null)
{
foreach (JToken AA in pT["AA"].Children())
{
if (AA["AuId"] != null && AA["AfId"] != null)
{
if (paper.AuIds.Contains((Int64)AA["AuId"]) &&
auth.Affiliations.Contains((Int64)AA["AfId"]))
{
pairs.Add(new Tuple<long, long>((Int64)AA["AfId"], (Int64)AA["AuId"]));
}
}
}
}
}
});
// now add all paths
foreach (var pair in pairs)
{
paths.Add(new Int64[] { auth.AuId, pair.Item1, pair.Item2, paper.Id });
}
}
#168：使用 Queries.Group 来将查询中的 AfId3 限定分组，以使得每一组生成的请求字符串长度都刚好达到 Oxford API 服务器允许的上限。当然，每一组请求都有作者必须包含 AuId1 的限定。
#170：我们只需要论文的 Id 、 AuId 、 AfId ，这样还可以节省网络流量。
#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中下载这些文章的信息。Task<IList<Paper>> rPsTask = Task.Run(() => refedPapers(paper1)); // 新线程查询id1引用的文章的信息 // [Id,Id,Id] and [Id,Id,any except Id,Id] Task forTask = rPsTask.ContinueWith((rpstask) => forward(paper1, paper2, rpstask, paths));注意，这里下载了所有
Id3的论文信息，是为了在 #46 中可以在此基础上筛选 3-hop 。顺带一提，在forward函数中处理了以下情况Id1 - Id3 - Id2：此时论文已经下载完了，直接根据Id3的RId进行筛选即可。Id - Id - CId/FId/JId/AuId - Id：使用IdId2Hop函数。
// 3-hop
if (paper2.CC != 0)
{
int th1 = 5000;
if (paper2.CC < th1)
#49, #52：从这里开始进行判断，如果指向 Id2 的引用文献（Citation）数量少于 5000 篇，则使用 backCombo 函数，从右向左查询；否则从左向右查询。它们用来寻找以下连接
Id1 - CId/FId/JId/AuId3 - Id4 - Id2- 从右向左：下载所有指向
Id2的引用文献（idRefs2），然后就可以愉快地根据下下来的文献的属性来进行筛选了。 - 从左向右
// 新线程计算四种情况 Task cTask = Task.Run(() => idCIdIdId(paper1.Id, paper1.CId.CId, paper2.Id, paths)); Task jTask = Task.Run(() => idJIdIdId(paper1.Id, paper1.JId.JId, paper2.Id, paths)); Task fTask = Task.Run(() => idfIdIdId(paper1, paper2.Id, paths)); Task auTask = Task.Run(() => idAuIdIdId(paper1, paper2.Id, paths)); // 当前线程计算[Id,Id,Id,Id] //[Id,Id,Id,Id] HashSet<Int64> rrIds = new HashSet<long>();嘛大概就是这个样子，区分了五种情况。前四种大同小异，而且都需要上网查找。例如
Id1 - CId3 - Id4 - Id2的情况，我们已经知道了Id1和对应的CId3，需要限定CId3和RId中包含Id2，然后调用 Oxford API 检索所有满足要求的Id4。
Id1 - Id3 - Id4 - Id2的情况在下面提到。
- 从右向左：下载所有指向
Id1 - Id3 - Id4 - Id2：- 从右向左：还记得前面的
Id1 - Id3 - Id2吗？等那里的Id3论文下完，这里就可以直接拿着Id3的RId1和idRefs2对着看了。 - 从左向右：同样地，等前面的
Id1 - Id3 - Id2那里把所有的Id3论文下完，这里就可以直接拿着Id3的RId1和idRefs2对着看了。（喂喂这段代码貌似和backCombo中类似的逻辑重复了……）
- 从右向左：还记得前面的
总结
作者直接考虑了1-hop、2-hop和3-hop中所有的情况，并分别提出解决方案。其中，合并处理以下情况
AuId - Id - CId/JId/FId/AuId - IdId - CId/JId/FId/AuId - Id - AuIdId - CId/FId/AuId - IdId - Id - CId/FId/JId/AuId - IdId - 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.ParsePaper 将 JToken 转换为 Paper 对象——其实可以使用 JsonConvert 的。不知道作者之前是否有考虑过。但在 Solver.cs#72 中，作者使用了 JsonConvert.SerializeObject 。估计是当时为了达到目的来不及想太多了。