《微观经济学》读书笔记

发表于 2024-10-25 更新于 2024-12-11

思维导图

《运筹学》读书笔记

发表于 2024-09-01 更新于 2024-12-11

思维导图

数据结构系列（四）图、网结构总结

发表于 2024-05-07 更新于 2024-12-11

逻辑结构

图的种类

维基百科对图（Graph）的定义：

A graph is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically.

无向图（Undirected Graph）

无向图

任何两个顶点（vertex）之间都有边（edge）的无向图称为无向完全图。一个具有 n 个顶点的无向完全图的边数为：

$$
C^2_n=n(n-1)/2
$$

有向图（Directed Graph）

有向图

任何两个顶点（vertex）之间都有弧（arc）的有向图称为有向完全图。一个具有 n 个顶点的有向完全图的弧数为：

$$
P^2_n=n(n-1)
$$

带权图（Weighted Graph）

带权图

边或弧上带有权值的图，也称为网（network）。

维基百科对网（network）的定义：

In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes (e.g. names).

图（graph）是高度抽象后的逻辑结构，而网（network）在此之上可以通过在顶点（vertex）和边（edge）上增加属性来包含更多的信息，更偏重于对实际问题的建模。

What’s the difference between Adjacency and Connectivity ?

在无向图中，邻接是点与点或者边与边之间的关系。在无向图中，如果两个点之间至少有一条边相连，则称这两个点是邻接的。同样，如果两条边有共同的顶点，则两条边也是邻接的。关联是点与边之自的关系。一个点如果是一条边的顶点之一，则称为点与该边关联。

存储结构

邻接矩阵（Adjacency Matrix）

维基百科对矩阵（Matrix）的定义：

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.

维基百科对矩阵（Matrix）的定义 2：

数学上，一个 $m×n$ 的矩阵是一个由 $m$ 行（row）$n$ 列（column）元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。

矩阵（Matrix）是很多科学计算问题研究的对象，矩阵可以用二维数组来表示。

图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

定义如下：

设 $G=(V,\ E)$ 是一个图，其中 $V={v_0,\ v_1,\ …\ ,\ v_{n-1}}$，那么 $G$ 的邻接矩阵 $A$ 定义为如下的 $n$ 阶方阵：

$$
A_{[i][j]}=
\begin{cases}
1& {若\ (v_i,\ v_j)\ 或\ <v_i,\ v_j>\ ∈\ E}\
0& {若\ (v_i,\ v_j)\ 或\ <v_i,\ v_j>\ ∉\ E}
\end{cases}
$$

邻接矩阵

可见，若无向图 $G$ 中有 $n$ 个顶点 $m$ 条边，采用邻接矩阵存储，则该矩阵中非 0 元素的个数为：
$$
2m
$$

对称矩阵（Symmetric Matrix）

用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。为什么这么说呢？

对于无向图来说，如果 $A_{[i][j]}$ 等于 1，那 $A_{[j][i]}$ 也肯定等于 1。实际上，我们只需要存储一个就可以了。也就是说，无向图的二维数组中，如果我们将其用对角线划分为上下两部分，那我们只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了。

上面描述的是一类特殊矩阵：

若一个 $n$ 阶方阵 $A$ 中的元素满足下述条件：
$$
a_{ij}=a_{ji} \quad (0≤i,\ j≤n-1)
$$

则 $A$ 称为对称矩阵（Symmetric Matrix）。

In the mathematical discipline of linear algebra, a symmetric matrix is a square matrix that is equal to its transpose.

对称矩阵可以压缩存储：对称矩阵有近一半的元素可以通过其对称元素获得，为每一对对称元素只分配一个存储单元，则可将 $n^2$ 个元素压缩存储到含有 $n(n＋1)/2$ 个元素的一维数组中。

三角矩阵（Triangular Matrix）

以对称矩阵的主对角线为界，上（下）半部分是一个固定的值（如 0），这样的矩阵称为：上三角矩阵（Upper Triangular Matrix）或下三角矩阵（Lower Triangular Matrix）。

In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix. A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero.

稀疏矩阵（Sparse Matrix）

如果我们存储的是稀疏矩阵（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。

这里描述的是一类「非零元素个数很少的矩阵」，即稀疏矩阵（Sparse Matrix）。

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero.

稀疏矩阵可以压缩存储，使用三元组表示法：$(i,\ j,\ a_{ij})$。

总结，邻接矩阵的存储方法的优点：

首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。

其次，用邻接矩阵存储图的另外一个好处是方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。比如求解最短路径问题时会提到一个 Floyd-Warshall 算法，就是利用矩阵循环相乘若干次得到结果。参考：《矩阵运算及其运算规则》

此外，针对邻接矩阵比较浪费存储空间的缺点，解决方案：

不带权的无向图的邻接矩阵，一定是一个对称矩阵，因此可以转为三角矩阵之后进行压缩存储。

有向图、带权图的邻接矩阵，一般都不是一个对称矩阵。但如果是一个稀疏矩阵，可以使用三元组表示法进行压缩存储。

邻接表（Adjacency List）

邻接表（Adjacency List）的定义：

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.

邻接表

还记得我们之前讲过的时间、空间复杂度互换的设计思想吗？邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。

就像图中的例子，如果我们要确定，是否存在一条从顶点 2 到顶点 4 的边，那我们就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。而且，我们前面也讲过，链表的存储方式对缓存不友好。所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。

在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。所以，我们也可以将邻接表同散列表一样进行 “改进升级”。

我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选择用红黑树。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。当然，这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。除此之外，我们还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

图的应用

图的搜索（遍历）

https://en.wikipedia.org/wiki/Graph_traversal

图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。具体方法有很多，比如两种最简单、最 “暴力” 的深度优先、广度优先搜索，还有 A*、IDA* 等启发式搜索算法。

连通图的两种搜索方式：

	邻接矩阵	邻接表
深度优先搜索		栈（LIFO）实现（$O(n+e)$）
广度优先搜索		队列（FIFO）实现

深度优先搜索（DFS）

https://en.wikipedia.org/wiki/Depth-first_search

深度优先搜索（Depth-first search, DFS）类似于树的先序遍历。

想象成“走迷宫”的过程。

深度优先搜索

实际上，深度优先搜索用的是一种比较著名的算法思想——回溯思想。这种思想解决问题的过程，非常适合用递归来实现。而递归的本质就是压栈与出栈操作。

