HICSC
性能优化:如何学习数据结构与算法

数据结构与算法可能是为数不多的所有人都认为非常重要,但又很少花时间去做功课的知识之一。其中很重要的原因是常用的数据结构和算法都有现成的框架或者类库,只要用得熟练,照样可以把代码写得飞起。就拿排序来说,JDK中的Collections.sort方法在数据量小的时候使用插入排序,而数据量大的时候使用归并排序,细节问题根本就不需要开发者担心。

渐渐地,我们就很少再去思考这些类库和框架背后的原理?也就很少去思考自己用的算法是不是最优的、数据存取效率是不是最高的、内存是不是最节省的?更不会去总结每种数据结构和相应算法的自身特点以及应用场景。

但这是不对的,想要写出高性能代码,数据结构与算法可以说是最重要也最基础的技能。单从技术层面来说,没有之一,就是最重要的。至少在我个人看来,比我前面所总结的任何技术层面的知识都要重要,从务虚的层面来说:

从务实层面来说,想要写出高性能代码,至少得学会如何分析代码的时间复杂度和空间复杂度吧;至少得知道基础的数据结构应该如何选择吧。这些都是学习数据结构和算法的意义所在。

如何高效的学习数据结构与算法

不知道你小时候是如何学习加减乘除的,但我是靠背诵来学习的。像十以内的加减法、九九乘法表之类的东西得背的滚瓜烂熟,为什么要背,因为那些都是最基础的内容。

其实,学习数据结构与算法也是一样的,对于最常用、最基础的数据结构与算法,如果你不会,那就得把它背下来。

但只是背下来肯定不行,还得经常去用。就像我背完九九乘法表以后,马上就会去学习两位数的加减乘除,这些都是以已学习的内容为基础的,慢慢地,基础内容自然而然的就印在脑海中了。

学习数据结构和算法也是一样的,不仅要学,还要会用。但在学习之前,首先得明确学习的范围,毕竟数据结构与算法有那么多,不可能把所有的都学完?

极客时间上 数据结构与算法之美 专栏的作者王争,结合自己的心得与多年的面试和开发经验,总结了20个最常用也最基础的数据结构和算法:

掌握了这些基础的数据结构和算法以后,再学更加复杂的数据结构和算法,就会非常容易、非常快。

如何学习?

前面也说到,这些基础的数据结构与算法,如果你不会,那就需要背下来。但这里并不是鼓励死记硬背。而是通过学习去记忆、去理解,我们要学习它们的来历、自身特点、适合解决的问题、实际的应用场景。

而且在学习过程中,更多的还要去辩证的思考,多问问为什么。就拿数组来说,我们都知道在指定位置插入数组或者删除数组的效率很低,因为在插入和删除过程中需要移动数组元素的位置。

但有没有更好的方法来插入和删除数组元素,让时间复杂度降到O(1)。如果数组元素不需要顺序的话,其实是有的,比如有一个数组a,如果要把元素 x 插入到第 3 个位置,只需要将 c 放入到 a[5],将 a[2] 赋值为 x 即可,具体的示意图如下所示。

向数组插入元素

这是一个非常好的思维训练过程,只要经常这样练习,一段时间过后,写代码的时候就会不用自主地考虑更多性能方面的事情,时间复杂度和空间复杂度高的代码出现的次数就会越来越少。

其他的学习方法,都已经被大家说烂了,比如:

最后,就是要耐心。学习本不是一个一蹴而就的过程,而是一个反复迭代,不断累积的过程。特别是数据结构与算法这样的基础知识,其对人产生的影响不会立竿见影,就更需要我们耐心。

如何应用?

在学习过程中,想要检验我们是否掌握某种数据结构或算法,多做几道题来检验一下就好。但如何把所学运用于实践呢?这里给你一个简单的路径:

数据结构与算法进阶路径

初级玩家

中级玩家

高级玩家

骨灰级玩家

简单总结起来,最初是套用数据结构与算法来解决问题,到最后是为了解决问题设计适合的数据结构与算法。

其实,不管是架构师还是最基础的业务工程师,即使你每天的工作就是CURD,也会用到数据结构和算法,只是自己不自知而已。

比如,Java 的 ArrayList 是用的最广泛的数据结构吧,但它其实有个缺点是不能存储基本数据类型,比如 int、long,需要封装为 Integer、Long 类,而自动装箱和拆箱是有一定的性能损耗的,如果你的代码特别关注性能,就可以考虑直接使用数组;甚至有时候,如果事先知道数据大小,且对数据的操作非常简单,可以使用数组来代替 ArrayList。

你看,数据结构的应用就这么简单,至少不是我们所想象的那么高大上。

再比如,当需要缓存数据时,一般都是直接使用 Guava Cache 或 Ehcache,但这时候是不是可以考虑下,如果让我来实现一个LRU缓存,该怎么做?使用什么数据结构?大致思路是什么?

如果使用链表来实现,可以这样做:

越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:如果此时缓存未满,则将此结点直接插入到链表的头部;如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

这时缓存访问的时间复杂度是O(N),那可不可以继续优化,让缓存访问的时间复杂度降到O(1),想得到更好,如果没想到,那就去 Guava Cache 的源码翻翻。看看一个工业级的内存缓存是如何实现的?要考虑哪些问题?自己为什么没有想到?

这样想想的话,数据结构与算法其实离我们也没那么远,不管你做什么工作,都可以用到。

最后

这篇文章其实是写给自己的,自己在这方面也非常弱,平时嘴上也说着要好好学学,但注意力总是被一些看似“高大上”的内容所吸引,总觉得不喊几句大数据和高并发都 low 人一截。

但真的是这样吗?我应该好好想想了。

最后,推荐学习专栏 数据结构与算法之美,专栏对上述20种数据结构和算法由浅入深,做了非常详尽的介绍,我们一起学习吧。

还有,关于性能优化这一主题,内容挺多的,还没写完……

封面图:Isaac Smith

参考资料

如何将数据结构和算法应用到实际之中?

极客时间专栏:数据结构与算法之美 - 入门篇

Comments

Post a Message

人生在世,错别字在所难免,无需纠正。

提交评论