第142章 規則

投票推薦 加入書籤 小說報錯

  第142章 規則

  熱烈掌聲響起來。

  觀眾席上大部分人都在盯著大屏幕,等著看規則。

  大屏幕亮了。

  團隊現場編程。限時三小時。共一道大題,分三個階段遞進。

  題目:設計一套中文輸入法引擎。

  林東看到這行字的時候,手指在鍵盤上停了一下。

  輸入法。

  屏幕、電池、主板、外殼、觸控算法、天線、驅動一全都齊了,唯獨輸入法還用的是開源的方案,體驗一般,適配也麻煩。

  他本來打算年後做一套,現在好了,決賽題目就是輸入法。

  他嘴角動了一下。

  做完直接拿走。

  階段一(60分鐘):核心索引。

  設計拼音到漢字的索引結構。給定詞庫(約10萬詞條),要求支持拼音輸入,返回匹配的候選詞列表。響應時間不超過20ms,內存占用不超過1MB。

  階段二(60分鐘):智能聯想。

  在階段一的基礎上,增加詞組聯想功能。輸入一個詞,系統自動預測下一個可能的詞。內存占用增加不超過0.5MB。

  階段三(60分鐘):動態優化。

  在階段二的基礎上,增加詞頻動態調整功能。用戶的使用習慣實時影響候選詞排序。內存占用增加不超過0.5MB,總內存不超過2MB。

  提交內容:每階段完成後提交代碼,系統自動評測。三階段全通過者按總用時排名。

  李教授頓了頓,掃了一圈全場:「現在,我宣布—一創新杯程序設計大賽決賽,正式開始。」

  大屏幕上倒計時跳動:03:00:00。

  體育館裡安靜下來,只有鍵盤敲擊的聲音。

  林東沒有急著動手。

  他把三個階段的要求又看了一遍,然後靠在椅背上,閉上眼睛。

  階段一,核心索引。

  拼音到漢字的映射,常規做法是用Trie樹,時間複雜度0(n),內存可控。但Trie樹的每個節點都要存26個指針,10萬詞條下來,內存肯定超1MB。得換一種思路。

  他想到了李虎重寫後的那個數據結構。

  第二輪比賽,李虎那道題的原解法是0(n2),重寫後降到了0(nlogn)。

  核心改進是把嵌套循環換成了哈希加二分查找,數據存儲從鍊表換成了數組。當時林東站在李虎後面看了一眼,覺得這個思路不錯,順手記下來了。沒想到今天用得上。

  他睜開眼睛,打開編輯器。

  先用哈希表存拼音到詞條索引的映射,再用數組存詞條本身。

  查詢的時候,哈希找到索引,二分查找定位,一次搞定。時間複雜度0(log

  n),內存占用—他算了一下,大概0.6MB。

  夠了。

  他開始寫代碼。

  手指落在鍵盤上,速度不快不慢。哈希函數、衝突處理、二分查找邊界—

  每一個細節都在他腦子裡過了好幾遍。他不是在「寫」代碼,是在「翻譯」腦子裡的東西。

  寫了大概三十分鐘,他停下來,檢查了一遍。哈希函數沒問題,二分查找邊界處理正確,內存分配沒有泄漏。

  他看了一眼旁邊的李虎。李虎也在寫,手指飛快,屏幕上代碼一行一行地跳出來。他寫的是階段一,用的也是哈希加二分查找一和林東的思路一模一樣。

  林東嘴角動了一下。

  他沒告訴李虎怎麼做,李虎也沒問他。兩個人想到一塊去了。是這道題的最優解就在那兒,誰水平夠,誰就能看到。

  他收回目光,繼續寫。

  又寫了十分鐘,代碼完成了。

  他按下「編譯」——通過。

  再按下「運行」——測試用例全部通過。

  響應時間——他看了一眼,12ms。內存占用——0.58MB。

  他深吸一口氣,按下「提交」。


  大屏幕上,四大天王隊的圖標亮了—一提交。

  觀眾席上一陣騷動。

  「這麼快?四十分鐘就提交了?」

  「張揚隊那邊還沒動靜呢。」

  「是不是太趕了?」

  李虎也轉過頭來,壓低聲音:「老四,你交了?」

  「嗯。」

  「這麼快?」

  林東沒回答,盯著大屏幕。

  幾秒鐘後,圖標變紅。

  未通過。

  觀眾席上響起一片議論。

  「被退回了。」

  「我說吧,太趕了。」

  「四大天王不會翻車吧?」

  周琳坐在觀眾席上,抓著陳露的胳膊,指甲都快掐進去了:「怎麼回事?」

  陳露盯著大屏幕,聲音很穩:「還沒結束。」

  林東看著屏幕上那個「未通過」,臉上沒什麼表情。

  他打開評測反饋,看了一眼—邊界條件。

  拼音「liang」和「lian」的分詞邊界沒處理。

  他暗罵了自己一聲。

  確實漏了。

  他開始改了。

  在哈希函數裡加了一個判斷,把「liang」和「lian」分開處理。

  五分鐘,改完。

  重新編譯,重新運行,測試用例全部通過。

  再次按下「提交」。

  大屏幕上,圖標變綠。

  通過。

  用時:四十五分鐘。

  林東靠在椅背上,長出一口氣。

  李虎在旁邊嘿嘿笑了一聲:「嚇我一跳。」

  「繼續。」林東說。

  階段一完成了,但其他人的階段一還沒完成。

  張揚隊那邊,階段一還沒提交。

  陳龍和許藏一直沒動手,在等林東和李虎寫完階段一,好接著做階段二。

  「階段二,誰來?」林東問。

  許藏開口了:「我來。」

  林東看了他一眼。

  「需要什麼?」林東問。

  「階段一的代碼。」許藏說,「還有詞庫。」

  林東把階段一的代碼發給他。

  許藏打開,從頭到尾看了一遍,沒說話。

  然後打開編輯器,開始寫。

  林東沒打擾他,靠在椅背上看著。

  許藏的思路和他不一樣。階段二要求詞組聯想—一輸入一個詞,系統自動預測下一個可能的詞。

  常規做法是統計詞與詞之間的共現頻率,詞庫10萬詞條,兩兩組合就是100億對,根本存不下。

  許藏用的不是常規做法。

  他把每個詞映射成一個固定維度的向量,然後計算向量之間的相似度。相似度高的詞,就是可能的下一個詞。

  這個思路,林東想過,但沒往深了想。

  因為向量維度太高,計算量太大。但許藏用了降維一用哈希把高維向量壓縮成低維,計算量從0(n2)降到了0(n)。

  許藏寫得很快,代碼量很少,但邏輯很繞。

  林東看了一遍,看懂了。陳龍也湊過來看了一遍,沒說話,但推了推眼鏡。

  五十分鐘後,許藏停下手指。

  「寫完了。」他說。

  「檢查了嗎?」陳龍問。

  「沒有。」許藏說。

  林東愣了一下:「沒檢查?」

  許藏看了他一眼:「你幫我檢查。」

  林東沒說話,把代碼拿過來,一行一行地看。

  哈希函數,沒問題。

  向量降維,沒問題。

  相似度計算,邊界條件沒處理。


  他改了一行代碼,加了一個判斷。

  「好了。」他說。

  許藏點了點頭,按下「提交」。

  大屏幕上,四大天王隊的圖標亮了—一提交。

  觀眾席上又是一陣騷動。

  「階段二也交了?這麼快?」

  「張揚隊階段二開始還沒有多久。」

  幾秒鐘後,圖標變綠。

  通過。

  用時:五十分鐘。

  李虎興奮得差點從椅子上跳起來,被陳龍按住了。

  「別激動。」陳龍說,「還有階段三。」

  林東看了一眼大屏幕上的時間。

  倒計時還剩一小時二十五分鐘。張揚隊階段一剛通過,用時六十五分鐘。

  四大天王總用時一個小時三十五分鐘,比張揚隊快了將近二十分鐘。

  但階段三才是最難的部分。

  詞頻動態調整。

  用戶的使用習慣實時影響候選詞排序。常規做法是用LRU或LFU算法,維護一個詞頻表,每次輸入後更新權重。

  但0.5MB的內存,存不了多少數據。10萬詞條,每個詞條存一個整數詞頻,就是40萬字節,差不多0.4MB。再加LRU的雙向鍊表,肯定超。

  林東有另一個辦法。

  他第二輪結束後研究過這個算法—一—近似計數算法。

  固定大小的二維數組,不存具體詞頻,只存近似值。內存占用固定0.3MB,響應時間0(1)。

  當時不是為決賽準備的,只是覺得「以後可能用得上」,順手寫了一個demo

  。沒想到今天真用上了。

  他打開編輯器,開始寫。

  算法不複雜。

  一個二維數組,d行,w列。每個輸入進來,哈希到某一行某一列,計數加一。查詢的時候,取該位置的最小值作為近似計數。誤差可控,內存固定。

  他寫得很快。每一個變量,每一個函數,每一行代碼,都在他腦子裡過了無數遍。

  李虎湊過來看了一眼,看了半天,問了一句:「你這個算法,跟第二輪那道題有點像?」

  林東沒抬頭:「嗯。」

  李虎撓了撓頭,沒再問了。

  他想起自己第二輪結束後重寫那道題的時候,林東站在他後面看了一眼。當時他以為林東只是隨便看看。

  現在他知道了,林東他把那個數據結構的精髓全看懂了,還用到了這裡。

  陳龍也湊過來看了一眼,看了幾秒,推了推眼鏡:「這個算法,你什麼時候寫的?」

  「之前。」林東說。

  陳龍沒再問了。

  二十多分鐘後,林東停下手指。

  「寫完了。」他說。

  「檢查了嗎?」陳龍問。

  林東沒回答,自己看了一遍。

  哈希函數沒問題,數組邊界沒問題,近似計數的誤差在可接受範圍內。

  內存占用—一他算了一下,0.3MB。加上階段一的0.58MB,階段二的0.4MB,總共1.28MB,遠低於2MB的限制。

  他按下「編譯」——通過。再按下「運行」——測試用例全部通過。響應時間——7ms。

  他深吸一口氣,按下「提交」。

  大屏幕上,四大天王隊的圖標亮了—一提交。

  觀眾席上安靜下來。所有人都在盯著那個圖標。

  幾秒鐘後圖標變綠。

  通過。

  用時:四十分鐘。

  李虎愣了一秒,然後一把抱住旁邊的陳龍:「通過了!三階段全過了!」

  陳龍被他勒得喘不過氣,但沒掙開。

  許藏睜開眼睛,看了一眼大屏幕,嘴角彎了一下。

  林東靠在椅背上,長出一口氣。

  總用時:四十五分鐘加五十分鐘加四十分鐘,一百三十五分鐘。二個小時十五分鐘。


  他看了一眼張揚隊那邊的進度。階段三,還在寫。

  又過了將近四十分鐘,張揚隊提交。

  通過。

  但總用時已經比四大天王多了將近四十分鐘。

  林東收回目光。

  張揚隊輸了。

  因為他們的路數不對。LRU是常規最優解,但在這個場景下,內存不夠用。他用的近似計數算法,是降維打擊。

  而這條路的起點,是第二輪結束後那天晚上,李虎在宿舍里重寫代碼的時候,他站在後面看了一眼。

  當時他沒多想,只是覺得「這個數據結構可以再優化一下」。然後他順手研究了一下,寫了一個demo。

  沒想到今天用上了。

  他看了李虎一眼。

  李虎還在興奮,和陳龍說著什麼,臉上笑得像個傻子。

  他不知道林東用了他的思路,也不知道林東因為他的習慣,提前準備好了階段三的算法。

  他只是想把自己的代碼寫得更好一點。

  林東收回目光,嘴角動了一下。

  有時候就是這樣,不知道自己做了什麼,但你做的每一件事,都在為未來鋪路。

  大屏幕上,最終排名出來了。

  第一名:四大天王。三階段全通過。總用時:一百三十五分鐘。代碼質量:

  S。

  第二名:張揚隊。三階段全通過。總用時:一百七十五分鐘。代碼質量:

  B+。

  第三名:極客聯盟隊。兩階段通過。

  其餘隊伍:一階段或以下。

  觀眾席上炸開了鍋。

  「一百三十五分鐘?不到二個半小時?」

  「張揚隊用了一百七十五分鐘,差了將近四十分鐘!」

  「四大天王太猛了吧?」

  「那個4號位林東,第三階段一個人寫的,四十分鐘就過了。」

  「真的假的?張揚寫了四十多分鐘都沒過。」

  「張揚最後也過了,但時間差太多了。」

  周琳從座位上跳起來,尖叫出聲。趙雨也站起來,拍著手。陳露沒站起來,但她的手鬆開了包帶,嘴角彎著,眼睛亮亮的。

  李虎還在座位上坐著,盯著大屏幕上的「第一名」三個字,愣了好幾秒。然後他站起來,轉過身,對著觀眾席舉起雙手,比了兩個大拇指。

  觀眾席上響起一片笑聲和掌聲。

  陳龍推了推眼鏡,嘴角彎了一下。許藏靠在椅背上,閉著眼睛,但嘴角也彎著。

  林東坐在最邊上,看著他們三個。

  贏定了。

章節目錄