兩屆獲獎(jiǎng)選手 手把手教你如何征戰(zhàn)華為軟件精英挑戰(zhàn)賽

5月21-22日，2022第八屆華為軟件精英挑戰(zhàn)賽-“普朗克計(jì)劃”總決賽及頒獎(jiǎng)典禮在深圳成功舉辦。最終，9支優(yōu)秀隊(duì)伍憑借優(yōu)異表現(xiàn)分享了66萬元總獎(jiǎng)金池。其中，來自粵港澳賽區(qū)的“量化交易研究小組”隊(duì)，獲得全球總決賽亞軍。作為連續(xù)獲得最優(yōu)美代碼獎(jiǎng)和亞軍的軟挑老兵，來自華南理工大學(xué)的優(yōu)秀選手李路撰文分享了其賽隊(duì)參賽經(jīng)驗(yàn)。

2022華為軟件精英挑戰(zhàn)賽，賽題聚焦視頻直播場景中的流量調(diào)度問題，結(jié)合運(yùn)營商的95計(jì)費(fèi)規(guī)則，要求選手合理設(shè)計(jì)算法，在滿足客戶要求的前提下最小化網(wǎng)絡(luò)使用成本。我們隊(duì)伍“量化交易研究小組”歷經(jīng)大賽四個(gè)環(huán)節(jié)(初賽，復(fù)賽，復(fù)活賽，決賽)，最終取得了亞軍的成績 。

一、緣起

作為軟挑老兵，去年作為“Z的絕對(duì)值”的一員我和另外兩位隊(duì)友HZ和CC一起獲得了2021年軟件精英挑戰(zhàn)賽決賽最優(yōu)美代碼獎(jiǎng)。在感受到專家們對(duì)我們代碼肯定的同時(shí)也留下了不小的遺憾，于是今年決定再戰(zhàn)以期望更進(jìn)一步。

二、準(zhǔn)備

有了往年的經(jīng)驗(yàn)，在賽題出來之后我第一時(shí)間就去花18塊買了一臺(tái)和線上判題環(huán)境相同的華為云服務(wù)器(相信我，這一步非常關(guān)鍵，特別是那些對(duì)編寫跨平臺(tái)代碼不太熟悉的同學(xué)，18元絕對(duì)物有所值）。然后就是配置好遠(yuǎn)程開發(fā)環(huán)境，編寫賽題baseline，編寫判題器，提交代碼。掛機(jī)等復(fù)賽（這里看個(gè)人情況，我個(gè)人認(rèn)為因?yàn)槌踬愲y度并不大，大家盡可能寫一版不錯(cuò)的baseline之后就去做自己的事情，畢竟軟挑賽程不短，大家還是要兼顧自己的學(xué)習(xí)生活 , 我們隊(duì)最終以24名進(jìn)入了復(fù)賽)。

三、折戟

復(fù)賽名不虛傳，是整個(gè)軟挑賽最卷的一個(gè)階段，各路編程高手各顯神通，mmap ,multithread等初賽一般不會(huì)見到的技術(shù)這個(gè)時(shí)候都會(huì)閃亮登場. 歷年來,軟挑賽都是沒辦法找到最優(yōu)解的，但是因?yàn)橥鶎?duì)選手的優(yōu)化方案有比較強(qiáng)的時(shí)間限制(今年是300S），所以選手一般不用考慮線性規(guī)劃，機(jī)器學(xué)習(xí)這種重量級(jí)武器。 九成方案大致上都是先求得一個(gè)初始解，再在這個(gè)解上做一些優(yōu)化， 去年和今年都可以用遷移優(yōu)化初始解。當(dāng)然，具體能優(yōu)化多少還得看初始解的求的好不好了。到了劃重點(diǎn)，敲黑板的時(shí)刻了，以上說的所有經(jīng)驗(yàn)，都沒有這里重要，那就是代碼質(zhì)量， 我這里所說的代碼質(zhì)量并非寫的代碼是否好看，是否高級(jí)，而是說嚴(yán)格控制bug的數(shù)量，以及控制程序運(yùn)行時(shí)間，控制內(nèi)存占用等。 為什么要強(qiáng)調(diào)這個(gè)，因?yàn)楣俜浇o大家練習(xí)的線下數(shù)據(jù)集往往是比較弱的，數(shù)據(jù)量小，而且還測不出一些邊界條件。所以大家在練習(xí)的時(shí)候最好是要自己寫測試程序，最好能多設(shè)計(jì)一些測試用例，設(shè)計(jì)自己的數(shù)據(jù)集也是個(gè)不錯(cuò)的選擇(這些工作一般可以分配給團(tuán)隊(duì)的掛件選手完成，一是提升他們的參與度，而是減輕主程壓力）。之所以特別強(qiáng)調(diào)了以上這點(diǎn)，正是因?yàn)槲覀兘衲甑难獪I史，如下圖所示。

