【大赛优秀作品技术分享 Vol.6】2025华为软件精英挑战赛——题目解析

前言

非常荣幸拿到了2025华为软件精英挑战赛全球总决赛的冠军，本文将会从初赛题目到决赛题目逐步解析用到的算法，算法代码可以在Github上找到（核心算法1800行，总代码量2400行）：https://github.com/sunkafei/huawei-software-challenge2025

初赛赛题解析

核心思路

将每个磁盘划分成NUM_BLOCKS个块，每个块内尽量存储相同标签的对象。顺序扫描整个磁盘，只有每次进入到新的块的时候才可以进行jump操作。每个对象都必须连续存储，并且在任意时刻只能有一个磁盘在处理这个对象。不存在垃圾空间这个概念，对象的3个副本都是可以被处理的。为了便于理解，本文中的变量名将尽可能与代码一致！

全局预处理阶段

在全局预处理阶段，对于每个标签会读入长度为1800的时间片内的插入、删除、读取的对象长度。我们可以根据这个信息做一些简单的预分配，从而使得后续的相同标签的对象存储尽可能连续以及磁盘之间的负载尽可能均衡。首先我们将磁盘分成NUM_BLOCKS个块（块的大小为block_size = V / NUM_BLOCKS），然后尝试给每个块也分配一个标签，对于标签为t的对象会被优先分配到标签为t的块里。首先我们我们顺序枚举找到一个最大的时间点T，使得前1800T时间内的对象能够被预分配到磁盘里（不考虑删除）。 接下来我们可以通过一个简单的迭代算法求解如下问题：

• 对于每个标签t，假设其在1800T的创建的对象总长度为  ，则我们要至少为其分配 １ 个块。
• 每个块有了标签之后，我们可以算出每个1800时间片内磁盘的期望负载，我们希望这个负载的方差尽可能小（负载均衡）。

因为预处理没有给出具体到秒的信息，同时我们的插入算法也不能完全通过公式简单确定，所以我们的负载均衡目标函数并不是真正负载的无偏估计量，所以这个迭代算法简单设计一下就好，更好的算法并不能带来更好的结果。

对象删除事件

直接删除就可以，如果有磁盘正在读取这个对象，需要特判并修改一下状态就行了。

对象插入事件

对象插入的核心在于找到要把这个对象插入到哪3个块里，因为对象会动态的插入和删除，所以我们无法保证每个对象都一定会被插入到同样标签的块里，所以此处我们要做一些额外的处理。

1. 计算标签之间的相似度。我们以1800时间片作为区间长度，根据全局预处理的信息可以得到每个标签在每个区间里读取的对象长度，据此可以得到一个读取向量  ，其中  定义为标签t在时间  内读取的对象总长度。接下来我们定义两个标签  和  之间的余弦相似度为  。
2. 如果标签  的所有块都已经满了，那么我们会选择一个与  最相似的标签  （通过余弦相似度），并将其插入到  所在的块里。
3. 在确定了要插入到哪个块里之后，只需要从左到右扫描，找到第一个连续的能存下这个对象的位置并分配给这个对象即可。

上面介绍的是插入算法的概述，具体实现时有很多基于数据集调节的超参数，包括但不限于：

• PENALIZE_MULTI_COLOR：惩罚有多个标签的块。如果一个块里的标签种类很多，那么对它的读取就很可能不够连续，我们尽量不把对象向这种块里分配。
• SAME_COLOR_INC：如果一个块里拥有的和被插入对象标签相同的对象越多，那么在插入的时候就更应该被优先选中。
• LEFT_BLOCK_FIRST：优先插入到这个磁盘里和对象标签相同的第一个块里。

对象读取事件

对于每一个磁盘，我们顺序扫描并读取所有经过的有请求的对象。在每次进入到一个新的块的时候，可以选择继续读取这个块，或者跳转到一个新的块。因为跳转需要耗费额外的时间，所以只有当新的块的价值是当前块的价值的JUMP_COEF倍的时候才会跳转。块的价值通过如下公式计算：

其中base、load、time、tokens是需要计算的变量，DISK_POW_JMP、TIME_POW、TOKENS_POW是超参数。下面介绍一下每一个变量的计算方式（细节请参考score_blocks函数）：

