第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號位林东，第三阶段一个人写的，四十分钟就过了。”
“真的假的？张扬写了四十多分钟都没过。”
“张扬最后也过了，但时间差太多了。”
周琳从座位上跳起来，尖叫出声。赵雨也站起来，拍著手。陈露没站起来，但她的手鬆开了包带，嘴角弯著，眼睛亮亮的。
李虎还在座位上坐著，盯著大屏幕上的“第一名”三个字，愣了好几秒。然后他站起来，转过身，对著观眾席举起双手，比了两个大拇指。
观眾席上响起一片笑声和掌声。
陈龙推了推眼镜，嘴角弯了一下。许藏靠在椅背上，闭著眼睛，但嘴角也弯著。
林东坐在最边上，看著他们三个。
贏定了。
热烈掌声响起来。
观眾席上大部分人都在盯著大屏幕，等著看规则。
大屏幕亮了。
团队现场编程。限时三小时。共一道大题，分三个阶段递进。
题目：设计一套中文输入法引擎。
林东看到这行字的时候，手指在键盘上停了一下。
输入法。
屏幕、电池、主板、外壳、触控算法、天线、驱动一全都齐了，唯独输入法还用的是开源的方案，体验一般，適配也麻烦。
他本来打算年后做一套，现在好了，决赛题目就是输入法。
他嘴角动了一下。
做完直接拿走。
阶段一（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號位林东，第三阶段一个人写的，四十分钟就过了。”
“真的假的？张扬写了四十多分钟都没过。”
“张扬最后也过了，但时间差太多了。”
周琳从座位上跳起来，尖叫出声。赵雨也站起来，拍著手。陈露没站起来，但她的手鬆开了包带，嘴角弯著，眼睛亮亮的。
李虎还在座位上坐著，盯著大屏幕上的“第一名”三个字，愣了好几秒。然后他站起来，转过身，对著观眾席举起双手，比了两个大拇指。
观眾席上响起一片笑声和掌声。
陈龙推了推眼镜，嘴角弯了一下。许藏靠在椅背上，闭著眼睛，但嘴角也弯著。
林东坐在最边上，看著他们三个。
贏定了。