深度优先搜索的栈（LIFO）实现，过程如下图，将压栈 push 的顶点序列输出即可。

深度优先搜索的栈实现

广度优先搜索（BFS）

https://en.wikipedia.org/wiki/Breadth-first_search

广度优先搜索（Breadth-first search, BFS）类似于树的层次遍历。

想象成 “地毯式搜索” 层层推进的过程。

广度优先搜索的队列（FIFO）实现，过程如下：

首先顶点入队，并输出。
然后顶点出队。
将出队顶点相连的所有顶点依次入队，并输出。

重复 2、3 两步，直到所有顶点输出为止，最终结果不唯一。

广度优先搜索的队列实现

广度优先搜索

连通分量

无向图中的极大连通子图（Maximal connected subgraph）称为原图的连通分量（Connected Components）。

连通分量

连通图只有一个极大连通子图，就是它本身。

最小生成树问题（MST problem）

如果无向图中，任意两个顶点都连通，称为连通图（Connected Graph）。如下图：

无向图

如果连通图中，边上有权值，称为连通网（Connected Network）。如下图：

带权图

连通图的一次遍历所经过的点和边的集合，构成一棵生成树（Spanning Tree）。

一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图（Minimum connected subgraph）。

一个具有 $n$ 个顶点的连通图，它的生成树的边数为 $n-1$。

连通图的遍历序列不是唯一的，所以能得到不同的生成树。其中权值总和最小的生成树，称为最小生成树（Minimum Spanning Tree, MST）。如下图：

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.

最小生成树

最小生成树的准则：

必须使用且仅使用连通网中的 n-1 条边来联结网络中的 n 个顶点；
不能使用产生回路的边；
各边上的权值总和达到最小。

最小生成树的应用：规划出总长度最小的网络

例如工程领域设计，如最小成本的铺设网线、电缆、管道、道路、…
https://en.wikipedia.org/wiki/Minimum_spanning_tree#Applications

Prim 算法

https://en.wikipedia.org/wiki/Prim%27s_algorithm

假设 $N=(V,\ E)$ 是连通网，$TE$ 是 $N$ 上最小生成树中边的集合：

初始态：$U={u_0},\ (u_0∈V),\ TE={}$
在所有 $u∈U,\ v∈V-U$ 的边 $(u,\ v)∈E$ 中找一条代价最小的边 $(u,\ v_0)$ 并入集合 $TE$，
同时 $v_0$ 并入 $U$
重复 2，直到 $U=V$

形象化理解：由点找边再找点的过程。

Prim 算法

📝 习题 📝

Kruskal 算法（加边法）

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

假设 $N=(V,\ E)$ 是连通网

非连通图 $T={V,\ {}}$，图中每个顶点自成一个连通分量
在 $E$ 中找一条代价最小，且其两个顶点分别依附不同的连通分量的边（即不形成回路的边），将其
加入 $T$ 中
重复 2，直到 $T$ 中所有顶点都在同一连通分量上

形象化理解：由边找点。

Kruskal 算法

最短路径问题（Shortest path problem）

在图论中，最短路径问题是在连通图中寻找两个顶点之间的一条路径，使得其组成边的权重（如时间、距离、费用等）之和最小化的问题。

最短路径的应用：

例如规划交通路线、解决运输问题、编制生产计划、…
https://en.wikipedia.org/wiki/Shortest_path_problem#Applications

最短路径的计算方法：

最短路径算法还有很多，比如 Bellford 算法、Floyd 算法等等。

回溯算法

从终点开始，逐步逆向推算。（从终点到起点的逆向回溯过程。）

Dijkstra 算法

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

《44 | 最短路径：地图软件是如何计算出最优出行路径的？》

📝 习题 📝

目的地	起点：甲	前驱	最短路径
1 ✅（2️⃣）	33	甲	甲 - 1
2 ✅（1️⃣）	27	甲	甲 - 2
3 ✅（4️⃣）	52	甲	甲 - 3
4 ✅（3️⃣）	47	2	甲 - 2 - 4
5 ✅（6️⃣）	~~122~~ 100	3 乙	甲 - 2 - 4 - 乙 - 5
乙 ✅（5️⃣）	73 67	1 4	甲 - 2 - 4 - 乙

A* 算法

https://en.wikipedia.org/wiki/A*_search_algorithm

《49 | 搜索：如何用 A * 搜索算法实现游戏中的寻路功能？》

最大流问题（Maximum flow problem）

https://en.wikipedia.org/wiki/Maximum_flow_problem

当以物体、能量或信息等作为流量流过网络时，怎样使流过网络的流量最大，或者使流过网络的流量的费用或时间最小。通常，把设计这样的流量模型问题，叫作网络的流量问题。

最大流量问题，就是在一定条件下，要求流过网络的流量为最大的问题。

📝 习题 📝

拓扑排序（Topological sorting）

拓扑排序算法：

在有向图中选一个入度为 0 的顶点并输出。
从图中删除该顶点和所有以它为尾的弧。

重复 1、2 两步，直到所有顶点输出为止，最终结果不唯一。

设某有向图中有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为 $O(n+e)$。

拓扑排序

https://en.wikipedia.org/wiki/Topological_sorting

《43 | 拓扑排序：如何确定代码源文件的编译依赖关系？》

图的两种存储结构，在社交应用的优缺点对比如下。例如在微博（有向图）中，设我为 $v_i$，ta 为 $v_j$：

邻接矩阵
- 优点：
  - 存储方式简单、直接，因为基于数组，用户之间的关系获取（$O(n)$）、建立（$O(1)$）、查找（$O(1)$）非常高效。
- 缺点：
  - 比较浪费存储空间。
  - 获取的好友关系无序。
邻接表：
- 优点：
  - 节约存储空间。
  - 获取的好友关系可以按关键字排序。
- 缺点：
  - 用户之间的关系建立、查找相对低效（取决于”关系“使用的数据结构）。
  - 关注列表（邻接表）、粉丝列表（逆邻接表）需要分别存储、同时维护，关系维护相对繁琐。

