Huawei-Code-Craft2020

KO | EN

gitlite — search

#javascript #llm #machine-learning #docker #java #cli #kubernetes #awesome-list #vue #security #pytorch #ios #mcp #open-source

Huawei-Code-Craft2020

(★ 14)

No description available.

Huawei-Code-Craft2020 Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 华为2020软件精英挑战赛（Huawei-Code-Craft）
本人所在的团队为武长赛区wdyggg，个人热身赛全国27，初赛区域第3，复赛A榜第1，B榜没分，止步复赛。队友是来自华科的Mr_sixven和来自湖南大学的Hyacinth。非常感觉我的两个队友，队友都很强，大家为了这个比赛都很努力，虽然结果很遗憾,还是非常感谢两个队友。

## 版本说明
1、main5+2.cpp版本是逆向存图两层，线上2.60s。  
2、main4+3.cpp版本是逆向存图三层，这个是封榜后才改好的，未测试，估计2.1xs左右，我们线上的成绩跟1800w的那个数据集时间类似，线上2.6s的，1800w的线下2.5xs左右，优化后大概1800w的线下2.0xs（这里非常感谢西北赛区的荒野大嫖客队伍，这是在跟他们讨论后得到的启发）

## 优化思路
这次的华为软件精英挑战赛，无论是从热身赛、初赛还是复赛，主要考验的是代码的性能优化（复赛B榜除外），对于算法部分考验度较低，毕竟大部分选手的算法都是类似的。由于比赛成绩按照时间进行排名，如何优化代码性能，提高代码的运行速度就成了关键。武长赛区临近复赛结束时，竞争比较激烈，前排的分数相差不多，所以各种优化小手段就成了关键。下面分享几个我们队伍的tricks：主要是通过调整算法和数据结构对 cachemiss，访问局部性，pagefault等方面进行优化，
 
### (1) 使用动态数组而不是stl的vector
复赛相比于初赛去掉了平均入度和出度的约束，线上样本中有出度和入度很大的点，在不考虑速度的情况下，使用vector可以动态分配内存，不用担心数组的越界问题，但vector的速度比较慢，特别是二维数组用vector表示时。二维数组实际是一段连续的内存，因此其内存访问的局部性很强，cache命中率较大，而vector<<vector<int>>>本身保存的是指向数据块的指针，指针是连续存放的，指针指向的行内数据是连续存放的，但行与行之间不是连续存放的，因此跨行访问时局部性较低，Cache命中下降，除此之外使用vector访问中间多了一层的地址转换，当空间不足时，会经过重新配置，元素移动，释放空间等过程，都会占用一定的时间。  
采用动态数组即根据节点的出入度进行分配，保证数据存储不会越界，也不会覆盖，同时节省了空间，对于一个数据很大的数组，如果直接以最大出入度进行分配，不仅浪费存储空间，若实际的出入度很小，那么内存访问的局部性就不好。  
 
### (2) id映射使用自定义的映射函数，而不是 unordered_map
无序映射是存储键值和映射值之间关系的关联容器 ，虽然其查找和插入都是 O(1) 复杂度，在常数级别，若映射的id数量足够多，在时间较短的情况下，也会拖慢程序的性能。无序映射使用散列值的方式，键值通过一个特定的哈希运算映射到一个特殊的位置，而该位置指向实际的存储值，相当于有两次地址转换，因此会比较慢，我们采用的是采用牺牲空间换时间的方式，自定义哈希函数，在查找和建立上都比较快。  
 
### (3) 读取、建图多线程
 读取和建图部分，基本所有的操作都使用多线程完成（除了映射部分），包括边的排序部分，边的排序使用自己写的归并排序和快速排序方式，比sort排序快。具体的实现细节看代码。
 
### (4) 4+3加存图方式
先建立正向的两层图，将满足权值要求的两层节点连续存放，这是优化内存访问的局部性，因为每一层的节点分布是随机且不连续的，每访问一层节点需要对节点的合理性进行判断然后内存访问再进行跳转，而事先存储两层节点的方式，由于每两层节点是连续存放的，这样的内存访问局部性较好。  
小trick：存储的两个节点首先会比较第一个节点，然后比较第二个节点，连续存放的两层节点的部分第一层节点是相同的，因此这里存在一个重复比较的问题，即若第一层节点已经访问过，那么就不需要在进行访问了，因此可以将第一节点相同的长度存储下来，若该节点不符合要求，直接偏移一定的长度，到下一个未访问的第一节点。
 