• base定义了一个块的基础价值，也就是这个块里所有请求的对象的长度之和。这里需要注意的一点是，为了让不同磁盘读取不同的块（以及同一个磁盘不同head读取不同的块）我们需要把所有其它head向后  长度遇到的对象掩码掉，也就是说他们不参与  的计算。
• load表示这块中的对象的3个副本所在的所有磁盘的负载量的和。这一项存在的意义是为了负载均衡，也就是说要尽可能为高负载的其它磁盘分担请求。
• time表示当前时间与上一次处理这个块的时间差。时间差越大，请求越容易超时，所以我们给时间差大的块更大的价值。
• tokens表示从头到尾处理完这个块需要耗费多少个令牌。因为对象在块中的排布可能非常碎片化，导致读取效率较低，所以我们给需要更多令牌才能读完的块更小的价值。

需要注意的是，对于空的位置或者是没有请求的对象并不一定总是会pass过去，如果间隔很短，read过去可能消耗的tokens更少。最优解的求解可以用一个简单的动态规划来实现，为了进一步提升程序的效率，我们甚至可以预处理这个动态规划（参加calculate_action函数），这样决策的时间复杂度就是O(1)了。

复赛赛题解析

垃圾回收

垃圾回收对于我们的算法性能提升非常有限，所以我们只实现了简单的垃圾回收策略。对于一个块，如果两个相邻对象之间有空隙（非连续排列），那么就给这个块的权值增加1。在垃圾回收的时候，我们把块按照权值排序（碎片化严重的块排在前面），依次处理每一个块。对于每一个被处理的块，我们从后往前扫描每一个对象，并尝试把它们往前挪动。

超时预测

我们的超时预测算法也非常非常的简单，并且能达到非常理想的效果。在一个开始的尝试中，我们尝试当超时事件发生频率过高时，直接删除某种类型标签的所有对象。但是我们很快发现，这样的删除粒度太粗了，很容易删多或者删少，我们要做的就是降低删除粒度——删除块。

我们动态维护一个删除比例factor，以长度105作为预测区间。在每一个新的预测区间开始的时候，我们会删除掉一些块，这些块的请求总数等于  （其中  是上一个预测区间的请求总数）。这样做的话，如果请求数是不变化的，那么我们删除的块应该刚刚好。当然，实际情况是请求数会发生变化，所以在每次预测开始之前，我们先观察一下上一个预测区间内发生的情况：

• 如果没有超时事件发生，那么说明我们需要减少删除的比例，我们简单的将factor乘上一个常量DECREASE_FACTOR即可（一般设为0.95或者0.9）。
• 如果有超时事件发生，并且超时的请求数比例为rate，我们只需要factor += rate，并将其作为新的预测区间中超时的比例。

通过这个简单的、动态的超时预测算法，我们可以把busy率降到0.2%甚至0.1%以下。

超参数搜索

到复赛之后，我们算法的超参数已经15个以上了，如果简单的手调的话非常耗时间，而且很难收敛到最优解。考虑到线下数据和线上数据是同分布的，我们可以用线下数据拟合一个最优的超参数，并提交到线上，理论上来说也能得到一个很不错的结果。

我们考虑将整个超参数的搜索过程自动化，首先要做的事情就是把所有的超参数定义提取出来，放到一个额外的文件里（hyperparameters.h）。这样我们就可以用正则表达式匹配和修改超参数，然后重新编译程序。

具体的，我们在 华为云/阿里云 上购买192核的高性能服务器（竞价的话大约10块钱每小时，相比于奖金是小钱了）。我们的超参数搜索包括两轮：

1. 启动192个进程，每个进程随机一套超参数。最后选择一套得分最高的超参数进入下一轮。
2. 在这一轮里，我们枚举每一个超参数，假设这个超参数有C种可能的取值，那么我们对每个取值启动  个线程（每个线程用不同的随机种子），并取这些线程得分的平均值作为这个取值的得分。然后将这个超参数设为计算出的最优取值，并继续处理下一个超参数。

这里额外补充3点注意事项：

