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

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

　　一、緣起

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

　　二、準備

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

　　三、折戟

　　復賽名不虛傳，是整個軟挑賽最卷的一個階段，各路編程高手各顯神通，mmap ,multithread等初賽一般不會見到的技術這個時候都會閃亮登場. 歷年來,軟挑賽都是沒辦法找到最優解的，但是因為往往對選手的優化方案有比較強的時間限制(今年是300S)，所以選手一般不用考慮線性規劃，機器學習這種重量級武器。 九成方案大致上都是先求得一個初始解，再在這個解上做一些優化， 去年和今年都可以用遷移優化初始解。當然，具體能優化多少還得看初始解的求的好不好了。到了劃重點，敲黑板的時刻了，以

　　上說的所有經驗，都沒有這里重要，那就是代碼質量， 我這里所說的代碼質量并非寫的代碼是否好看，是否高級，而是說嚴格控制bug的數量，以及控制程序運行時間，控制內存占用等。 為什么要強調這個，因為官方給大家練習的線下數據集往往是比較弱的，數據量小，而且還測不出一些邊界條件。所以大家在練習的時候最好是要自己寫測試程序，最好能多設計一些測試用例，設計自己的數據集也是個不錯的選擇(這些工作一般可以分配給團隊的掛件選手完成，一是提升他們的參與度，而是減輕主程壓力)。之所以特別強調了以上這點，正是因為我們今年的血淚史，如下圖所示。

　　復賽練習賽最終排名：

　　復賽正式賽最終排名：

　　復賽正式賽提交作品情況：

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

　　四、復活

　　得到這樣一次機會我都不知道該說自己是撞了大運還是天道酬勤。汲取復賽教訓，這一階段我基本上可以說是用了十層功力去優化代碼了，排除了各種潛在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分的屎山中選擇，我會毫不猶豫選擇前者。