• 欢迎访问天天编码网站,Java技术、技术书单、开发工具,欢迎加入天天编码
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏天天编码吧
  • 我们的淘宝店铺已经开张了哦,传送门:https://shop145764801.taobao.com/

Google工程师巩朋的算法之路(3)

算法书单 tiantian 1632次浏览 0个评论 扫描二维码

应用

说老实话,自从本科实习之后,我就一直觉得算法除了面试时能用用,其它基本用不上,甚至还写了一篇当时颇为自得现在读起来极为傻逼的文章来黑那些动不动就”基础”或”内功”的所谓”大牛”们,这里摘取一段现在看起来很傻逼但当时却觉得是真理的文字:

所以那些动则就扯什么算法啊基础啊内功啊所谓的大牛们,请闭上你的嘴,条条大道通罗马。算法并不是编程的前提条件,数学也不会阻碍一个人成为优秀的程序员。至少在我看来,什么算法基础内功都是唬人的玩意,多编点能用的实用的程序才是王道,当然如果你是一个pure theorist的话就当我什么都没说好了。—巩朋

然而有意思的是,写了这篇 文章 没多久,鼓吹算法无用论的我自己做的几个大大小小的项目全部用到了算法——我疑心是上天在有意抽我的脸。

LL(k)

我在微软实习的第一个项目做的是 代码覆盖率分析——计算 T-SQL 存储过程的代码覆盖率。

简单的看了下 SQL Server 相关的文档,我很快发现 SQL Reporting Service 可以记录 T-SQL 的执行语句及行号,于是行覆盖(line coverage)搞定,但老大说行覆盖太 naive,我们需要更实际的块覆盖(block coverage)。

阅读了块覆盖的定义后,我发现我需要 对T-SQL 进行语法分析,在没有找到一个好用的 T-SQL Parser 的情况下,只能自己动手搞一个:

1《Language Implementation Patterns》

比较奇诡的是,做这个项目时当时我刚好把 ANTLR 作者的 《Language Implementation Patterns》(中译本:《编程语言实现模式》)看了一半,什么 LL(k) 啊 Packrat 啊 AST Walker 的概念啊正热乎着呢。

Google工程师巩朋的算法之路(3)

  • 豆瓣评分: 8.6
  • 购买链接: 京东
  • 推荐指数: 五颗星

于是,自己自己就照着 T-SQL 的官方 EBNF,三下五除二搞了一个 T-SQL 存储过程的 LL(k) Parser,把代码转换成 AST,然后用一个 External AST Walker 生成代码块覆盖的 HTML 报表,全部过程一周不到。

老大自然是很满意——我疑心他的原计划是花两三个月来完成这个项目,因为这个项目之后的两个月我都没什么活干,天天悠哉游哉。

拼音索引

拼音索引是我接的一个手机应用私活里的小模块,用户期待在手机文本框可以根据输入给出智能提示,就是类似百度搜索框那种。

中文匹配这个简单,但拼音匹配就得花时间想想了——懒得造轮子的我第一时间找到了微软的拼音库,但接下来我就发现微软这个鸟库在手机上跑不动,研究了下发现 WP7 对 Dictionary 的 items 数量有限制,貌似是 7000 还是 8000 个 item就会崩盘,而标准汉字则有两万多个,尼玛。

痛骂MS坑爹+汉字坑爹之余,还是得自己撸一个库出来:

  1. 首先把那两万个汉字搞了出来,排序,然后弄成一个超长的字符串。
  2. 接下来用 Int16 索引了汉字所有的拼音(貌似500多个)。
  3. 再接下来用 Int64 建立汉字和拼音的关联——汉字有多音字,所以需要把多个拼音 pack 到一个 Int64 里,这个简单,位操作就搞定。
  4. 最后用二分+位移 Unpack,直接做到从汉字到拼音的检索。
  5. 后来小测了下性能,速度是 MS 原来那个库的五十倍有余,而代码量只有 336 行。