• 因为我们的算法具有一定的抖动性，所以单次的运行结果好并不一定是真的好，选多个随机种子运行并取平均值是个更稳定的做法。
• 现场赛的时间只有3小时！！！如果程序运行的太慢，3小时不够搜索出最优的超参数，我们需要优化程序的执行效率。这里就涉及了很多的性能压榨技巧，就不详细展开了（可以参考我知乎的其它文章），当然后果就是程序的可读性显著降低......
• 决赛开始就提供3个数据集了，我们非常暴力的开了3台192核服务器，对每个数据集计算出最优的超参数，并提交到线上。
• 因为线上线下的数据集并不相同（只是同分布），所以我们的算法和算力已经足够了，更好的算法以及更高的算力并不能产生更好的结果（只会过拟合到本地数据）。

具体的超参数搜索算法请参见finetune.py。

决赛赛题解析

标签计算

我们的标签计算算法也非常简单。我们还是将时间按照1800作为跨度进行分片，对每个对象统计出在每个跨度里有多少个请求，这样每个对象都得到了一个读取分布的向量。类似的，对于每个标签，我们将其所属对象的向量的平均值作为这个标签的向量。接下来对于没有标签的对象，我们只需要计算出它的向量与哪个标签的向量最接近就行了。向量的距离有很多种定义方式，这是一个可以调节的超参数。

卡时迭代

因为第二轮是一个离线处理的过程，所以我们可以选取不同的随机种子多跑几次（直到运行时间接近时间限制600s），并将得到的最好结果输出。

离线预分配

离线预分配是一个能大幅提升分数的算法（在决赛中提升了150w分左右）。首先我们观察数据的分布，可以总结出如下的特点：

1. 在前期（比如前30000s）读取的数量较少，但是插入的数量较多。
2. 随着时间的推移，我们的算法（我估计别人写的算法也一样）碎片话会越来越严重，也就是说会有很多对象存储的不够连续，也会有很多块存储了多种标签的对象。

第2点说明我们的算法处理请求的效率随着时间推移逐渐下降，但是请求数最多的时候是在后期而不是前期！！！这就启发我们设计一个预分配算法，来均衡前期和后期的请求处理效率。

具体地，假设我们预分配的时间长度为T，我们先找出在[1, T]时刻内创建的所有对象，将他们按照删除时间从大到小排序，删除时间相同时按照插入时间从小到大排序，依次进行插入。并将插入的位置作为对这个对象预留的位置，在后续执行过程中预分配的位置是不能被占用的。这样做会产生如下两个结果：

1. 在前期（比如  时刻），对象分布非常不联系，请求处理效率较低。但是前期的请求数量很少，所以这并不重要！
2. 在后期（比如  时刻，以及往后的其它时刻），对象分布更连续了。因为后期的请求数多，所以这能显著提高分数！

对于离线预分配还有几点需要额外阐述：

1. T是如何选取的？如果选的太小了，那么预分配的效果就不好；如果选的太大了，那么无法对[1, T]中的每个对象都预分配位置，算法会fail掉。一个朴素的思路是从小达到枚举T，直到算法fail掉，但是这样做效率太低了。一个更好的做法是二分T的值，这个不难想，就不详细展开了。
2. 对于T时刻之后的插入还是默认插入算法吗？显然不是！在程序运行到T时刻之后，我们可以再运行一次预分配算法，为后续插入继续进行预分配来提高得分。

后记

非满编队打这种比赛是真的累，中途都想弃赛了！决赛题目做出了巨大的改动，还只有4天时间可以写代码，完全不够收敛到个人能力的最大值哈哈哈哈。

在决赛练习赛的4天时间里，我大概只有2天时间在写算法，然后实现了数据生成器generator.py以及debug.py并对程序进行了充分的测试。我觉得这是一个非常重要的环节（也是我这些年比赛的经验吧），对于2k行的代码有bug是很正常的事情，在最后的阶段一定要对程序进行充分测试，如果现场赛触发了bug，后果将是毁灭性的！

在这次比赛的赛后，我也了解到了一些选手的代码跑测试赛数据没有问题，跑现场赛的数据就会Runtime Error。最窒息的还是本地没有错，交上去Runtime Error！如果这种情况发生了，后果可能就是一个多月的努力全都白费了，所以在最后我选择宁肯少实现几个trick也要做好最终的测试！！！

最后提一下，我的ACM队友也参加了这场比赛，并获得了亚军，他的代码和赛题解析可以在这里看到：https://github.com/yulemao/huawei-code-craft2025

本文转载自知乎  [ 2025华为软件精英挑战赛——题目解析 ]

作者 by [ 孙咖啡 ]