2020华为软挑初赛粤港澳赛区第一（全国前十），复赛粤港澳赛区A榜第一（全国第二）解决方案
团队名： 以上团队均未获奖
首先讲一些用到的trick：
建图
① 最大的trick，针对菊花点和非菊花点使用不同的建图方式
已知使用数组建图有两种方式，第一种是maxnode*max出入度的二维数组方式，第二种是在第一种基础上去掉多余空间的压缩方式。
又已知第一种访问比第二种快（第一种得到某个结点的地址只需要乘以最大度数），第二种更加节省空间。
基于此，我们可以设置阈值，让度数＜T的结点使用第一种建图方式，≥T的结点使用第二种建图方式。
然后每层循环用一个bool数组判断是不是菊花点(bool访问代价远低于第二种方式的int数组取地址)，从而动态使用两种图。
这个trick让我们复赛A榜从2.35->2.06
② 多线程mmap读入
③ 若最大结点小于1e7，使用数组做映射；否则使用unordered_map
④ 将unordered_map换成robin_map，但需要复制2000+行源码。按照官方的说法，有被查重的风险（呵呵）
找环
① 使用抢占式负载均衡方式进行多线程找环
一开始每个线程处理一片数据（大小是超参数），谁处理完了就用mutex取下一片未处理数据，以此类推，可以达到最好的并行效果。但是会相对的增加少量合并结果的时间
② 并行时让主线程也参与工作
这个小trick在我的程序上影响不大，因此没有使用。
③ 4+3 > 6+3 + 5+2 > 5+2
④ 为了提高取址速度，对菊花点和非菊花点动态切换两种存储方式
⑤ 为了提高程序效率，将dfs转为迭代
⑥ 由于path数组有序程度较高，使用插入排序来提高排序效率
相比原始的sort或者stable_sort，插排要快10倍以上
⑦ path数组映射版慢于不映射版，所以A榜时没有使用映射
据我所知有的团队映射版还更快，并且映射版好处是不容易爆内存。
⑧ 为了提高效率，尽可能压缩数据类型的字节数
Bool, uint8_t, unsigned short, int等尽量卡到能刚好满足要求的数据类型
这可以大大提高程序效率，但是同时会牺牲一些可扩展性
⑨ 适当的调整if的顺序，不同剪枝的力度和访问/计算代价各不相同
比如4+3正向遍历的最后一层要用path数组里该节点的个数是否等于0作为第一个剪枝。
因为该数组的类型可以是uint8_t或unsigned short，访问较快，剪枝效力也较强
写入
① memcpy利用对齐技巧，每次都指定长度为16，下次按照真实长度开始覆盖。
对齐是个玄学，至今仍未参透。 改变变量定义的顺序之类的也能提高一些分
② ID到字符串的映射存储由二维数组改为一维数组。
③ 将转字符串的过程与write的过程并行
众所周知write只能串行写入。因此利用标记来确认是否已经获得前面环的总字节长度，
获得了就开始当前线程的写入过程，可以一定程度上防止多个线程同时阻塞write
上分过程
1. 初始版本
6+3找环，使用反向3层深度剪枝。
线上分数 **8.0**
2. 找环调度策略
使用抢占式，每个线程从任务池中取任务（ID），跑完后再继续取。
线上分数 **4.2218**
3. 内存对齐
在定义边的数据结构时，使用
struct Edge
{
int v, w;
};比使用
struct Edge
{
int v; uint64_t w;
};更快。
线上分数 **3.4426**
5. 5+2找环
5+2找环，并使用反向3层深度剪枝。
线上分数 3.0149
4. 4+3找环
线上分数 **2.7282**
5. 排序方式
4+3找环时存储的路径需要进行排序，插入排序比归并排序更快。
线上分数 2.4946
6. 访问的连续性
ID到字符串的映射存储方式，从二维数组改为一维数组，结果转换为字符串时更快。
线上分数 **2.3592**
7. 区分菊花点
区分菊花点，使用不同的建图方式
线上分数 **2.0676**
觉得有用的话，麻烦给个star~
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent