华为2020软件精英挑战赛复赛代码开源(京津东北赛区1504b,复赛A榜 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+3更适合于线下的随机图,而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个月有余,收获不少但遗憾更多。遗憾之处在于没能拿到更好的名次,更在于不能到深圳和各位共同进步的大佬学习。