CodeCraft2020

华为2020软件精英挑战赛复赛代码开源（京津东北赛区1504b，复赛Ａ榜 rank1, B榜无有效成绩）

代码清单

• main63.cpp : 6+3 版本代码，线下4.8x, 线上2.6x。（线下为1963w数据，下同）
• main43.cpp : 4+3 版本代码，线下5.5x, 线上2.3x。
• test.sh : 批量测试脚本，可用于测试路径、答案等是否正确。用法 :
  • 添加执行权限：chmod u+x test.sh
  • 测试：./test.sh main.cpp
  • (可能提示没有权限创建文件，以 sudo 权限运行即可)
  • test_data_xxxx.txt : 数据集，其中xx为环的个数
  • answer_xxxx.txt : 与数据集对应的答案
  • log.txt : 测试日志文件，可用于排查错误

基本思路

1.建图（耗时130ms）

由于vector数组速度慢、静态数组受节点出入度的限制影响很大、动态数组管理不方便且在内存中排布不够紧凑等原因，采用前向星作为图的数据结构具有很大的优势。前向星中的边在内存中紧密排布，所需空间为n * sizeof(Edge)。其中，n 为边的数量，也就是转账记录数。

其他trick：

(1)不使用unordered_map来映射;

(2)减少哈系表的访问，如标记该节点是否在哈系表中，以减少if(!Map.count(key))的消耗。

2.找环（6+3耗时4.0x,4+3耗时4.8x ）

很多同学都是6+3或4+3两个思路，我的6+3在线下的1963w数据集上表现优于4+3，但在线上却稍逊于4+3，看起来似乎6＋３更适合于线下的随机图，而4+3更适合于线上的随机图＋菊花图（＋完全图）。（也有可能是我最后两天转的4+3，还没有调教得很好）

由于大部分同学都是用的这两个思路，因此方法层面没什么好说的，这里有几个trick可能有一定的优化作用：

(1)尽量减少不必需的内存访问，如在dfs的过程中访问ID数组来获取原始id。

(2)能用uint8/bool数组绝不用u32/int数组，这可能是因为u32/int数组占用空间大，cache中存在的几率更小，从而导致更多的cache miss。

(3)dfs过程中的if-continue的判断次序很重要，对于更有可能导致continue的分支应该放在更前面。

(4)避免不必要的判断，例如if(DIS[curr] < 3)已经包含if(curr != start)，因此后者无须再判断一次。

3.转换输出（耗时580+ms）

我的转换输出并不快，主要思路是先将多线程找到的环进行合并，然后进行多线程查表转换，最后以mmap+多线程memcpy的方式写入文件。

这里采取的建表方式为：以映射后的id为下标，将映射前的id转换为字符串后存入对应的位置。例如，5439817映射后为42,则conv[42] == “5439817”。这样可以使得转换过程中无须进行反映射，从而减少的内存访问。

上述建表方式耗时<1ms，空间大小为11 * n，这里的n为有效节点数。

参赛感想

本次比赛从热身赛到复赛结束耗时2个月有余，收获不少但遗憾更多。遗憾之处在于没能拿到更好的名次，更在于不能到深圳和各位共同进步的大佬学习。