下载客户端
下载客户端
关于我们 寻求报道 加入我们
weizhizao 2016-4-02 09:35

学习算法,到底有什么用

编者:朱赟, 硅谷女博士,毕业于科大少年班和美国莱斯大学,Square第一个中国女工程师,现在 Airbnb 任职。本文首发于微信公众号 “嘀嗒嘀嗒”,原标题为 “闲话算法”,已获得作者同意转载。

微信公众号后台对用户属性有根据性别、语言、省份、机型等分布进行统计。但是没有对年龄的统计。

但是我琢磨我的读者里还是有不少一票是还在读大学的或者刚毕业的,因为每次总有几个留言,很亲热的叫姐,“姐,你咋又把文章删啦?” “姐,我支持你。” “姐,你咋还没睡啊。” ……

有一个问题,倒是有好几个人问到类似的:

“ 姐姐,希望有机会能讲解下算法在工作中的运用和你和你个人学习算法的过程,因为我对算法还是有点怕。除此之外,您认为大学是应该多花时间学应用还是理论知识,设计架构等思维模式等呢?谢谢。”

老实说,被叫姐叫多了,就错觉自己真的成了姐了。所以端着 “姐” 的架子闲扯几句吧~

很久前在朋友圈看到一段文字,原文不记得了。但是意思是说:当一个人回过头来写自己的经历,尤其是站在有点小小成功的高度往回看,特别容易神话自己,摆出一副俯瞰故土苍生的自恋和得意。因着读到这句话,虽然可能自己不能完全做到免俗,却尽量每次下笔前一再提醒自己:老老实实写就好,不要为了美化自己而增增减减。

HNCK4023

