关于大数据:浅谈常见数据结构和算法的应用系列一

近来有小伙伴问我：刷 leetcode 真的有用吗，感觉收益很小，越刷越迷茫了 …

诚然每个人刷题的目标不一样，233 酱还不是为了能水几篇文章 …

当然不止。我感觉刷题是一件有意思的事，就像小猫小狗咬本人尾巴，捉弄的不可开交。比喻可能不太失当，是有种沉迷小游戏的感觉。可是在艰巨打野的过程中，咱们不要忘了，最重要的是：理解每种技能包的特点，适宜解决的问题和场景。在特定实战场景下可能应用特定的技能包，借鉴技能包。这才是文治的至高境界。

装 X 完结，浅谈开始。。

数据结构是指：一种数据组织、治理和存储的格局，它能够帮忙咱们实现对数据高效的拜访和批改。

数据结构 = 数据元素 + 元素之间的构造。

如果说数据结构是造大楼的骨架，算法就是具体的造楼流程。流程不同，效率资源不同。我会两者联合简略探讨下他们的特点和利用。

常见的数据结构可分为：线性构造、树形构造 和 图状构造。

常见的算法有：递归、排序、二分查找、搜寻、哈希算法、贪婪算法、分治算法、回溯算法、动静布局、字符串匹配算法 等。

本文从 线性数据结构、递归 和 排序算法 谈起。

线性构造

线性构造：是指数据排成像一条线一样的构造。每个元素结点最多对应一个前驱结点和一个后继结点。如数组, 链表，栈，队列等。

数组

数组是是由雷同类型的元素（element）的汇合所组成的数据结构，调配一块间断的内存来存储。利用 元素的下标地位 能够计算出该元素对应的存储地址。

长处 ：
调配基于间断内存，是一种天生的 索引 构造，查问批改元素的效率 O(1)。同时能够借助 CPU 的缓存机制，预读数组中的数据，所以拜访效率更高。

毛病 ：
数组的索引长处也是它的毛病，因为它的索引是基于一块间断内存元素存储的地位下标决定的，增删 arr[i]工夫复杂度 O(n)，须要整体挪动数组 arr[i-n-1]的地位。此外，调配大数组会占用较大的内存。

可通过以下形式防止元素拷贝和占用大的开销：

1. 懒删除：删除时只标记元素被删除，并不真正的执行删除。当数组整体内存不够用时，再执行真正的删除。
2. 分块思维：将一大块内存分为 n 个小块，以 小块 为单位进行数组内存的拷贝。如 Mysql 的 InnoDB 引擎中每个 Buffer Pool 实例由若干个 chunk 组成，理论内存申请操作以 chunk 为单位。
3. 缩容：已经面试阿里时，就让设计了一个缩容版的 HashMap。节约可耻，节约光彩。
4. 链表。

链表

链表的存在就是为了解决数组的增删简单耗时，内存占用较大的问题。它并不需要一块间断的内存空间，它通过 指针 将一组零散的内存块串联起来。依据指针的不同，有单链表，双向链表，循环链表之分。

长处 ：
增删 arr[i]工夫复杂度 O(1)，应用链表自身没有大小的限度，人造地反对动静扩容。

毛病 ：
没有“索引”，查问工夫复杂度 O(n)。须要保护指针，更占内存。同时内存不间断，容易造成内存碎片。

能够看出：数组和链表是互相补充的一对数据结构。那怎么补救链表的有余呢？

内存这块是不好解决，这是由 指针 决定的。对于索引，没索引就帮它建索引好了：

1. 联合 hash 表，记录链表每个结点的地位。
2. 链表长度拉的过长时，思考跳表，红黑树这类数据结构。（别慌，前面会讲～）

利用场景：
数组和链表的使用很宽泛，他们是形成 数据结构的根底。如栈，队列，汇合等等。

栈

栈是一种受限制的线性数据结构。元素只能够在栈顶被拜访。合乎先进后出的 First-In-Last-Out 的拜访形式。

用数组实现的叫程序栈，用链表实现的叫链式栈。可能有人会有疑难：我用数组链表在头尾两端可伸可缩，为毛要用只能在头部操作的栈构造呢？
这种 FILO 的构造当然是只实用于 FILO 的场景。如果咱们将数组 / 链表这种构造封装为栈，就能够只应用其 pop/push 的 API，屏蔽掉实现细节。

利用场景：
1. 编辑器的 redo/undo 操作。
2. 浏览器的后退 / 后退操作。
3. 编译器的括号匹配校验
4. 数学计算中的表达式求值
5. 函数调用
6. 递归
7. 字符串反转 …

队列