需求	邻接矩阵	邻接表 A、逆邻接表 R
我关注的人	$A_{[i][0-n]}$	$A_{[i]}$
我的粉丝（关注我的人）	$A_{[0-n][i]}$	$R_{[i]}$
我关注 ta	$A_{[i][j]}$ = 1	insert($A_{[i]}$, $v_j$) && insert($R_{[j]}$, $v_i$)
我取消关注 ta	$A_{[i][j]}$ = 0	delete($A_{[i]}$, $v_j$) && delete($R_{[j]}$, $v_i$)
我是否关注 ta	$A_{[i][j]}$ == 1	exist($A_{[i]}$, $v_j$)
ta 的粉丝是否有我	$A_{[i][j]}$ == 1	exist($R_{[j]}$, $v_i$)

基于上述存储结构，可以进一步实现如下需求（以邻接表为例）：

# 求共同关注
A[i] ∩ A[j]

# 我关注的人也关注 ta
foreach(member in A[i]) {
  # 我每个关注的人，他们关注的人中，是否有 ta
  A[member] ∩ vj
}

# 我可能认识的人
foreach(member in A[i]) {
  # 我每个关注的人，他们关注的人中，有我还没关注的
  A[member] - A[i]
}

《图应用：微博系统中的好友关系》

知识图谱（Knowledge graph）

https://en.wikipedia.org/wiki/Knowledge_graph

参考

https://en.wikipedia.org/wiki/Graph_theory

https://en.wikipedia.org/wiki/Network_theory

《30 | 图的表示：如何存储微博、微信等社交网络中的好友关系？》

《31 | 深度和广度优先搜索：如何找出社交网络中的三度好友关系？》

数据结构系列（三）树结构总结

发表于 2024-05-05 更新于 2024-12-11

一叉树

有没有想过为啥有二叉树，而没有一叉树？实际上顺序表、链式表就是特殊的树，即一叉树实现。

二叉树

二叉树的五种基本形态：

注意：一棵树（包括二叉树）的最少结点个数为 0（空树）。

二叉树的五种基本形态

二叉树的常见形态：

二叉树
满二叉树
完全二叉树

二叉树的性质

二叉树的通用性质：

性质 1：二叉树第 i (i ≥ 1) 层至多有 $2^{i-1}$ 个结点。
性质 2：深度为 k (k ≥ 1) 的二叉树至多有 $2^k-1$ 个结点。
性质 3：二叉树中，若度数为 0 的叶子结点个数为 $n_0$，度数为 2 的结点个数为 $n_2$，则 $n_0 = n_2 + 1$。
若根节点的层数为 1，则具有 n 个结点的二叉树的最大高度为 n（即一叉树）。

参考：https://www.atnyla.com/tutorial/level-and-height-of-the-tree/3/392

逻辑结构

下面介绍几种特殊的二叉树：

满二叉树（Full Binary Tree）

满二叉树的性质：

深度为 k (k ≥ 1) 的满二叉树，共有 $2^k-1$ 个结点。如下图和表格：

$k=1$ $k=2$ $k=3$ $k=4$

结点总数 $2^1-1=1$ $2^2-1=3$ $2^3-1=7$ $2^4-1=15$

	$k=1$	$k=2$	$k=3$	$k=4$
结点总数	$2^1-1=1$	$2^2-1=3$	$2^3-1=7$	$2^4-1=15$

完全二叉树（Complete Binary Tree）

完全二叉树

完全二叉树的性质：

含有 n 个结点的完全二叉树，深度为 $⌊log_2n⌋+1$。
深度为 k 的完全二叉树：

$k=1$ $k ≥ 2$

最少结点数 $2^{k-1}$ $2^{k-1}$

最少叶子结点数 $k$ $2^{k-2}$

如下图和表格：

$k=1$ $k=2$ $k=3$ $k=4$

最少结点数 $2^{1-1}=1$ $2^{2-1}=2$ $2^{3-1}=4$ $2^{4-1}=8$

最少叶子结点树 1 $2^{2-2}=1$ $2^{3-2}=2$ $2^{4-2}=4$
含有 n 个结点的完全二叉树按层编号，则：

	$k=1$	$k ≥ 2$
最少结点数	$2^{k-1}$	$2^{k-1}$
最少叶子结点数	$k$	$2^{k-2}$

	$k=1$	$k=2$	$k=3$	$k=4$
最少结点数	$2^{1-1}=1$	$2^{2-1}=2$	$2^{3-1}=4$	$2^{4-1}=8$
最少叶子结点树	1	$2^{2-2}=1$	$2^{3-2}=2$	$2^{4-2}=4$

完全二叉树的父子结点编号计算

存储结构

顺序存储结构

如果将完全二叉树按层编号，并以编号作为数组下标将结点存入一维数组中，则完全二叉树的顺序存储结构如下图：

完全二叉树的顺序存储

通过观察，完全二叉树按层编号之后，编号之间的关系满足下图的编号计算公式。

完全二叉树的父子结点编号计算

公式可以准确反映出结点之间的逻辑关系，可用于求某结点的父、子结点。（这一性质是二叉树顺序存储结构的基础）

但如果将非完全二叉树按层编号进行顺序存储，则无法套用编号计算公式求父、子结点：

	优点	缺点
方式一：直接对结点按层编号，然后再将各结点按编号存入数组。	节省存储空间。	无法根据结点间的下标关系确定它们之间的逻辑关系，从而难以实现二叉树求父、子结点等基本运算。
方式二：先增设虚拟节点，将其转为一棵完全二叉树，然后再按层编号存入数组。	方便实现二叉树求父、子结点等基本运算。	浪费存储空间。

非完全二叉树的顺序存储

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

当我们讲到堆和堆排序的时候，你会发现，堆其实就是一种完全二叉树，最常用的存储方式就是数组。

链式存储结构

二叉树有不同的链式存储结构，其中最常用的是二叉链表和三叉链表，其结点形式如下图：

二叉链表和三叉链表的结点形式

二叉树的两种链式存储结构如下图：

二叉树的链式存储结构

其中，判断叶子结点的条件为：(p->lchild == NULL) && (p->rchild == NULL)。

基本运算

树常见的基本运算如下：

初始化（Init）
建树（Create）
插入、删除结点
求根（Root）
求双亲（Parent）
求孩子（Child）
- 二叉树求左孩子（Lchild）
- 二叉树求右孩子（Rchild）
遍历（Traverse）
- 二叉树先序遍历（PreOrderTraverse）
- 二叉树中序遍历（InOrderTraverse）
- 二叉树后序遍历（PostOrderTraverse）
- 层次遍历（LevelOrder）：从上往下逐层遍历，同一层中结点从左往右

