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

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

一、緣起

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

二、準(zhǔn)備

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

三、折戟

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

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

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

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

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

四、復(fù)活

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

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

五、終戰(zhàn)

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

六、完整方案

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

我們仔細觀察邊緣節(jié)點的計費公式：

1. 所有時刻都不用，計費為0，這就是全程不開機的情況

2. 開機(至少一個時刻用過）且95計費位小于等于V，那么收費為V

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

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

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

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

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

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

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

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

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

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

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

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

生成海報

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