復(fù)賽練習(xí)賽最終排名：

復(fù)賽正式賽最終排名：

復(fù)賽正式賽提交作品情況：

正式賽的時(shí)間是下午一點(diǎn)到四點(diǎn)，我們幾乎是三點(diǎn)才出一個(gè)分?jǐn)?shù)。盡管后面馬力全開，也不能力挽狂瀾。若是今年沒有復(fù)活賽，可以說我們也是提前告別了。所以這一階段，總結(jié)就是，不要太在意練習(xí)賽排名，大家參賽的時(shí)候一定要保證代碼質(zhì)量。

四、復(fù)活

得到這樣一次機(jī)會(huì)我都不知道該說自己是撞了大運(yùn)還是天道酬勤。汲取復(fù)賽教訓(xùn)，這一階段我基本上可以說是用了十層功力去優(yōu)化代碼了，排除了各種潛在bug，并從性能，可擴(kuò)展性方面大幅度優(yōu)化了代碼。下面貼一段優(yōu)化過后的代碼(我是不是也可以競爭最優(yōu)美代碼獎(jiǎng),hhhhh)。

以上函數(shù)定義了一個(gè)對(duì)免費(fèi)邊緣節(jié)點(diǎn)拉取流量的操作，這幾乎是我這個(gè)階段對(duì)代碼優(yōu)化程度的一個(gè)縮影了。優(yōu)化之后，代碼簡潔，高效，而且性能不錯(cuò)。最終，復(fù)活賽我們隊(duì)伍也成功以第一名的成績晉級(jí)如愿獲得了寶貴的決賽入場券。

五、終戰(zhàn)

由于粵港澳賽區(qū)大部分晉級(jí)隊(duì)伍來自華南理工大學(xué)，賽事主辦方很貼心的用專車直接接送決賽選手。一如往年，我們抵達(dá)安樸逸城后領(lǐng)取了決賽大禮包，然后就開始寫代碼了。不要懷疑，這一夜很多人沒有睡覺，畢竟我知道不少選手們四五點(diǎn)還在群里討論問題，說決賽前的這兩個(gè)夜晚是整個(gè)賽事周期中最緊張的時(shí)段完全不為過，什么獎(jiǎng)金，什么綠卡，這時(shí)候都拋諸腦后了，大家都在享受著巔峰對(duì)決的快感，只為終極一戰(zhàn)。 關(guān)于決賽的經(jīng)驗(yàn)，我想對(duì)明年的參賽選手說的是，無論大家在練習(xí)賽表現(xiàn)的如何，不要放棄，一定要堅(jiān)持到底。對(duì)自己的代碼不斷審視，不斷優(yōu)化，提升代碼的可讀性，可擴(kuò)展性，這樣才能在決賽現(xiàn)場發(fā)揮百分百的實(shí)力，毫不夸張的說，算法和bonus(決賽賽題變更點(diǎn)) 對(duì)最終成績的影響是五五開的。

六、完整方案

由于邊緣節(jié)點(diǎn) 采用95 計(jì)費(fèi)規(guī)則 , 那我們就應(yīng)該充分的利用不計(jì)費(fèi)的那5%個(gè)時(shí)刻 (免費(fèi)的自助餐,豎折進(jìn)，橫著出，才是最優(yōu)解)。這里有兩個(gè)問題， 一個(gè)是選擇哪些時(shí)刻作為5%時(shí)刻，二個(gè)是是否用上所有邊緣節(jié)點(diǎn)的5%時(shí)刻。

我們仔細(xì)觀察邊緣節(jié)點(diǎn)的計(jì)費(fèi)公式：

1. 所有時(shí)刻都不用，計(jì)費(fèi)為0，這就是全程不開機(jī)的情況

