两届获奖选手 手把手教你如何征战华为软件精英挑战赛

5 月 21-22 日,2022 第八届华为软件精英挑战赛-“普朗克计划”总决赛及颁奖典礼在深圳成功举办。最终,9 支优秀队伍凭借优异表现分享了 66 万元总奖金池。其中,来自粤港澳赛区的“量化交易研究小组”队,获得全球总决赛亚军。作为连续获得最优美代码奖和亚军的软挑老兵,来自华南理工大学的优秀选手李路撰文分享了其赛队参赛经验。

2022 华为软件精英挑战赛,赛题聚焦视频直播场景中的流量调度问题,结合运营商的 95 计费规则,要求选手合理设计算法,在满足客户要求的前提下最小化网络使用成本。我们队伍“量化交易研究小组”历经大赛四个环节(初赛,复赛,复活赛,决赛),最终取得了亚军的成绩 。

一、缘起

作为软挑老兵,去年作为“Z 的绝对值”的一员我和另外两位队友 HZ 和 CC 一起获得了 2021 年软件精英挑战赛决赛最优美代码奖。在感受到专家们对我们代码肯定的同时也留下了不小的遗憾,于是今年决定再战以期望更进一步。

1653557794759966.png

二、准备

有了往年的经验,在赛题出来之后我第一时间就去花 18 块买了一台和线上判题环境相同的华为云服务器(相信我,这一步非常关键,特别是那些对编写跨平台代码不太熟悉的同学,18 元绝对物有所值)。然后就是配置好远程开发环境,编写赛题 baseline,编写判题器,提交代码。挂机等复赛(这里看个人情况,我个人认为因为初赛难度并不大,大家尽可能写一版不错的 baseline 之后就去做自己的事情,毕竟软挑赛程不短,大家还是要兼顾自己的学习生活 , 我们队最终以 24 名进入了复赛)。

三、折戟

复赛名不虚传,是整个软挑赛最卷的一个阶段,各路编程高手各显神通,mmap ,multithread 等初赛一般不会见到的技术这个时候都会闪亮登场. 历年来,软挑赛都是没办法找到最优解的,但是因为往往对选手的优化方案有比较强的时间限制(今年是 300S),所以选手一般不用考虑线性规划,机器学习这种重量级武器。 九成方案大致上都是先求得一个初始解,再在这个解上做一些优化, 去年和今年都可以用迁移优化初始解。当然,具体能优化多少还得看初始解的求的好不好了。到了划重点,敲黑板的时刻了,以上说的所有经验,都没有这里重要,那就是代码质量, 我这里所说的代码质量并非写的代码是否好看,是否高级,而是说严格控制 bug 的数量,以及控制程序运行时间,控制内存占用等。 为什么要强调这个,因为官方给大家练习的线下数据集往往是比较弱的,数据量小,而且还测不出一些边界条件。所以大家在练习的时候最好是要自己写测试程序,最好能多设计一些测试用例,设计自己的数据集也是个不错的选择(这些工作一般可以分配给团队的挂件选手完成,一是提升他们的参与度,而是减轻主程压力)。之所以特别强调了以上这点,正是因为我们今年的血泪史,如下图所示。

复赛练习赛最终排名:

复赛正式赛最终排名:

复赛正式赛提交作品情况:

1653557867493614.png

正式赛的时间是下午一点到四点,我们几乎是三点才出一个分数。尽管后面马力全开,也不能力挽狂澜。若是今年没有复活赛,可以说我们也是提前告别了。所以这一阶段,总结就是,不要太在意练习赛排名,大家参赛的时候一定要保证代码质量。

四、复活

得到这样一次机会我都不知道该说自己是撞了大运还是天道酬勤。汲取复赛教训,这一阶段我基本上可以说是用了十层功力去优化代码了,排除了各种潜在 bug,并从性能,可扩展性方面大幅度优化了代码。下面贴一段优化过后的代码(我是不是也可以竞争最优美代码奖,hhhhh)。

以上函数定义了一个对免费边缘节点拉取流量的操作,这几乎是我这个阶段对代码优化程度的一个缩影了。优化之后,代码简洁,高效,而且性能不错。最终,复活赛我们队伍也成功以第一名的成绩晋级如愿获得了宝贵的决赛入场券。

五、终战

