阅读 1958

「前端进阶」前端如何搞定数据结构与算法(先导篇)

观感度:🌟🌟🌟🌟🌟

口味:锅包肉

烹饪时间:20min

本文已收录在Github github.com/Geekhyt,感谢Star。

为什么要学习数据结构与算法?

在0202年的今天,由于每天被无数的信息轰炸,大多数人已经变得越来越浮躁了,并且丧失了独立思考的能力。

你可能会经常听到这样的感慨:

  • 技术人究竟能走多远?我遇到了天花板
  • 35岁的程序员要如何面对中年危机?
  • 技术更新太快,好累,学不动了

然后,你也变得焦虑起来。那你有没有静下心来想过,如何才能抵御年龄增长并且使自己增值呢?

无非是终身学习,持续修炼自己的内功。内功也就是基础知识和核心概念,这些轰轰烈烈发展的技术本质,其实都是基础知识,也就是我们在大学里学过的基础课程。

  • 操作系统
  • 计算机组成原理
  • 计算机网络
  • 编译原理
  • 设计模式
  • 数据结构与算法

这也就是为什么越靠谱的面试官越注重你基础知识的掌握程度,为什么越牛的的企业越重视你的算法能力。因为当你拥有了这些,你已经比大多数人优秀了。你的天花板由你自己来决定,大家口中的中年危机可能并不会成为你的危机。新技术来临时,你对它的本质会看得更加透彻,学起来会一通百通。这样的人才,公司培养你也会花费更少的成本。

(不过,一辈子做个开开心心的 CRUD Boy 也是一种选择。)

数据结构与算法之间的关系

Rob Pike's 5 Rules of Programming中的第五条是这样说的:

Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

数据占主导。如果您选择了正确的数据结构并组织得当,那么这些算法几乎总是不言而喻的。数据结构而非算法是编程的核心。

瑞士计算机科学家,Algol W,Modula,OberonPascal 语言的设计师 Niklaus Emil Wirth 写过一本非常经典的书《Algorithms + Data Structures = Programs》,即算法 + 数据结构 = 程序

我们可以得出结论,数据结构与算法之间是相辅相成的关系。数据结构服务于算法,算法作用于特定的数据结构之上。

数据结构与算法好难,怎么学?

  • 是不是我脑子有问题?智商不够?
  • 数学太难了,我天生数学就不好
  • 好不容易搞懂了一个算法,没过几天就忘了

在我坚持刷 LeetCode 这段时间,我也曾产生过怀疑,但后来发现,其实都不是。学习都是反人性的,贵在坚持。数据结构与算法这块知识并不适合零碎的时间来学习,你首先需要规划整块的时间。然后从最基础数据结构开始学起,从易到难,由浅入深。学到后面你会发现。其实,数据结构中的基础就是数组(顺序存储)和链表(链式存储)

  • 队列和栈可以分别通过数组和链表实现
  • 通常情况下我们会用数组实现堆(完全二叉树),用链表也可以实现(二叉搜索树、红黑树、AVL、B树等)
  • 图用二维数组实现就是邻接矩阵,用链表实现就是邻接表
  • 散列表中可以用链表解决散列冲突(拉链法),也可以用数组(线性探测法)

所以,记住这些基础的概念,学习复杂的数据结构和算法时会事半功倍。

(算法的套路过多,请允许我再开一篇专栏)

时间久了记不住怎么办?

美国缅因州国家训练实验室做过学习金字塔的实验并得出如下报告,这个理论最早于1946年由美国学者 Edgar Dale 提出。

人的学习分为被动学习和主动学习两个层次。

  • 被动学习:听讲、阅读、试听、演示。学习内容平均留存率为5%、10%、20%和30%。
  • 主动学习:讨论、实践、教授给他人,平均留存率为50%、75%和90%。

这个理论可能大家早已听过,但是实际践行的人又有多少呢?

数据结构与算法也是这样,你需要养成 LeetCode 上每日一题的习惯,并及时复习淡忘的部分。除此之外,践行主动学习。找到志同道合的小伙伴,一起交流进步。还可以在开源项目上提供题解,这样也是教授给他人的一种方式。

这里推荐一个好朋友 Lucifer 的已有 30K+ StarLeetCode 题解库,我已经提交了一些题解,写题解的时候你会发现,这才是真正考验你是否掌握的时候。

lucifer的LeetCode解题之路

数据结构与算法在前端中的应用

  • 你熟知的 DOM 树、AST 树、以及 Vue、ReactVirtual DOM 都是树。

  • React Hooks 的本质是数组,React Fiber 是基于链表实现的。

  • HTTP 缓存响应消息 和 Vuekeep-alive 都用到了 LRU 算法。

  • 浏览器前进后退功能通过实现。

  • TCP 连接实现多路复用时借助了epoll,而决定 epoll 高效的原因:数据结构采用了红黑树队列

  • 搜索引擎采用的是广度优先搜索策略

如果你了解 Linux、Nginx 、数据库和一些消息队列,你会发现到处都是数据结构与算法的应用。这里举几个例子:

  • Linux 进程调度、进程空间管理用到了红黑树
  • Linux 文件系统中为了提高目录项对象的处理效率:LRU、哈希表
  • Linux 路由表 Tire 树
  • Nginx 定义缓存 key 用到了红黑树
  • MySQL 数据库索引使用 B+ 树提高查询效率
  • Redis中根据大多数开发场景下,数据的大小和多少采用更适合存储的数据结构。(数据量小用数组下标访问快、占用内存小。但是因为数组需要占用连续的内存空间,所以当数据量大的时候,采用链表,同时又为了兼顾速度又需要和数组结合,从而有了散列表。)
  • 分布式消息队列,RocketMQKafka 也是一种队列

通关数据结构与算法的捷径?

刷题就是捷径。

对,你没看错。

其实,和计算机交流真的很简单,你给他输入,他肯定会给你输出。比女朋友好伺候多了。

掘金小册、开源项目及书单推荐

掘金小册

修言的 《前端算法与数据结构面试:底层逻辑解读与大厂真题训练》,我在小册撰写前期有幸参与试读,修言大佬保姆级别教程,不买后悔系列。

开源项目

书单

初级

  • 算法图解
  • 大话数据结构
  • 算法之美
  • 数学之美
  • 数据结构与算法 JavaScript 描述

经典

  • 算法
  • 算法导论

典藏

  • 计算机程序设计艺术

写在最后

伽利略曾经说过,“宇宙这本书是用数学语言写成的”

数学不光是曾经在学校学过的公式,它其实是一种思维模式,所以最终要提高的是归纳、总结和抽象的能力。

前面的路还很长,共勉。

❤️爱心三连击

1.看到这里了就点个赞支持下吧,你的是我创作的动力。

2.关注公众号前端食堂,你的前端食堂,记得按时吃饭

3.本文已收录在前端食堂Github github.com/Geekhyt,求个小星星,感谢Star。