用户很 happy——因为我捎带把他没想到的多音字都搞定了,而且流畅的一逼。

我也很 happy,因为没想到自己写的库居然比 MS 的还要快几十倍,同时小十几倍。

从这个事情之后我变得特别理解那些造轮子的人——你要想想,如果你需要一个飞机轮子但市场上只有自行车轮子而且老板还催着你交工,你能怎么搞。

快速字符串匹配

前面提到在微软实习时老大扔给我一个 Windows Phone 让我研究下,我当时玩了玩就觉着不太对劲,找联系人太麻烦。

比如说找”张晓明”,WP 只支持定位到Z分类下——这意味着我需要在 Z 分类下的七十多个联系人(姓张的姓赵的姓钟的等等)里面线性寻找,每次我都需要滑动四五秒才能找到这个张姓少年。

这也太傻逼了,本屌三年前的老破NOKIA都支持首字母定位,996->ZXM->张晓明,直接搞定,尼玛一个新时代 Windows Phone 居然会弱到这个程度。

搜了一下发现没有好用的拨号程序,于是本屌就直接撸了一个支持首字母匹配的拨号程序出来扔到WP论坛里。

结果马上就有各种问题出现——最主要的反映是速度太慢,一些用户甚至反馈按键有时要半秒才有反应。本屌问了下他的通讯录大小:大概 3000 多人。

吐槽怎么会有这么奇葩的通讯录之余,我意识到自己的字符串匹配算法存在严重的性能问题:读取所有人的姓名计算出拼音,然后一个个的匹配——结果如果联系人数量太多的话,速度必然拙计。

于是我就开始苦思冥想有没有一个能够同时搜索多个字符串的高端算法,以至于那两天坐地铁都在嘟囔怎么才能把这个应用搞的快一些。

2《Algorithms on Strings, Trees and Sequences》

最终还是在 《Algorithms on Strings, Trees and Sequences》 里找到了答案——确实有能够同时搜索多个字符串的方法:Tries,而且这本书还用足足一章来讲怎么弄 Multiple string comparison,看得我当时高潮迭起,直呼过瘾。

  • 豆瓣评分: 9.1
  • 购买链接: 京东
  • 推荐指数: 五颗星

具体细节不多说,总之换了算法之后,匹配速度快了大约九十多倍,而且代码还短了几十行。哪怕是有 10000 个联系人,也能在 0.1 秒内搞定,速度瓶颈就这样愉快的被算法搞定。

3《Writing Efficient Programs》

之后又做了若干个项目,多多少少都用到了”自制”的算法或数据结构,最奇诡的一次是写一个电子书阅读器里的分页,我照着模拟退火(Simulated Annealing)的原理写了一个快速分页算法,事实上这个算法确实很快——但问题是我都不知道为啥它会这么快。

总之,算法是一种将有限计算资源发挥到极致的武器,当计算资源很富余时算法确实没大用,但一旦到了效率瓶颈算法绝壁是开山第一刀(因为算法不要钱嘛!要不还得换 CPU 买 SSD 升级 RAM,肉疼啊!!)。一些人会认为这种说法是有问题,因为编写新算法的人力成本有时比增加硬件的成本还要高——但别忘了增加硬件提升效率也是建立在算法是 Scalable的基础上——说白了还是得搞算法。

说到优化这里顺带提一下 《Writing Efficient Programs》——很难找到一本讲代码优化的书(我疑心是自从 Knuth 说了 过早优化是万恶之源 之后没人敢写,万恶之源嘛,写它干毛),注意这本书讲的是代码优化——在不改变架构、算法以及硬件的前提之下进行的优化。尽管书中的一些诸如变量复用或是循环展开的 trick 已经过时,但总体仍不失为一本好书。


天天编码 , 版权所有丨本文标题:Google工程师巩朋的算法之路(3)
转载请保留页面地址:http://www.tiantianbianma.com/msra-gong-peng-algorithm-three.html/
喜欢 (4)
支付宝[多谢打赏]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址