前言

• 团队名：景
• 成绩：粤港澳复赛A榜第2，全国第12
• 分工:
  （1）KITE-HZ承担了大部分的编程工作和优化工作，也是我们的队长；
  （2）Buerzhu承担了多线程的优化工作和部分算法优化工作;
  （3）cxyanhk承担了部分IO优化工作和部分算法优化工作；

优化

• 找环算法优化
  （1）基础是4+3，即在开始找环之前，先构建一个P3来存储路径倒数三个节点的信息；
  （2）在构建P3的时候顺便用反向邻接表构建P1,P1找环比遍历子节点来寻找是否有头结点的找环方式更加高效；
  （3）对路径中的第2、3、4、5使用P3来找环，可以同时减少路径上第4、5、6、7节点通过P1找环的工作；
  （4）在反向遍历3层构建P3的过程中顺便统计有哪些点与起点的距离小于等于3，并利用这一点在正向遍历过程中剪枝，具体例子如下：

//对于第五层的点，如果该点距离起点的距离大于3，则该点无环
if(target.nodeLen[m]!=3 || G[l_it].first <= head || ccm*left<ccL || ccm>right*ccL)
      continue;

• 数据结构优化
  （1）使用数组来代替vector，减少扩容开销；
  （2）类似的，使用一维和二维数组来存储邻接表和P3等信息，即尽量减少STL容器的使用；
  （3）在节点去重工作的排序过程sort(temp,temp+sumID)中，由于temp中重复的节点过多，会大大增加排序时间，因此使用一个bool idUnique[MAX_ID]数组来存储那些已经在temp内的节点，从而避免重复存储。通过多次提交证明，大部分节点id大小在1亿以下；
  （4）类似的，对小于1亿的节点使用数组进行hash映射，也可以减少部分映射时间；
  （5）对前向邻接表排序后再构建后向邻接表，从而使得后向邻接表有序，减少部分排序工作；
  （6）为了节省空间和寻址时间，在满足功能的情况下尽量使用较小的数据结构，例如，使用uint8_t来存储每个节点对应的字符串长度；

• 多线程优化
  （1）使用抢占式负载均衡方式进行多线程找环，一次任务分块的节点数为100；
  （2）采用atomic_flag来构造自旋锁，可以避免互斥锁的系统调用的开销；
  （3）通过多次提交证明，6线程工作效果较佳；

• 其他优化
  （1）尽量使用局部变量；
  （2）使用memcpy来代替部分赋值工作；
  （3）使用循环展开；
  （4）利用计算机系统的空间局部性合理设计数据结构；
  （5）读取txt使用mmap;
  （6）写入使用fwrite;
  （7）在if判断中注意判断条件的顺序；
  （8）将dfs递归改为迭代，减少函数调用的开销；
  （9）用查表方式来代替部分判断；