遍历

https://en.wikipedia.org/wiki/Tree_traversal

已知二叉树，求遍历序列

二叉树的遍历（traversing binary tree），是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问有且仅被访问一次。

二叉树的遍历，有三种经典方式：

经典的三种遍历方式	遍历顺序	推导
先序遍历	DLR	首先访问父节点，因此先序序列的第一个结点必为根节点（如下图先序遍历 A）
中序遍历	LDR	先于根结点的为左子树，后于根结点的为右子树
后序遍历	LRD	最后访问父节点，因此后序序列的最后一个结点必为根节点（如下图后序遍历 A）

已知二叉树，求三种遍历序列：

二叉树遍历

归纳：

若一棵非空二叉树的先序序列和后序序列相同，则该二叉树中只有一个根节点。
若一棵具有 n (n>0) 个结点的二叉树的先序序列和后序序列正好相反，则该二叉树一定是：高度为 n 的二叉树。
若一棵二叉树的先序序列和中序序列正好相反，则二叉树上每个结点的右子树都是空二叉树。

已知遍历序列，求二叉树

由二叉树的遍历可知，任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。已知先序或后序序列 + 中序序列，可以确定一棵二叉树：

问题：

假设一棵二叉树的中序序列与后序序列分别为：BACDEFGH 和 BCAEDGHF，建立该二叉树。

分析：

二叉树恢复

二叉树遍历的实现方式

递归实现
非递归实现（栈）

多叉树

B-tree

B-tree 的阶（Order），来自 Knuth (1998) 的定义：

Knuth (1998) defining the order to be maximum number of children (which is one more than the maximum number of keys).

所以按照 Knuth 定义一棵 m 阶的 B 树（国内教材所用的定义）：

Every node has at most m children.

每个节点最多有 m 个孩子。

Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.

非叶非根节点至少有 [m/2] 个儿子。[m/2] 表示取大于 m/2 的最小整数。

The root has at least two children if it is not a leaf node.

根节点至少有 2 个儿子。除非它本身是叶子节点，即整棵树只有它一个节点。

A non-leaf node with k children contains k − 1 keys.

非叶节点：有 k 个儿子，就有 k-1 个 keys。

All leaves appear in the same level and carry no information.

所有叶子节点在同一层，不携带信息 data。

例如一棵 3 阶 B 树，高度相比二叉树会更低。

B+ Tree

特性：

非叶子节点存储索引；
叶子节点存储数据，且通过双向链表关联。

为什么用？

为了减少内存开销和磁盘 IO

B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就可以存储更多的键值，相应的树的阶数就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数会再次减少，数据查询的效率也会更快。另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。
为了支持区间查找

因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，叶子节点间通过双向链表连接。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。

树和森林

https://en.wikipedia.org/wiki/Tree_structure

逻辑结构

无回路的连通图（Connected Graph）即为树。

存储结构

森林（Forest）：n 棵互不相交的树的集合。

A set of n ≥ 0 disjoint trees.

LC-RS Representation

https://blog.csdn.net/chengyq116/article/details/112342319

https://slidetodoc.com/left-childright-sibling-representation-instructor-prof-jyhshing-roger/

Parent Representation

List Representation

树的应用

分类算法

哈夫曼树（最优二叉树）

https://en.wikipedia.org/wiki/Huffman_tree

哈夫曼树的性质：

哈夫曼树中，不存在度数为 1 的分支结点。
若度数为 0 的叶子结点个数为 $n_0$，则哈夫曼树共有 $2n_0 - 1$ 个结点。
若度数为 2 的结点个数为 $n_2$，则哈夫曼树共有 $2(n_2 + 1) - 1$ 个结点。

《灵光一现的创造霍夫曼编码》

【霍夫曼编码原理文本压缩、ZIP压缩文件原理 Huffman Encoding by Tom Scott-哔哩哔哩】 https://b23.tv/wFatkFc

【Huffman 编码动画演示】 https://www.bilibili.com/video/BV18V411v7px/

查找

二叉查找树（Binary Search Tree, BST）

中序遍历时从小到大的二叉树。

平衡二叉查找树（Balanced Binary Search Tree, BBST）

排序

堆排序（Heap）

《28 | 堆和堆排序：为什么说堆排序没有快速排序快？》

《29 | 堆的应用：如何快速获取到 Top 10 最热门的搜索关键词？》

参考

Tree (data structure)

Binary tree
- Binary search tree
  - Self-balancing binary search tree
B-tree

B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.[2]Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as disks. It is commonly used in databases and file systems.
- B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.
  
  The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,[1] typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
- 2–3 tree is a B–tree of order 3.
- 2–3–4 tree is a B–tree of order 4.
R-tree，R 树是 B 树向多维空间发展的另一种形式

《23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？》

《24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？》

《48 | B+树：MySQL数据库索引是如何实现的？》

《AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？》

《Implementing a Binary Tree in Java | Baeldung》

数据结构系列（二）线性结构总结

发表于 2024-05-03 更新于 2024-12-11

线性结构

数组

线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻按关系决定它们在存储空间中的存储位置，即：逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。因此，数组可以看成线性表的一种推广。

一维数组

存储结构

一维数组又称向量（Vector），它由一组具有相同类型的数据元素组成，并存储在一组连续的存储单元中。其存储结构如下图：

顺序表

基本运算

对于可变长数组（Resizable Array）的插入、删除操作，其元素移动情况如下：

	元素移动次数（n 为数组大小, i 为操作位置）	平均移动次数	时间复杂度
插入	$n-i+1$ 次	$n/2$ 次	`O(n)`
删除	$n-i$ 次	$(n-1)/2$ 次	`O(n)`

顺序表操作

二维数组

若一维数组中的数据元素又是一维数组结构，则称为二维数组，以此类推。一般地，一个 n 维数组可以看成元素为 n-1 维数组的线性表。

二维数组的地址计算（行优先）如下：

$$
loc[i,\ j]=loc[0,\ 0]+(n*i+j)*k
$$

其中，$i$ 为行坐标，$j$ 为列坐标，$n$ 为总列数，$k$ 为存储单元。

由公式可知，数组元素的存储位置是下标的线性函数。

矩阵（Matrix）是很多科学计算问题研究的对象，矩阵可以用二维数组来表示。