队列也是一种受限制的线性数据结构。合乎先进先出的 First-In-First-Out 的拜访形式。同样，用数组实现的队列叫作程序队列，用链表实现的队列叫作链式队列。

依据头尾指针和操作的不同，队列又可分为双端队列，循环队列，阻塞队列，并发队列。

• 双端队列：头尾均能够进行插入，删除，拜访元素，更为实用。不存在 FIFO 这种限度。

• 循环队列：把队列的头尾相连接并且应用顺序存储构造进行数据存储的队列。

存在并发的场景下，队列存取元素的临界区为 队列空时的取操作 和 队列满时的存操作。保障并发下的队列存取平安为阻塞队列 和 并发队列。两者的区别在于 同步资源的粒度不同。

• 阻塞队列：通过 互斥锁 保障enqueue、dequeue 的平安，锁粒度较大。如 Java JUC 包中的阻塞队列。
• 并发队列：基于数组的循环队列，利用 CAS 原子操作保障 enqueue、dequeue 的平安。
  其实就是通过：屡次 volatile 读 + CAS 操作 这种乐观思维 批改头尾指针的地位，保障enqueue、dequeue 的平安。CAS 的同步代价小较小，所以称为：无锁并发队列。如 Disruptor 框架中 Ring Buffer 就使用了这点。

PS: 很多框架对线程池的需要都替换成了 Disruptor 来实现，如 Log4j2、Canal 等。

利用场景：
队列的作用其实就是事实中的排队。当资源有余时，通过“队列”这种构造来实现排队的成果。用于：
1. 任务调度存在的中央：CPU/ 磁盘 / 线程池 / 任务调度框架 …
2. 两个过程中数据的传递：如 pipe/file IO/IO Buffer…
3. 生产者消费者场景中..
4.LRU

递归实现

递归 是一种算法求解的编码实现。利用于如深度优先搜寻、前中后序二叉树遍历（挖坑前面讲～）等。因为接下来的排序算法如：归并 / 快排 可通过递归来实现，所以咱们先看一下书写递归的步骤。相熟了递归的思维，它其实是一种书写简略的编码方式。

只有问题满足以下三点，均可应用递归来进行求解：

1. 一个问题的解能够合成为几个子问题的解
2. 问题和子问题之间，除了数据规模不同，求解思路齐全一样
3. 存在递归终止条件

写递归代码的关键在于：找到如何将大问题合成为小问题的 法则 ，并且基于此写出 递推公式 ，而后再敲定 终止条件，最初将递推公式和终止条件翻译成代码。

因为人并不善于解决这种程序，所以在写递归代码的时候，咱们能够主动屏蔽掉递归的执行过程。咱们只须要通知程序：递推公式 和 终止条件 是什么，事件就会便 Easy~

应用时的留神项：

1.stackoverflow: 理论函数调用档次太深，就会有零碎栈或者虚拟机栈空间溢出的危险。

2. 子问题的反复计算：后面文章我有讲 动静布局通过防止子问题的反复计算可能升高工夫复杂度。一种形式就是通过 递归 + 备忘录（子问题的解保存起来）来解决。

排序算法

233 酱学习的第一个算法就是冒泡排序算法，我想不少码农都经验过被“几大排序算法”摆布的恐怖。

排序是咱们在我的项目工程中常常遇到的一个场景，如 TopK，中位数问题等。有序 和 无序 的数据汇合之间的差异在于 前者 “逆序对” 为 0.

小贴士：如果 i < j，且 a[i] > a[j], 就称为一个逆序对，如 1，7，3，5 中的 <7，5>
反之则为有序对，如 <1,3>

不同的排序算法毁灭逆序对的形式不一样，体现在时空复杂度，排序形式，稳定性，实用场景等方面不同。

我先放一张网上排序算法的图：

抉择排序算法时，咱们应该思考算法的执行效率，内存耗费，稳定性等这些因素。

PS：以下内容次要援用极客工夫王争大佬的《数据结构和算法之美》课程，233 能力无限，默默给大佬打广告 & 点赞。

如何剖析排序算法的执行效率

1. 最好状况、最坏状况、均匀状况工夫复杂度

对于要排序的原始数据，数据的有序度不同，对排序的执行效率是有影响的。比方靠近有序的待排序数据 插入排序的工夫复杂度靠近 O(n)。咱们须要理解排序算法在不同数据下的性能体现。

2. 工夫复杂度的系数、常数、低阶

在对小规模的数据排序时，如 10 个，100 个，1000 个。须要把系数、常数、低阶也思考进来，能力抉择适合的排序算法。

3. 比拟次数和替换（或挪动）次数

