王争,西安交通大学 计算机专业
本科毕业时候编程水平其实是很差的。读研究生看《算法导论》。从此我对算法的“迷恋”便一发不可收拾。之后,我如把图书馆里几乎所有数据结构和算法书籍都读了一遍。
我边读边练。没多久我就发现,写代码时会不由自主考虑很多性能方面的问题。我写出时间复杂度高、空间复杂度高的垃圾代码越来越少了,算法能力提升了很多,编程能力也有了质的飞跃。
得益于此,研究生毕业,我直接进入Google,从事Google翻译相关的开发工作。
工作十年间,我见过许多程序员,有着各种各样的背景,有很多既有潜力又非常努力,但始终无法在自己现有水平上更进一步。
在技术圈里,我们经常喜欢谈论高大上的架构,比如高可用、微服务、服务治理等等。鲜有人关注代码层面的编程能力,而愿意沉下心来,花几个月时间啃一啃计算机基础知识、认认真真夯实基础的人,简直就是凤毛麟角。
一位原来腾讯T4的技术大牛。区块链大潮之前在腾讯工作了10多年,长期负责手机QQ后台整体建设,经历了手机QQ从诞生到亿级用户在线的整个过程。后来他去了微众银行做区块链。他用了不到半年时间,就把区块链的整个技术脉络摸清楚了。 现在,他是微众银行的区块链负责人,微众科技创新产品部的老总。
为什么他可以做到花半年时间就能精通一个新的领域?
其中最重要的就是基础足够扎实。像区块链、人工智能这些看似很新的技术,其实一点儿都不“新”。最初学编程的时候,他就把那些基础的知识都学透了。当面临行业变动、新技术更迭的时候,他不断发现,那些所谓的新技术,核心和本质的东西其实就是基础知识。掌握了这个“规律”之后,他学任何东西都很快,任何新技术都能快速迎头赶上。这就是快速学习并且获得成功的秘诀。
基础知识就像是一座大楼的地基,它决定了我们的技术高度。而要想快速做出点事情,前提条件一定是基础能力过硬,“内功”要到位。
技术人究竟都需要修炼哪些“内功”呢?
无外乎就是大学里的那些基础课程,操作系统、计算机网络、编译原理,数据结构和算法。
像《算法导论》这些经典书籍,虽然很全面,但是过于理论,学起来非常枯燥;而市面很多课程大多缺失真实的开发场景,费劲学完感觉好像还是用不上,过不了几天就忘了。
那怎样解决这个问题呢?
我把专栏分成四个递进的模块。
- 入门篇
时间、空间复杂度分析是数据结构和算法中非常重要的知识点,贯穿整个专栏的学习过程。但同时也是比较难掌握的,所以我用了2节课来讲这部分内容,而且还举了大量的实例,让你一边学一边练,真正能掌握复杂度分析,为后面的学习铺路。
我希望通过这一模块,你能掌握时间、空间复杂度的概念,大O表示法的由来,各种复杂度分析技巧,以及最好、最坏、平均、均摊复杂度分析方法。之后,面对任何代码的复杂度分析,你都能游刃有余、毫不畏惧!
- 基础篇
这部分是专栏中篇幅最大的内容,也是我们学习的重点,共有26节内容,涵盖了最基础、最常用的数据结构和算法。针对每种数据结构和算法,我都会结合具体的软件开发实例,由浅入深进行讲解,并适时总结一些实用“宝典”,保证你印象深刻、学有所用。
比如递归这一节,我会讲到,为什么递归代码比较难写?如何避免堆栈溢出?如何避免递归冗余计算?如何将递归代码转化为非递归代码?
-
高级篇
这部分我会讲一些不是那么常用的数据结构和算法。虽然不常用,但是这些内容你也需要知道。设置这一部分的目的,是为了让你开拓视野,强化训练算法思维、逻辑思维。如果说学完基础部分可以考80分,那掌握这一部分就能让你成为尖子生! -
实战篇
我们整个专栏都是围绕数据结构和算法在具体软件实践中的应用来讲的,所以最后我会通过实战部分串讲一下前面讲到的数据结构和算法。我会拿一些开源项目、框架或者系统设计问题,剖析它们背后的数据结构和算法,让你有一个更加直观的感受。
跨过去,你就可以成长,跨不过去就是困难和停滞。而在后面很长的一段时间里,你都需要为这个困难买单。
入门篇
01 为什么要学数据结构与算法?
我们学任何知识都是为了“用”的,是为了解决实际工作问题的,学习数据结构和算法自然也不例外。
你真地愿意写一辈子CRUD吗?
- 如果不知道已经封装好的接口、类库背后的原理,不懂得时间、空间复杂度分析,你如何能用好、用对它们?
- 存储某个业务数据的时候,你如何知道应该用ArrayList,还是Linked List呢?
- 调用了某个函数之后,你又该如何评估代码的性能和资源的消耗呢?
我们会用到各种框架、中间件和底层系统,比如Spring、RPC框架、消息中间件、Redis等等。在这些基础框架中,都揉和了很多基础数据结构和算法的设计思想。
Redis中,有序集合是用什么数据结构来实现的呢?为什么要用跳表来实现呢?不用二叉树呢?
如果你能弄明白这些底层原理,你就能更好地使用它们。即便出现问题,也很容易就能定位。因此,掌握数据结构和算法,不管对于阅读框架源码,还是理解其背后的设计思想,都是非常有用的。
平时的工作中,数据结构和算法的应用到处可见。我来举一个你非常熟悉的例子:如何实时地统计业务接口的99%响应时间?
你可能最先想到,每次查询时,从小到大排序所有的响应时间,如果总共有1200个数据,那第1188个数据就是99%的响应时间。很显然,每次用这个方法查询的话都要排序,效率是非常低的。但是,如果你知道“堆”这个数据结构,用两个堆可以非常高效地解决这个问题。
基础架构研发工程师,写出开源水平的框架才是你的目标!
现在互联网上的技术文章、架构分享、开源项目满天飞,照猫画虎做一套基础框架并不难。
拿RPC框架举例。不同的公司、不同的人做出的RPC框架,架构设计思路都差不多,最后实现的功能也都差不多。但有的人做出来的框架,Bug很多、性能一般、扩展性也不好,只能在自己公司仅有的几个项目里面用一下。有的人做的框架可以开源到GitHub上给很多人用,甚至被Apache收录。
为什么会有这么大的差距呢?
高手之间的竞争其实就在细节:你用的算法是不是够优化?数据存取的效率是不是够高?内存是不是够节省?
对编程有追求?不想被行业淘汰?不要只会写凑合能用的代码!
什么是编程能力强?
代码的可读性好、健壮?还是扩展性好?
性能好坏起码是其中一个非常重要的评判标准。如果你连代码的时间复杂度、空间复杂度都不知道怎么分析,怎么写出高性能的代码呢?
如何不被行业淘汰?
程序员35岁之后很容易陷入瓶颈,被行业淘汰;
有的人写代码的时候,从来都不考虑非功能性的需求,只是完成功能,凑合能用就好;
做事情的时候,也从来没有长远规划,只把眼前事情做好就满足;‘
我面试过很多大龄候选人,简历能写十几页,经历的项目有几十个,但是看下来,每个项目都是重复地堆砌业务逻辑而已,完全没有难度递进,看不出有能力提升。久而久之,十年的积累可能跟一年的积累没有任何区别。这样的人,怎么不会被行业淘汰呢?
如果你在一家成熟的公司,面对的是千万级甚至亿级的用户,开发的是TB、PB级别数据的处理系统。性能几乎是开发过程中时刻都要考虑的问题。一个简单的ArrayList、Linked List的选择问题,就可能会产生成千上万倍的性能差别。这个时候,数据结构和算法的意义就完全凸显出来了。
数据结构和算法这个东西,如果不去学可能真的这辈子都用不到,也感受不到它的好。但是一旦掌握,你就会常常被它的强大威力所折服。你可能需要费很大劲儿来优化的代码,需要花很多心思来设计的架构,用了数据结构和算法之后,很容易就可以解决了。
学习数据结构和算法,目的是建立时间复杂度、空间复杂度意识,写出高质量的代码,能够设计基础架构,提升编程技能,训练逻辑思维。
所以,不管你是业务开发工程师,还是基础架构工程师;不管你是初入职场的初级工程师,还是工作多年的资深架构师,又或者是想转人工智能、区块链这些热门领域的程序员,数据结构与算法作为计算机的基础知识、核心知识,都是必须要掌握的。
掌握了数据结构与算法,你看待问题的深度,解决问题的角度就会完全不一样。因为这样的你,就像是站在巨人的肩膀上,拿着生存利器行走世界。数据结构与算法,会为你的编程之路,甚至人生之路打开一扇通往新世界的大门。
02 如何抓住学习的重点
什么是数据结构?什么是算法?
广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。数据结构是为算法服务的,算法要作用在特定的数据结构之上。
我们要讲的是某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。我们要讲的这些经典数据结构和算法,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,可以高效地帮助我们解决很多实际的开发问题。
学习的重点在什么地方?
要学习数据结构与算法,首先要掌握一个数据结构与算法中最重要的概念——复杂度分析,几乎占了数据结构和算法这门课的半壁江山,是数据结构和算法学习的精髓。
什么是复杂度分析?
数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,复杂度分析方法就是考量效率和资源消耗的方法,是心法!
作为一个非算法工程师来说,你并不需要掌握图里面的所有知识点。
要学习要学会找重点,20个最常用的、最基础数据结构与算法:
- 10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树;
- 10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
学习数据结构和算法的过程中,你也要注意,不要只是死记硬背,不要为了学习而学习,而是**要学习它的
- “来历”
- “自身的特点”
- “适合解决的问题”
- “实际的应用场景”
只要你掌握了我每节课里讲的内容,就能在开发中灵活应用。学习数据结构和算法的过程,是非常好的思维训练的过程,
千万不要被动地记忆,要多辩证地思考,多问为什么。如果你一直这么坚持做,你会发现,等你学完之后,写代码的时候就会不由自主地考虑到很多性能方面的事情,时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。你的编程内功就真正得到了修炼。
你要做的:
1、边学边练,适度刷题
建议你花1~2个小时的时间,集中把这周的三节内容涉及的数据结构和算法,全都自己写出来,用代码实现一遍。
要大量刷题吗?
可以“适度”刷题,但一定不要浪费太多时间在刷题上。学习的目的还是掌握,然后应用。先从掌握这个专栏的内容开始。
除非面试Google、Facebook这样的公司,算法题目非常难,必须大量刷题,才能在短期内提升应试正确率。
2、多问、多思考、多互动
学习最好的方法,找到几个人一起学习,一块儿讨论切磋,有问题及时提问。
3、打怪升级学习法
学习的过程中,我们碰到最大的问题就是,坚持不下来。在枯燥的学习过程中,也可以给自己设立一个切实可行的目标,就像打怪升级一样。
针对这个专栏,你就可以设立这样一个目标:
每节课后的思考题都认真思考,并且回复到留言区。当你看到很多人给你点赞之后,你就会为了每次都能发一个漂亮的留言,而更加认真地学习。
比如,每节课后都写一篇学习笔记或者学习心得;或者你还可以每节课都找一下我讲得不对、不合理的地方……诸如此类,你可以总结一个适合你的“打怪升级攻略”。
4、知识需要沉淀,不要想试图一下子掌握所有
想听一遍、看一遍就把所有知识掌握,这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。要尊重学习的规律。