在数值分析中经常出现一些高阶矩阵，这些高阶矩阵中有许多值相同的元素或者零元素，如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。矩阵的非零元素个数很少的矩阵称为稀疏矩阵。

为了节省存储空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。

链表

存储结构

四种链表对比：

四种链表	非循环	循环（Cycle）
单向（Singly）	单向链表	单向循环链表
双向（Doubly）	双向链表	双向循环链表

其中，是否循环的关键代码差异如下：

关键代码	非循环链表	循环链表
判断是否空链表	`head->next == NULL`	`head->next == head`
判断是否尾结点	`p->next == NULL`	`p->next == head`

四种链表对比

基本运算

单链表插入（insert p before i）、删除（delete i）结点操作如下：

// 单链表需要先找到 i - 1 结点以便进行插入、删除操作
q = get(i - 1);

// 插入结点（注意操作顺序：先新再旧）
p->next = q->next;
q->next = p;

// 删除结点
p = q->next;
q->next = p->next;
free(p);

注意：等号左边是指针，等号右边是结点。

单链表操作

双向循环链表插入（insert p after i）、删除（delete i）结点操作如下：

// 双向循环链表直接获取 i 结点即可，因为可以通过其前驱、后继指针直接进行插入、删除操作
q = get(i);

// 插入结点（注意操作顺序）
p->prev = q;
p->next = q->next;
q->next->prev = p;
q->next = p;

// 删除结点（注意操作顺序）
q->prev->next = q->next;
q->next->prev = q->prev;
free(q);

注意：等号左边是指针，等号右边是结点

双向循环链表操作

栈

顺序存储结构

链式存储结构

基本运算

使用场景

队列

顺序存储结构

链式存储结构

基本运算

使用场景

数据结构系列（一）概论总结

发表于 2024-05-01 更新于 2024-12-11

引言

计算机解决一个具体问题时，一般需要经过以下几个步骤：

从具体的问题抽象出一个适当的数学模型；什么是数学模型呢？数学模型常常是现实世界的一个简化，是抽取对象的本质特性构造出来的。尽管数学是一门精准的科学，但是我们建立数学模型却要从实际出发，要针对问题做必要简化，简化的标准有两个：够用、易解。
设计一个求解该数学模型的算法；
用某种计算机编程语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解。

计算机解决问题的步骤

基本概念和术语

data_structure

数据：所有被计算机存储、处理的对象。
数据对象：是性质相同的数据元素的集合，是数据的子集。
数据元素：数据的基本单位，也是运算的基本单位。例如在数据库中，又称为记录（Record）/元组（Tuple）。
数据项：数据不可分割的最小单位。例如在数据库中，又称为字段（Field）/域（Domain）。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。它包括：
- 数据的逻辑结构
- 数据的存储结构
- 数据的基本运算

逻辑结构

https://en.wikipedia.org/wiki/Abstract_data_type

集合结构

任意两个结点之间都没有邻接关系，组织形式松散：

集合结构

集合的三大特性：

确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。
互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集，其中的元素允许出现多次。
无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序。

集合之间可以进行运算：

数学符号	含义	英文
∩	交	Intersection
∪	并	Union
−	差	Difference

线性结构

顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

线性结构

特征：

排队（1:1）
起始节点无直接前驱
终端节点无直接后继
中间节点都有直接前驱和直接后继

树形结构

父子（1:N）

树形结构的相关术语

有没有想过为啥只有二叉树，而没有一叉树？实际上链表就是特殊的树，即一叉树。

图结构

地图（N:M）

图结构

存储结构

数据的逻辑结构在计算机中的实现，称为数据的存储结构（或物理结构）。

一般情况下，一个存储结构包括以下两个部分：

存储数据元素本身
数据元素之间的关联方式

逻辑结构常见的存储结构实现如下：

	顺序存储方式	链式存储方式	散列存储方式
集合结构			散列表（Hash Table）
线性结构	数组（一维、二维）顺序栈循环队列（取余运算）	链表（单向/双向、是否循环）链栈链队列
树形结构 (二叉树)	一维数组满二叉树完全二叉树非完全二叉树（需增设虚拟结点转为完全二叉树）	链表二叉链表三叉链表
树形结构 (树)	双亲表示法（一维数组）	孩子链表表示法（一维数组 + 单链表）孩子兄弟表示法（二叉链表，LC-RS）
图结构	邻接矩阵（二维数组）	邻接表（一维数组 + 单链表）

顺序存储方式

所有存储结点存放在一个连续的存储区中。利用结点在存储区中的相对位置来表示数据元素之间的逻辑关系。

链式存储方式

每个存储结点除了含有一个数据元素之外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点。利用指针表示数据元素之间的逻辑关系。

散列存储方式

散列表（Hash Table）。

索引存储方式

基本运算

基本运算，是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。一般而言，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：等。

建立（Init）
读取（Access）
查找（Search）
插入（Insert）
删除（Delete）

算法

定义：一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能在有限时间内被求解。

算法分析：

正确性
易读性
健壮性
时空性

时间复杂度

空间复杂度

常用数据结构

data_structure

参考

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

https://www.bigocheatsheet.com

https://the-algorithms.com/

数据结构与算法教程 C 语言版教程

Techie Delight

Homebrew 包管理器总结

发表于 2024-02-01 更新于 2024-12-11

参考文档：https://brew.sh/

安装目录：/usr/local/Cellar

Homebrew

terminology

Cask 通常用于安装一些带有图形界面的应用程序。
Formulae 则是用于安装命令行工具和软件包的规则和脚本。

cask

常用的 cask：

$ brew install --cask iterm2
$ brew install --cask windterm
$ brew install --cask redisinsight
$ brew install --cask oss-browser
$ brew install --cask sourcetree

$ brew install --cask typora
$ brew install --cask xmind
$ brew install --cask evernote

formula

常用的 formula：

$ brew install coreutils

$ brew install node

$ brew install nginx
$ brew install mysql
$ brew install redis
$ brew install elasticsearch
$ brew install zookeeper
$ brew install prometheus
$ brew install grafana

$ brew install ffmpeg
$ brew install imagemagick

$ brew install wireshark

tap

MongoDB

https://www.mongodb.com/zh-cn/docs/manual/tutorial/install-mongodb-on-os-x/

https://github.com/mongodb/homebrew-brew

1	$ brew tap mongodb/brew