(插图来自:imgix

最近各种公众号,各种社群,搞的风风火火,谈系统设计和架构的偏多。却没有太多分享算法的。是因为算法不重要么?恰恰相反,而是因为算法太重要太基础,以至于你会算法,这事都没啥好说好分享的了。除非你是搞出了什么新的特别牛的算法(更多是学术界),否则你去给谁分享?抓个合格的程序员别的不会,算法总是会的。何况这门技术已经成了经典,不用看什么公众号文章,就看《算法导论》就行了。

我不知道大家怎么开始一步步精通算法和数据结构的。老实说,大二还是大三第一次接触《数据结构》这门课,因为是从来没有过的思维训练,其实当时也是学的比较费力的。那时候编程接触的还比较少,所以并没有很多实际的体验去让我欣赏和体味一个好的数据结构或算法设计的 “美” 在哪里。甚至有点死记硬背的感觉,并不知道为什么 “如果不这样设计” 会在实际中出哪些问题。各种大O小o的时间空间复杂度当时对我而言也仅仅是一些不能融入到实际问题的一些数学游戏。你就说各种排序,每种最坏情况和平均情况的时间空间复杂度,为什么那么重要?可能因为考试要考吧。

boss-fight-free-high-quality-stock-images-photos-photography-macbook-pro-code

(插图来自:bossfight

然而我算幸运的。算法这门课我大学上一遍,读博士上一遍,后来 Rice 因为每个研究生要无偿当五个学期的助教(可能是因为 Rice 奖学金给太高了吧),而我又好巧不巧的被算法老师两次挑中当助教。所以一本《算法导论》前前后后这样被逼着细学了不下四次。不是开玩笑,全本书的习题可能大部分都做过,有些还不止做了一遍。所以要说我学习算法的过程,几乎不能推荐给任何人用。

那么学习算法到底有些什么用处呢?

首先就是面试

国内我不太清楚,硅谷的 IT 公司除了电话面试是偏算法的,onsite 面试至少有两轮都是考算法和编程的。大一些老一些的公司,像 Google,Facebook,LinkedIn,Dropbox 等,都是白板写程序。而新一些的小一些的公司,如 Square,Airbnb 等,都是需要现场上机写出可运行的程序的。

Twitter,Uber 等则是白板上机兼备,看情况。虽然说还有其它考系统设计等的部分,但是如果算法没有打好基础,这关就很难过。而且算法要熟悉到能够现场短时间内写出正解,其实很多人准备面试前都是需要刷题的(也有特例)。

nasm_ttedig_nd15_iyb_interview_1208x808

(插图来自:nasm

记得我一年多前,有一次当面试官,电话面试另外一个人,当时是用 codepad 共享需要对方写出可运行的一个 regular expression 的 parser(职业操守,其实并没有这道题,只是类似举例)。45 分钟过去了,对方并没有写出来。我就例行公事地问:“你还有什么问题想问或者想了解么?” 然后对方估计因为写不出来程序很有挫败感,就说:“ 你们平时工作难道就是天天写 regular expression 的 parser?么?” 我竟然无言以对。想了想,我回复说:“ 不用天天写。那我再给你 15 分钟,你证明给我看你还会什么,或者什么理由我应该给你进一步面试的机会?” 对方想了一会,默默挂掉了电话。

老实说我对目前面试中对算法的侧重程度是持保留意见的。算法题答得好,其实并不说明你很牛。而牛人,也有因为不愿刷题而马失前蹄的时候。然而怎样才能最优化面试流程,这也是个扯起来没完的话题,并且每次讨论必定无果而终。

写程序用到的更多的是算法的思想,不是写具体的算法

说到实际工作中需要真的用到写一个算法的机会,让我往回想一想……可能应该在接近 10% 的附近游走。可能有些朋友做的工作会遇到略多些。更多的时候,是对业务逻辑的理解,程序语言的各种特性的熟练,代码 style、pattern 的把握,各种同步异步的处理,代码测试、部署的正规化等等。需要设计甚至实现一个算法的机会确实很少,即使用到,现学可能都来得及。

而对基本算法的了解的好处可能在于:工作中需要读一段代码包含一些基本算法的思想,你会更快对其理解;读到一段烂代码,你知道为什么烂,怎么优化;当真的需要有一些算法设计在程序里面的时候,对基本算法的掌握会让你更有可能给出一个完备的方案;对每种程序中出现的算法或比较复杂的逻辑的时间复杂度等你会更有敏感性;熟悉算法你还可以成为一个更优秀的面试官;还可以和别的码工聊天的时候不被鄙视…… 就酱!

不精通算法的工程师永远不会是一个好的工程师

当然,除了算法导论中那些已成为经典的基本算法以及算法思想(Divide-and-conquer,Dynamic programming)等,其实我们每天接触到的各种技术中,算法其实是无处不在的。

leveldb

(插图来自:wzxue

就拿人人都会接触的 Storage 的例子吧。各种不同的 DB 或者 KV store 的实现,就可能涉及到各种 sharding 算法、各种 cache invalidation 算法、各种 locking 算法、以至于各种容错算法(多 copy 间的同步算法)…… 虽然说平时不太会去写这些算法(除非你恰恰是做 storage 实现的),但是做到真正了解这个技术是用了什么算法,实现的细节是怎样的,其实无论对于技术选型还是对自己程序的整体性能的评估都是至关重要的。

举个例子,当你在系统里需要一个 KV store 的方案的时候,面对可供选择的各种备选方案,你到底应该选择哪一种呢?

永远没有一种方案在所有方面都是最佳的。就拿 Facebook opensource 的 RocksDB 来说吧。了解它的历史的都知道,RocksDB 是构建在 LevelDB 之上的可以在多 CPU server 上高效运行的一种 KV store。而 LevelDB 又是基于 Google 的 BigTable 数据库系统的概念设计的。早在 2004 年,Google 开始开发 BigTable,其代码大量的依赖与 Google 内部的代码库,虽然 BigTable 很牛逼,却因此无法开源。

12367

(插图来自:S3 bench

2011 年,Google fellow Jeff Dean 和 Sanjay Ghemawat 开始按照 BigTable 的思想,重新开发一个开源的类似的系统,并保证做到不用任何 Google 的代码库,于是有了 LevelDB。这样一个 KV store 的实现也用于 Chrome 的 indexedDB 的实现中,对于 Google Chrome 的开源也提供了一定的支持。

而我在文章中多次提到的 CockroachDB,其实又可以看作是基于 RocksDB 之上的一个分布式实现。虽然,从另一个层面上讲,CockroachDB 也可以说是 Spanner 的一个开源实现。知道这些,就知道这些 DB / KV Store 其实都同出一系,再来看看 LevelDB 底层的 SSTable 算法,就知道他们都是针对 high throughput, sequential read/write workloads 会很有效的存储系统了。

当然,一个系统里除了最基本的算法,还有很多很多的实现细节和系统架构对性能以及应用的影响都很大。然而,对算法本身的理解和把握,永远是深入了解系统不可或缺的一环。

Uber-taxi-nyc-

(插图来自:appinformers

类似的例子还有很多很多,如日志分析、打车软件的调度算法等等。

再拿我比较熟悉的支付来说吧,比如信用卡 bin data 的压缩,从 server 传到 app 的过程,为了传给手机 app 的数据比较小,需要做编码,每个国家比如中国,韩国,墨西哥信用卡前缀格式都不一样,如何尽量压缩同时不要太复杂影响手机 app 代码的复杂度造成 bug 等,也需要对各种相关算法有着详尽地了解,才有可能做出最优的方案。

题图来自:电影《TRANSFORMERS》

有好的产品或者项目希望我们报道,猛戳这里 寻求报道

文章评论(-)
后参与讨论
正在加载中

HDR电视有规可依,TCL QUHD TV引领画质革新风潮 | 品牌

2016-4-02 17:18下一篇

让人面红耳赤的杜蕾斯,这次又准备带我们怎么啪啪啪?

2016-3-28 14:02上一篇