- 团队名:景
- 成绩:粤港澳复赛A榜第2,全国第12
- 分工:
(1)KITE-HZ承担了大部分的编程工作和优化工作,也是我们的队长;
(2)Buerzhu承担了多线程的优化工作和部分算法优化工作;
(3)cxyanhk承担了部分IO优化工作和部分算法优化工作;
- 找环算法优化
(1)基础是5+2,即在开始找环之前,先构建一个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)用查表方式来代替部分判断;