2. 開機(jī)(至少一個(gè)時(shí)刻用過）且95計(jì)費(fèi)位小于等于V，那么收費(fèi)為V

3. 95計(jì)費(fèi)位大于V，由以上二次函數(shù)定義費(fèi)用，注意這里分子的平方其實(shí)是懲罰項(xiàng), 也就是說，如果某個(gè)邊緣承載的流量過高，那么對(duì)應(yīng)的懲罰也會(huì)很大。 但是同時(shí)，分母的帶寬又似乎給了我們指示，帶寬越大，懲罰越小回到我們之前提出的兩個(gè)問題：

5%的免費(fèi)用在哪些時(shí)刻。 我們從宏觀上考慮這個(gè)問題，暫不考慮5%的免費(fèi)并忽略一些細(xì)節(jié)，每個(gè)時(shí)刻每個(gè)邊緣節(jié)點(diǎn)承載的流量～= 時(shí)刻總流量/邊緣節(jié)點(diǎn)總數(shù)，而邊緣節(jié)點(diǎn)數(shù)量在每個(gè)時(shí)刻是固定的，那么我們可以大致認(rèn)為，95計(jì)費(fèi)位由流量總和排在前面的那些時(shí)刻決定，也就是說，我們用5%的免費(fèi)機(jī)會(huì)去拉低這些時(shí)刻的流量的話，那么95計(jì)費(fèi)位也會(huì)跟著下降。

是否用上所有的邊緣節(jié)點(diǎn)。 從上述邊緣節(jié)點(diǎn)計(jì)費(fèi)公式我們可以知道，只要開機(jī)，那么就至少會(huì)有費(fèi)用V。 我們考慮兩個(gè)極端的情況， 一臺(tái)邊緣節(jié)點(diǎn)拉滿了5%的免費(fèi)時(shí)刻，也就是5%*T*Sitebandwidth;T*T*Sitebandwidth;Site_band_width;一臺(tái)邊緣節(jié)點(diǎn)只在一個(gè)時(shí)刻拉了size=1 的流量。 相信大家不難看出這里面的問題，那就是，如果我們能夠拉取的免費(fèi)流量比較多，那就需要開機(jī)，如過拉的很少，那就得不償失了。

下面貼出求每個(gè)時(shí)刻總流量的關(guān)鍵代碼:

在選取了拉取哪些時(shí)刻進(jìn)行流量拉取(削峰)后，更重要的一點(diǎn)，是我們要決定，用怎樣的邊緣服務(wù)器去承載這些峰值流量，這里也是決賽區(qū)分于復(fù)賽的關(guān)鍵點(diǎn)之一：

在復(fù)賽，我們針對(duì)邊緣節(jié)點(diǎn)的帶寬從大到小排序，也就是說優(yōu)先用帶寬大的去承載，效果往往是不錯(cuò)的。

原因正如前述分析邊緣節(jié)點(diǎn)成本公式時(shí)所說，帶寬越大，免費(fèi)拉取的流量越多，同時(shí)，承載同樣流量，在計(jì)費(fèi)位需要的成本越低，綜合以上兩點(diǎn)，只需要排序帶寬即可。 然而，在決賽中，多了中心成本的考量，對(duì)于中心成本，一個(gè)顯而易見的事實(shí)是，我們將同樣類型的流都放到同一個(gè)邊緣節(jié)點(diǎn)里，將會(huì)獲得最小的中心代價(jià)(正如練習(xí)賽的超級(jí)邊緣節(jié)點(diǎn)那樣). 基于以上分析，在決賽，我們就不能單獨(dú)根據(jù)邊緣結(jié)點(diǎn)的帶寬來進(jìn)行排序。 我們的方案如下，首先對(duì)邊緣節(jié)點(diǎn)根據(jù)帶寬從大到小進(jìn)行排序，并歸一化；其次，對(duì)邊緣節(jié)點(diǎn)，根據(jù)其與客戶連接的度從大到小排序(度越大，能拉取的同類型流越多，中心代價(jià)越小),同樣進(jìn)行歸一化，最終，將兩個(gè)歸一值相加，作為邊緣節(jié)點(diǎn)的選取優(yōu)先級(jí)。

在解決了以上兩個(gè)問題之后，我們需要面臨的一個(gè)問題就是以什么樣的方式拉取流量的問題。這里，我們?cè)O(shè)計(jì)了兩種方案：

一種是對(duì)流按大小從大到小排序，這里類似于用石頭沙子裝瓶子，先放大的，再放小的；另外一種是利用同類流聚合的方式，即相同類型的流放在一起，同時(shí)同一類型的流內(nèi)部從大到小排序。 設(shè)計(jì)的接口利用模板統(tǒng)一了這兩種拉取方式，使用起來十分方便。 同時(shí)值的一提的是這里我利用了多路歸并思想，并非nlogn的復(fù)雜度，這一點(diǎn)也讓程序性能大幅度提升。

以上是核心思想，至于其他值得一提的，可能就是關(guān)于緩存的逐級(jí)更新問題，我們用lambda表達(dá)式以及遞歸，非常簡單的解決了這個(gè)問題：

如大家所見，決賽bonus其實(shí)我只更改了三元表達(dá)式那一句話。

總而言之，我認(rèn)為，簡單才是最美，如果讓我在99分的優(yōu)美代碼和100分的屎山中選擇，我會(huì)毫不猶豫選擇前者。

生成海報(bào)

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請(qǐng)進(jìn)一步核實(shí)，并對(duì)任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對(duì)有關(guān)資料所引致的錯(cuò)誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個(gè)人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識(shí)產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí)，應(yīng)及時(shí)向本網(wǎng)站提出書面權(quán)利通知或不實(shí)情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會(huì)依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。