由于粤港澳赛区大部分晋级队伍来自华南理工大学,赛事主办方很贴心的用专车直接接送决赛选手。一如往年,我们抵达安朴逸城后领取了决赛大礼包,然后就开始写代码了。不要怀疑,这一夜很多人没有睡觉,毕竟我知道不少选手们四五点还在群里讨论问题,说决赛前的这两个夜晚是整个赛事周期中最紧张的时段完全不为过,什么奖金,什么绿卡,这时候都抛诸脑后了,大家都在享受着巅峰对决的快感,只为终极一战。 关于决赛的经验,我想对明年的参赛选手说的是,无论大家在练习赛表现的如何,不要放弃,一定要坚持到底。对自己的代码不断审视,不断优化,提升代码的可读性,可扩展性,这样才能在决赛现场发挥百分百的实力,毫不夸张的说,算法和 bonus(决赛赛题变更点) 对最终成绩的影响是五五开的。

六、完整方案

由于边缘节点 采用 95 计费规则 , 那我们就应该充分的利用不计费的那 5%个时刻 (免费的自助餐,竖折进,横着出,才是最优解)。这里有两个问题, 一个是选择哪些时刻作为 5%时刻,二个是是否用上所有边缘节点的 5%时刻。

我们仔细观察边缘节点的计费公式:

1. 所有时刻都不用,计费为 0,这就是全程不开机的情况

2. 开机(至少一个时刻用过)且 95 计费位小于等于 V,那么收费为 V

3. 95 计费位大于 V,由以上二次函数定义费用,注意这里分子的平方其实是惩罚项, 也就是说,如果某个边缘承载的流量过高,那么对应的惩罚也会很大。 但是同时,分母的带宽又似乎给了我们指示,带宽越大,惩罚越小回到我们之前提出的两个问题:

5%的免费用在哪些时刻。 我们从宏观上考虑这个问题,暂不考虑 5%的免费并忽略一些细节,每个时刻每个边缘节点承载的流量～= 时刻总流量/边缘节点总数,而边缘节点数量在每个时刻是固定的,那么我们可以大致认为,95 计费位由流量总和排在前面的那些时刻决定,也就是说,我们用 5%的免费机会去拉低这些时刻的流量的话,那么 95 计费位也会跟着下降。

是否用上所有的边缘节点。 从上述边缘节点计费公式我们可以知道,只要开机,那么就至少会有费用 V。 我们考虑两个极端的情况, 一台边缘节点拉满了 5%的免费时刻,也就是 5%*T*Sitebandwidth;T*T*Sitebandwidth;Site_band_width;一台边缘节点只在一个时刻拉了 size=1 的流量。 相信大家不难看出这里面的问题,那就是,如果我们能够拉取的免费流量比较多,那就需要开机,如过拉的很少,那就得不偿失了。

下面贴出求每个时刻总流量的关键代码:

在选取了拉取哪些时刻进行流量拉取(削峰)后,更重要的一点,是我们要决定,用怎样的边缘服务器去承载这些峰值流量,这里也是决赛区分于复赛的关键点之一:

在复赛,我们针对边缘节点的带宽从大到小排序,也就是说优先用带宽大的去承载,效果往往是不错的。

原因正如前述分析边缘节点成本公式时所说,带宽越大,免费拉取的流量越多,同时,承载同样流量,在计费位需要的成本越低,综合以上两点,只需要排序带宽即可。 然而,在决赛中,多了中心成本的考量,对于中心成本,一个显而易见的事实是,我们将同样类型的流都放到同一个边缘节点里,将会获得最小的中心代价(正如练习赛的超级边缘节点那样). 基于以上分析,在决赛,我们就不能单独根据边缘结点的带宽来进行排序。 我们的方案如下,首先对边缘节点根据带宽从大到小进行排序,并归一化;其次,对边缘节点,根据其与客户连接的度从大到小排序(度越大,能拉取的同类型流越多,中心代价越小),同样进行归一化,最终,将两个归一值相加,作为边缘节点的选取优先级。

在解决了以上两个问题之后,我们需要面临的一个问题就是以什么样的方式拉取流量的问题。这里,我们设计了两种方案:

一种是对流按大小从大到小排序,这里类似于用石头沙子装瓶子,先放大的,再放小的;另外一种是利用同类流聚合的方式,即相同类型的流放在一起,同时同一类型的流内部从大到小排序。 设计的接口利用模板统一了这两种拉取方式,使用起来十分方便。 同时值的一提的是这里我利用了多路归并思想,并非 nlogn 的复杂度,这一点也让程序性能大幅度提升。

以上是核心思想,至于其他值得一提的,可能就是关于缓存的逐级更新问题,我们用 lambda 表达式以及递归,非常简单的解决了这个问题:

如大家所见,决赛 bonus 其实我只更改了三元表达式那一句话。

总而言之,我认为,简单才是最美,如果让我在 99 分的优美代码和 100 分的屎山中选择,我会毫不犹豫选择前者。