基于比拟的排序算法的执行过程，会波及两种操作，一种是元素比拟大小，另一种是元素替换或挪动。所以，如果咱们在剖析排序算法的执行效率的时候，应该把比拟次数和替换（或挪动）次数也思考进去。

排序算法的内存耗费

上图中有一列排序形式：原地排序（In-place）和 内部排序 (Out-place)。前者是指空间复杂度为 O(1) 的排序算法，不须要在内部开拓内存空间。后者须要额定开拓空间来存储中间状态。前者的益处在于能够借助 CPU 的缓存机制，拜访效率更高。这是一个重要的考量因素。

小贴士：快排的空间复杂度为是因为它的实现是递归调用的，每次函数调用中只应用了常数的空间，因而空间复杂度等于递归深度 O(logn)。

排序算法的稳定性

稳定性是指：待排序的序列中存在值相等的元素，通过排序之后，相等元素之间原有的先后顺序是不变的。

为啥要思考排序算法的稳定性呢？
这是因为理论场景中的待排序的对象 排序维度可能是多个。比方咱们对订单先依照金额排序，再依照下单工夫排序。实现简略的思路为：先给订单依照 下单工夫排序，再依照金额排序。稳定性的排序算法可能保障 金额雷同的两个对象，在排序之后的下单程序不变。

上面次要从数据规模上探讨这些排序算法的利用。

小规模数据排序

在小规模数据下，冒泡排序 / 抉择排序 / 插入排序实现较为简单，排除不稳固的抉择排序，插入排序（可类比打扑克抓牌时的排序思维）比冒泡排序（最大元素顺次往后冒）好在替换次数少，小规模下排序效率更高。

此外当待排序序列的有序度比拟高时，插入排序也好过归并 / 快排这类 O(nlogn)的效率。所以 在小规模数据场景下，适宜用插入排序。

大规模内存级数据排序
大规模数据排序适宜思考 O(nlogn)级别的排序算法，这里探讨 归并排序 和 疾速排序。

归并排序 的思维是 分治 思维。将整个无序序列的排序 划分为 无序小序列的排序问题。子序列有序了，再合并起来有序的子序列，整体就排好序了。
归并排序是内部排序。每次合并操作都须要申请额定的内存空间，在合并实现之后，长期开拓的内存空间就被开释掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个长期的内存空间在应用。长期内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

疾速排序 利用的也是 分治 思维。部分有序 最终 全局有序。它应用一个分区点数据(pivort) 将元素分为 < pivort,=pivort,>pivort 三个局部。而后在 < pivort 和 >pivort 这两局部持续递归解决，最终排序实现。

如果 快排正当的抉择 pivort，多路指针参加分区能够防止工夫复杂度的好转。而且快排是原地排序，相比归并排序是内部排序，空间复杂度较高 O(n)。快排的利用更为宽泛。

Java 中 Arrays.sort 是混合排序，实现策略分为两种：

Case1. 存储的数据类型是根本数据类型

应用的是快排，在数据量很小的时候，应用的插入排序；

Case2. 存储的数据类型是 Object

应用的是归并排序，在数据量很小的时候，应用的也是插入排序

大规模内部数据排序

当数据规模很大时，咱们并不能把所有数据都加载到内存。这时候能够思考工夫复杂度是 O(n) 的内部排序算法：桶排序、计数排序、基数排序。内部排序是指数据存储在内部磁盘中。

这里工夫复杂度之所以低是因为：这三个算法是非基于比拟的排序算法，都不波及元素之间的比拟操作。

桶排序 是依照某种属性将元素调配到全局有序的子桶内，再在子桶内做部分排序。当子桶个数划分的足够大时，工夫复杂度就靠近 O(n)。

计数排序 其实是桶排序的一种非凡状况。当要排序的 n 个数据，所处的范畴并不大的时候，比方最大值是 k，咱们就能够把数据划分成 k 个桶。每个桶内的数据值都是雷同的，省掉了桶内排序的工夫。

基数排序 是依据每一位来排序，基数排序对要排序的数据是有要求的，须要能够宰割出独立的“位”来比拟，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不必比拟了。除此之外，每一位的数据范畴不能太大，要能够用线性排序算法来排序，否则，基数排序的工夫复杂度就无奈做到 O(n) 了。

感谢您的浏览，文中有谬误或者太过通俗的局部还请帮 233 酱指出 & 补充。感觉有播种就四连 「关注，点赞，在看，转发」 反对下 233 酱吧。

另外，关注公众号【码农知识点】加我微信好友，欢送退出我的刷题技术探讨群。和 233 独特成长提高～

参考资料：

[1]. 维基百科

[2].https://time.geekbang.org/column/intro/126

[3].https://zhuanlan.zhihu.com/c_190721074