services

例子

$ brew services start mysql@8.4
$ brew services start redis
$ brew services start mongodb-community
$ brew services start grafana

国内加速

《Homebrew 国内如何自动安装？》

Homebrew 源替换为 USTC 镜像：http://mirrors.ustc.edu.cn/help/brew.git.html

Homebrew 关闭自动更新：https://github.com/Homebrew/homebrew-autoupdate

1	export HOMEBREW_NO_AUTO_UPDATE="1"

参考

传输层常用工具总结——netstat、ss、lsof

发表于 2023-12-12 更新于 2024-12-11

ss

https://man7.org/linux/man-pages/man8/ss.8.html

1 2	ss [options] [ FILTER ] 其中，FILTER := [ state STATE-FILTER ] [ EXPRESSION ]

例子

# 列出当前 socket 统计信息
$ ss -s

# 显示所有已建立（established）的 HTTP、SMTP、SSH 连接
$ ss -o state established '( dport = :http or sport = :http )'
$ ss -o state established '( dport = :smtp or sport = :smtp )'
$ ss -o state established '( dport = :ssh or sport = :ssh )'

# 找出所有连接 X 服务器的进程
$ ss -x src /tmp/.X11-unix/*

# 统计指定进程 TCP 连接占用的端口
$ ss -tanp | grep 7059 | tr -s ' '  | cut -d ' ' -f 4 | sort -n | uniq -c

# 统计指定进程 TCP 连接状态
$ ss -tanp | grep 7059 | tr -s ' '  | cut -d ' ' -f 1 | sort -n | uniq -c

# 统计已建立 TCP 连接的 IP 数量
$ ss -tnp | grep 7059 | awk '{print $5}' | sort -n | uniq -c

`ss`、`netstat`、`lsof` 命令的输出结果对比

netstat 是遍历 /proc 下面每个 PID 目录；

ss 直接读 /proc/net 下面的统计信息。所以 ss 执行的时候消耗资源以及消耗的时间都比 netstat 少很多。

输出结果对比

netstat

https://en.wikipedia.org/wiki/Netstat

https://linux.die.net/man/8/netstat

《每天学一个 Linux 命令（65）：netstat》

例子

Linux 端口占用统计

1	$ netstat -tanp \| grep 7059 \| tr -s ' ' \| cut -d ' ' -f 4 \| sort -n \| uniq -c

Mac 端口占用查询

1	$ netstat -anv \| grep 7059

Windows 端口占用查询

# 查询占用了 8080 端口的[进程号]（最后一列）
$ netstat -ano|findstr "8080"

# 找到[进程号]对应的[进程名称]
$ tasklist|findstr 7059

# 根据[进程名称]杀死进程
$ taskkill /f /t /im /javaw.exe

lsof

https://en.wikipedia.org/wiki/Lsof

https://linux.die.net/man/8/lsof

常用选项：

选项	描述
-n	不显示主机名（host name），显示 IP（network number）。例如 localhost 显示为 127.0.0.1
-P	不显示端口名（port name），显示端口号（port number）。例如 cslistener 显示为 9000
-a	AND 运算
-p s	筛选指定 PID
-i […]	筛选指定条件，例如：TCP + 端口号
-s [p:s]	筛选指定条件：例如：TCP (LISTEN)

-i [46][protocol][@hostname|hostaddr][:service|port]

where:

46 specifies the IP version, IPv4 or IPv6 that applies to the following address. ‘6‘ may be be specified only if the UNIX dialect supports IPv6. If neither ‘4‘ nor ‘6‘ is specified, the following address applies to all IP versions.

protocol is a protocol name - TCP, UDP

hostname is an Internet host name. Unless a specific IP version is specified, open network files associated with host names of all versions will be selected.

hostaddr is a numeric Internet IPv4 address in dot form; or an IPv6 numeric address in colon form, enclosed in brackets, if the UNIX dialect supports IPv6. When an IP version is selected, only its numeric addresses may be specified.

service is an /etc/services name - e.g., smtp or a list of them.

port is a port number, or a list of them.

Here are some sample addresses:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-i6 - IPv6 only

-iTCP:25 - TCP and port 25

-i@1.2.3.4 - Internet IPv4 host address 1.2.3.4

-i@[3ffe:1ebc::1]:1234 - Internet IPv6 host address 3ffe:1ebc::1, port 1234

-iUDP:who - UDP who service port

-iTCP@lsof.itap:513 - TCP, port 513 and host name lsof.itap

-iTCP@foo:1-10,smtp,99 - TCP, ports 1 through 10, service name smtp, port 99, host name foo

-iTCP@bar:1-smtp - TCP, ports 1 through smtp, host bar

-i:time - either TCP, UDP or UDPLITE time service port

-s [p:s]

When followed by a protocol name (p), either TCP or UDP, a colon (‘:’) and a comma-separated protocol state name list, the option causes open TCP and UDP files to be

excluded if their state name(s) are in the list (s) preceded by a ‘^’;

or

included if their state name(s) are not preceded by a ‘^’.

For example, to list only network files with TCP state LISTEN, use:
1
-iTCP -sTCP:LISTEN
State names vary with UNIX dialects, so it’s not possible to provide a complete list. Some common TCP state names are: CLOSED, IDLE, BOUND, LISTEN, ESTABLISHED, SYN_SENT, SYN_RCDV, ESTABLISHED, CLOSE_WAIT, FIN_WAIT1, CLOSING, LAST_ACK, FIN_WAIT_2, and TIME_WAIT.

例子

查询端口占用

# 筛选条件：端口号
$ lsof -nP -i:端口号

# 筛选条件：端口号 + TCP 协议
$ lsof -nP -iTCP:端口号

# 筛选条件：端口号 + TCP 协议 + LISTEN 状态
$ lsof -nP -iTCP:端口号 -sTCP:LISTEN

按 PID 查询

# 查看某个进程的 open files，等价于 /proc/PID/fd/
$ lsof -nP -p PID

# 按 TCP + 端口号 + PID 查询
$ lsof -nP -iTCP:端口号 -a -p PID

# 按 TCP (LISTEN) + PID 查询
$ lsof -nP -iTCP -sTCP:LISTEN -a -p PID

COMMAND  PID    USER   FD   TYPE     DEVICE SIZE/OFF NODE NAME
java    6276    dev   36u  IPv4 1097042515      0t0  TCP *:8720 (LISTEN)
java    6276    dev  150u  IPv4 1097044387      0t0  TCP *:8171 (LISTEN)
java    6276    dev  187u  IPv4 1097042576      0t0  TCP *:58077 (LISTEN)
java    6276    dev  202u  IPv4 1097042587      0t0  TCP *:8062 (LISTEN)

lsof 输出结果每一列的含义：

COMMAND：进程的名称
PID：进程标识符
USER：进程所有者
FD：文件描述符，应用程序通过文件描述符识别该文件。如 cwd、txt 等
TYPE：文件类型，如 DIR、REG 等
DEVICE：指定磁盘的名称
SIZE：文件的大小
NODE：索引节点（文件在磁盘上的标识〉
NAME：打开文件的确切名称

lsof 例子

参考

《Linux 端口占用查询——netstat、ss、lsof | 良许 Linux》

位运算及使用场景总结

发表于 2023-11-07 更新于 2024-12-11

	二进制位运算	十进制运算
`&` 按位与（AND）	$M\&(n-1)$	$M \bmod n$
`\|` 按位或（OR）
`~` 按位非（NOT）
`^` 按位异或（XOR）
`<<` 左位移（LEFT SHIFT）	$M<<n$	$M*2^n$
`>>` 右位移（RIGHT SHIFT）	$M>>n$	$M/2^n$
`>>>` 无符号右移

https://en.wikipedia.org/wiki/Mask_(computing)

Using a mask (bitmask) can be set

either on or off,

or inverted from on to off (or vice versa)

in a single bitwise operation.

Common bitmask functions

「按位与 `&`」的使用场景

求子网地址

求子网地址（主机地址与子网掩码做按位与运算），参考：

例子：

Calculate subnet address

实现循环队列

编程的时候，很多时候都会要求一个数在某一个范围内进行反复循环，例如实现循环队列。如果使用 if 语句，当判断达到最大值的时候回到开始处，效率较低。是否有更简单更高效的方法？

& 按位与（AND）。比如说我想让一个数在 0-7 内循环，该如何做呢？temp = (temp++)&0x07，如此就简单的实现了 0-7 循环。因为要实现 0-7 的循环，其实只要提取一个变量递增的低三位即可。不管这个变量如何变化，它的低三位始终都是在 0-7 循环变化的。同理，它也可以实现 0-15、0-31 变化。但是这个方法有局限，它只能按照连续 bit 位的最大值进行循环。
% 取余运算（Modulo），它不存在上述限制。可以在 0-任意数循环。比如 0-5 循环，只要 temp = (temp++)%6（注意是 6 而不是 5），那么 temp 就会在 0-5 之间循环了。

「按位或 `|`」的使用场景

单个变量保存多个值，节省存储空间

DragonPay

雪花算法的拼接

     timestamp << TIMESTAMP_SHIFT
| dataCenterNo << DATA_CENTER_NO_SHIFT
    | workerNo << WORKER_NO_SHIFT
       | seqNo << SEQ_NO_SHIFT
         | ext

线程池的成员属性 `ctl`

线程池的成员属性 ctl，高 3 位表示 runState，低 29 位表示 workerCnt（按位或运算 bitwise OR）：

runState workerCnt                       runState workerCnt
     000 00000000000000000000000000000   SHUTDOWN empty
‭‭     001 00000000000000000000000000000       STOP empty
     010 00000000000000000000000000000    TIDYING empty
     ‭011 00000000000000000000000000000‬ TERMINATED empty
     111 00000000000000000000000000000    RUNNING empty
‭     111 11111111111111111111111111111    RUNNING full

操作系统 - 分页存储管理 - 逻辑地址结构

若用 $m$ 位表示逻辑地址，页大小为 $2^n$ 字节，则低 $n$ 位表示「页内偏移量」，高 $m-n$ 位表示「页号」。
例如 32 位的逻辑地址中，页大小为 $2^{12}$ (4KB)，则低 12 位表示「页内偏移量」，高 20 位表示「页号」。即：可用内存为「页号量 $2^{20}$」×「页大小 $2^{12}$ B」=「$2^{32}$ B」=「4 GB」

paging address structure

`epoll_ctl()` 的 `event` 参数

EPOLLIN | EPOLLOUT | EPOLLRDHUP | EPOLLPRI | EPOLLERR | EPOLLHUP | EPOLLET | EPOLLONESHOT

event.events = EPOLLIN | EPOLLET;
epoll_ctl (efd, EPOLL_CTL_ADD, sfd, &event);

TCP - Header Format - Flags

Unix-like permissions

chmod、umask

Unix-like permissions

「按位异或 `^`」的使用场景

《异或运算 XOR 使用场景 | 阮一峰》

前向纠错（FEC)）

TCP 协议实现可靠数据传输的 5 种措施中之一——差错控制，有两种纠错方案：

Automatic repeat request (ARQ) 丢包重传
Forward error correction (FEC) 前向纠错

其中 FEC 的实质就是按位异或运算：

FEC

参考：https://www.jianshu.com/p/6157e120ef99

求 hash 值

求 hash 值使用了：

>>> 无符号右移
^ 按位异或
& 按位与

int hash(Object key) {
    int h = key.hashCode();
    h = h ^ (h >>> 16);
    return h & (capitity - 1); //capicity 表示散列表的大小
}

位移

逻辑右移可以处理除数为任意二的幂的除法，即：$M>>n$ 等于 $M/2^n$

更一般地，在特定底数 Base 的进位制中，除数（或分母）为任意 $Base^n$ 的除法（n 为整数）皆可以透过将数字位数向右移 n 位来完成。例如除以十：

$M/Base^n$	Base 2	Base 8	Base 10	Base 16
230 / 2 = 115	1110 0110 / 10 = 111 0011
230 / 8 = 28		346 / 10 = 34
230 / 10 = 23			230 / 10 = 23
230 / 16 = 14				0xE6 / 10 = 0xE

参考

https://en.wikipedia.org/wiki/Bit

https://en.wikipedia.org/wiki/Bitwise_operation

https://en.wikipedia.org/wiki/Bit_array

https://dev.mysql.com/doc/refman/5.7/en/bit-functions.html

《计算机中有哪些令人拍案叫绝的设计？ | 良许 Linux》

《C 语言”位运算”有哪些奇特技巧？》

传输层 TCP 协议保活机制总结（TCP 长连接）

发表于 2023-05-25 更新于 2024-12-11

什么是 TCP keepalive?

The keepalive concept is very simple: when you set up a TCP connection, you associate a set of timers.

为什么使用 TCP keepalive ?

TCP 是一个基于连接的协议，其连接状态是由一个状态机进行维护，连接完毕后，双方都会处于 established 状态，默认情况下，这之后的状态并不会主动进行变化。这意味着如果上层不进行任何调用，一直使 TCP 连接空闲，那么这个连接虽然没有任何数据，但仍然保持连接状态，一天、一星期、甚至一个月，即使在这期间：

对端主机系统奔溃
中间路由原因（如奔溃重启、NAT 转换表移除该记录）

TCP keepalive 的两个目标

Checking for dead peers

 _____                                                     _____ 
|     |                                                   |     | 
|  A  |                                                   |  B  | 
|_____|                                                   |_____| 
   ^                                                         ^ 
   |--->--->--->-------------- SYN -------------->--->--->---| 
   |---<---<---<------------ SYN/ACK ------------<---<---<---| 
   |--->--->--->-------------- ACK -------------->--->--->---| 
   |                                                         | 
   |                                       system crash ---> X 
   | 
   |                                     system restart ---> ^ 
   |                                                         | 
   |--->--->--->-------------- PSH -------------->--->--->---| 
   |---<---<---<-------------- RST --------------<---<---<---| 
   |                                                         |

Preventing disconnection due to network inactivity

 _____           _____                                     _____ 
|     |         |     |                                   |     | 
|  A  |         | NAT |                                   |  B  | 
|_____|         |_____|                                   |_____| 
   ^               ^                                         ^ 
   |--->--->--->---|----------- SYN ------------->--->--->---| 
   |---<---<---<---|--------- SYN/ACK -----------<---<---<---| 
   |--->--->--->---|----------- ACK ------------->--->--->---| 
   |               |                                         | 
   |               | <--- connection deleted from NAT table  | 
   |               |                                         | 
   |--->- PSH ->---| <--- invalid connection                 | 
   |               |                                         |

Linux 使用 TCP keepalive

Linux 有内置的 keepalive 支持，配置如下：

$ cat /proc/sys/net/ipv4/tcp_keepalive_time 
7200 
$ cat /proc/sys/net/ipv4/tcp_keepalive_probes 
9 
$ cat /proc/sys/net/ipv4/tcp_keepalive_intvl 
75 

$ sysctl -a | grep keepalive 
net.ipv4.tcp_keepalive_time = 7200 
net.ipv4.tcp_keepalive_probes = 9 
net.ipv4.tcp_keepalive_intvl = 75

# 查看 TCP 协议的一些描述和参数定义（man 命令使用手册共 9 章，TCP 的帮助手册位于第 7 章）
$ man tcp
$ man 7 tcp

上述参数表示：默认情况下一条 TCP 连接在 2 小时（7200 秒）都没有报文交换后，会开始进行保活探测，若再经过 9*75 秒 = 11 分钟 15 秒的循环探测都未收到探测响应（即共计：2 小时 11 分钟 15 秒），就会自动断开 TCP 连接。

在探测过程中，对方主机会处于以下四种状态之一：

状态	处理方式
对方主机仍在工作，并且可达	TCP 连接正常，将 keepalive 计时器重置
对方主机崩溃，并且已经重启	重启后原连接已失效，对方主机由于不认识探测报文，会响应重置报文段（RST）	TCP 连接断开重连
对方主机已崩溃（已关机或者正在重启）	TCP 连接不正常，请求端经过指定次数的探测依然没得到响应	TCP 连接断开重连
对方主机仍在工作，但由于网络原因不可达	TCP 连接不正常，请求端经过指定次数的探测依然没得到响应	TCP 连接断开重连

应用程序使用 TCP keepalive

TCP keepalive configuration

参考

《TCP/IP 详解卷 1: 协议》第二版，第 17 章：TCP Keepalive 保活机制》

https://tldp.org/HOWTO/TCP-Keepalive-HOWTO/index.html

https://en.wikipedia.org/wiki/Keepalive

https://linux.die.net/man/7/tcp

《HTTP 长连接和 TCP 长连接有区别？图解》

《HTTP keep-alive 和 TCP keepalive 的区别，你了解吗？》

逻辑结构

图的种类

无向图（Undirected Graph）

有向图（Directed Graph）

带权图（Weighted Graph）

图的相关术语

存储结构

邻接矩阵（Adjacency Matrix）

对称矩阵（Symmetric Matrix）

三角矩阵（Triangular Matrix）

稀疏矩阵（Sparse Matrix）

邻接表（Adjacency List）

图的应用

图的搜索（遍历）

深度优先搜索（DFS）

广度优先搜索（BFS）

连通分量

最小生成树问题（MST problem）

Prim 算法

Kruskal 算法（加边法）

最短路径问题（Shortest path problem）

回溯算法

Dijkstra 算法

A* 算法

最大流问题（Maximum flow problem）

拓扑排序（Topological sorting）

社交网络（Social network）

知识图谱（Knowledge graph）

参考

相关术语

一叉树

二叉树

逻辑结构

满二叉树（Full Binary Tree）

完全二叉树（Complete Binary Tree）

存储结构

顺序存储结构

链式存储结构

基本运算

遍历

已知二叉树，求遍历序列

已知遍历序列，求二叉树

二叉树遍历的实现方式

多叉树

B-tree

B+ Tree

树和森林

逻辑结构

存储结构

树的应用

分类算法

哈夫曼树（最优二叉树）

查找

二叉查找树（Binary Search Tree, BST）

平衡二叉查找树（Balanced Binary Search Tree, BBST）

排序

堆排序（Heap）

参考

数组

一维数组

存储结构

基本运算

二维数组

链表

存储结构

基本运算

栈

顺序存储结构

链式存储结构

基本运算

使用场景

队列

顺序存储结构

链式存储结构

基本运算

使用场景

引言

基本概念和术语

逻辑结构

集合结构

`ss`、`netstat`、`lsof` 命令的输出结果对比

「按位与 `&`」的使用场景

「按位或 `|`」的使用场景

线程池的成员属性 `ctl`

`epoll_ctl()` 的 `event` 参数

「按位异或 `^`」的使用场景