### (5) 逆向搜索加标记
这部分基本很多人都是差不多的，这里有个小细节，就是节点是否在逆向搜索中出现的标记，开始 我们也是使用bool类型的方式，bool类型只占8个字节，对0,1的判断也很快，并且memset状态恢复需要操作的字节数较少。但频繁的memset也会带来一定的时间损耗，所以采用每次不需要重置数组的方式会比较快，int类型比uint8类型慢（测试得到），这里直接使用uint8_t 类型和bool类型存储长度一定（猜测是否是编译器进行并行化时，存储长度小的可以进行并行化操作大？）然后每一位代表不同的含义。不同搜索的层数都标记出来，可以进行一定的剪枝。剪枝策略大家都差不多 ，原来只存储了逆向两层的数据，线上2.6s，封榜后改为了存储三层，应该能更快，同时使用了动态修改内存的方式，稳定性较好。  
 
### (6) 找完环再进行字符转换
找环时同时进行字符转换理论上会减少一次内存的复制过程，但由于存储环路，和环路字符的buffer比较大，在找环时进行转化相当于需要从节点的图存储页面跳转到字符转码操作，然后跳转到存储字符的页面，即内存访问的局部性不好，频繁的页面跳转比较费时间。找完环再进行转码，相当于只需要取出int类型变量，然后转码成字符型，然后存储即可，属于重复性操作，会比较快（测试大概能提高0.1s~0.2s）。  
 
### (7) 找环多线程负载均衡
初赛时是采用了节点分块的方式进行线程任务划分，但由于越到后面的节点id，其环路个数越少，负载不均衡，若根据数据集进行调整，不同的数据集的负载均衡性很难保证都合理，这里使用原子变量，由于节点id映射之后是从0开始增大，直接使用一个原子变量，然后++即可，这样每个线程在完成当前节点的环路搜索后得到的起始节点索引是不同的，这样的负载均衡性好，而且没有使用互斥锁的方式，线程之间等待时间少，也不会冲突。  
 
### (8) 输出负载均衡
输出3,4,5,6,7环的字符串，思路是：计算34567环各自存储的节点总数，以及分配到四个线程的平均节点数；四线程分别完成3,4,5,6环的转码+存储，将7环分为四份分摊到各个线程中，保证每个线程处理的节点总数大致相等；转码是根据映射后的节点id从真实id字符串数组中获取，该数组按照映射后的id顺序存储；负载均衡按照节点数分配，认为节点id的位数在各个线程处理的节点中分布一致。  
 
### (9) 存储映射前的节点id字符串
这个应该大家都有做，在建图时，同时完成id的字符转换过程，虽然cpu进行计算时间比较快，但int转字符有除法操作，并且映射过程也比较耗时，所以直接在建图时就同时建立映射前的字符串和映射后的id之间的关系。  
 
### (10) 写入fwrite单线程
这里很奇怪，线下使用多线程mmap的方式有效果，线上很慢，各种多线程写的方式都尝试过，pwrite等等，都不如fwrite，本来想试下异步写入的方式，后面放弃了。

### tricks总结
总的来说，很多trick大家都是差不多的，看了其他人的trick，我们组做的稍微好点的就是自定义的映射函数，和排序函数，还有一些就是数据结构方面的操作，提高了内存访问局部性。

## 参赛感受：
本人第一次参加软件类的比赛（没有留下什么好的印象），能取得这样的成绩，对自己还算满意吧，最后未进决赛只能说十分遗憾，再次感谢我的两个队友，大家都很强。  
参加华为比赛的两个月，经历了热身赛、初赛和复赛的各种蜜汁操作，身心疲惫（复赛参加和没参加一个分数，跪了），武长赛区A榜最后几天的竞争也很激烈，为了优化0.xs，肝了几个通宵，然而没啥用。  
这次比赛最大的收获就是见识了各种优秀的同学，能跟这些大佬们同台竞技，还是很满意的，大佬们说了不少以前没学过的知识点，很感兴趣，以后遇到了，可以好好研究下，同时也深感自己有很多不足，接下来就要好好学习了。

Huawei-Code-Craft2020

Huawei-Code-Craft2020 Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Huawei-Code-Craft2020

Huawei-Code-Craft2020 Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README