相似性检索

相似性检索：从指定目标集合中检索出与给定样本相似的目标

• range searches：范围检索，给定查询点、检索距离阈值
• K-neighbor searches：K近邻检索，给定查询点、检索结果 数量

• 待检索目标、样本：以指定feature space中的高维数据点 表示

• 相似性检索则在相应metric space中搜索样本点最近邻作为 检索结果

• 关键：对待检索的目标建立有效的相似性索引

  • 对待检索目标进行预划分，在对给定样本进行检索时，只需 对比相似索引中给出的可能相似的目标
  • 减少相似性检索的对比次数、I/O，让相似性检索在大规模 数据集中应用成为可能

Tree-Based Index

基于树结构的索引

• 向量维度大于20之后，仍然需要扫描整个向量集合的大部分， 与线性扫描没有太大差别

• 包括

  • kd-tree
  • R-tree
  • R*-tree
  • X-tree
  • SS-tree
  • SR-tree
  • VP-tree
  • metric-trees

Hasing-Based Index

基于哈希的索引技术：利用LSH函数简化搜索

• locality sensitive hashing：LSH，局部敏感哈希，特征 向量越接近，哈希后值越可能相同

  • 局部敏感哈希值能够代表代替原始数据比较相似性
  • 支持对原始特征向量进行非精确匹配

• hash技术能从两个方面简化高维数据搜索

  • 提取特征、减小特征维度

    • 在损失信息较小的情况下对数据进行降维
    • hash函数（特征提取方法）选择依赖于对问题认识
    • 一般都归于特征提取范畴

  • 划分特征空间（哈希桶）、缩小搜索空间

    • 将高维特征映射到1维先进行近似搜索得到候选集， 然后在候选集中进行精确搜索
    • hash函数的选择取决于原始特征表示、度量空间
    • 一般LSH都是指此类哈希技术

提取特征

• average hashing：aHash，平均哈希
• perceptual hashing：pHash，感知哈希
• differantiate hashing：dHash，差异哈希

划分空间

• MinHashing：最小值哈希，基于Jaccard系数
• 基于汉明距离的LSH
• 基于曼哈顿距离的LSH
• Exact Euclidean LSH：E2LSH，基于欧式距离

Visual Words Based Inverted Index

向量化方法：将向量映射为标量，为（图像）特征建立 visual vocabulary

• 基于K-means聚类（层级K-means、近似K-means）
• 在图像检索实际问题中取得了一定成功
• K-means聚类算法的复杂度与图像特征数量、聚类数量有关
  • 图像规模打达到百万级时，索引、匹配时间复杂度依然较高

• visual vocabulary：视觉词库，代表聚类类别整体
• visual word：视觉单词，每个代表一个聚类类别

总述

• 二叉查找树：最基础的查找树，但是不平衡时效率很差
• 自平衡查找树：使用旋转技术得到平衡二叉树
• 多路查找树：使用多叉树达到平衡

• 树高度一般即决定其查找、插入、删除效率
• 以代码复杂性、插入节点时间代价，换取查询时$logN$性能

Self-Balancing Binary Tree

自平衡查找树：如果节点插入、删除产生了一棵违背平衡要求的树， 就从称为旋转的一系列特定变换中选择一种，重新构造树使得 树满足平衡要求

• 不同的对平衡的定义产生了不同的实现
• 这种方案属于变治法中实例化简

Balance Factor

平衡因子：节点左、右子树高度差（一般右树-左数）

• AVL树中平衡情况下节点平衡因子只能为-1、+1、0

• 更新节点后可能存在不平衡节点，其平衡因子可能变为-2、+2

• 平衡因子也可以被定义为左右子树叶子数

Rotation

旋转需要使得二叉树平衡时，保证二叉树依然有序

• 左旋：节点平衡因子符号为正，即右子树高于左子树

  • 节点T下沉为其右儿子R的左儿子
  • 如果右儿子R本身有左子树RL，则左子树RL成为节点T 新右子树

• 右旋：节点平衡因子符号为负，即左子树高于右子树，

  • 节点T下沉为其左儿子L的右儿子
  • 如果左儿子L本身有右子树LR，则右子树LR成为节点T 新左子树

• 旋转只涉参与选择的至多3个节点指针变化，其余节点状态保持
• “旋转”行为确实类似：节点绕其子节点旋转，子节点旋转后上浮 成为父节点
• 参与旋转的两个节点也称为轴

分类

• AVL树
• 红黑树
• 分裂树

Multiway Search Tree

多路查找树：允许查找树中单个节点中不止包含一个元素

• 二叉查找树的推广，用于磁盘超大数据集的高效存取
• 此方案属于变治法中改变表现

分类

• 2-3树
• 2-4树
• B树
• B+树

Binary Search Tree

二叉查找树：分配给每个父母顶点的数字都比其左子树中数字大， 比右子树数字小

• 二叉树有序，保证二叉树能够快速找到中间元素，从而支持 二分查找

特点

• 对于n个顶点的二叉树，满足 $ \lfloor {log_{2}^{n}} \rfloor \leq h \leq n-1 $

• 二叉查找树的查找算法效率取决于二叉树的高度

  • 平均情况下，查找、插入、删除时间$\in Theta(logn)$

  • 最差情况下（严重不平衡的树，接近链表结构），树高度 h接近节点数n，查找、插入、删除时间$\in Theta(n)$

• 包含n个键的二叉查找树总数量 $c(n) = \frac 1 {n+1} C_{2n}^n, c(0)=1$

应用

• 查找

操作

查找

在给定二叉查找树中查找给定键值K

• 如果树为空，查找失败

• 若树不为空，将查找键K和树根节点K(r)比较

  • 相等则查找停止
  • $K < K(r)$：在左子树中继续查找
  • $K > K(r)$：在右子树中继续查找

特点

• 算法时间效率
  • 最差情况下，二叉树完全偏斜，需要进行n次比较
  • 随机情况下，查找n个随机键构造的二叉树比较次数$2logn$

插入

除非是空树，否则总是把新键K插入叶子节点中

• 通过查找K确定合适插入位置（叶子节点）
• 若K大于叶子节点键值，则作为右子女，否则作为左子女

最优二叉查找树

对集合中元素确定的查找概率，成功查找的平均比较次数最小的 二叉查找树（可以扩展到包含不成功查找）

• $a_i, i=1,2,\cdots,n$：从小到大互不相等的键
• $p_i, i=1,2,\cdots,n$：键查找概率
• $T_i^j$：由键$a_i, \cdots, a_j$构成的二叉树
• $C(i, j)$：成功查找的最小平均查找次数

动态规划构造

• 根据最优化法则，最优二叉查找树左右子树均是最优排列的

• 二叉树$Ti^j$有序，设树根为$a_1$，$a_2,..,a{k-1}$构成 的左子树、$a_{k+1},..,a_j$构成右子树均是最优排列的

递推式如下

• $1 \leqslant i \leqslant j \leqslant n$

  $$\begin{align} C(i, j) & = \min_{i \leqslant k \leqslant j} \{p_k + \sum_{s=i}^{k-1} p_s * (a_s在T_i^{k-1}中层数 + 1) + \sum_{s=k+1}^j p_s * (a_s在T_{k+1}^j中层数 + 1) \}\\ & = \min_{i \leqslant k \leqslant j} \{ \sum_{s=i}^{k-1} p_s * a_s在T_i^{k-1}中层数 + \sum_{s=k+1}^j p_s * a_s在T_{k+1}^j中层数 + \sum_{s=i}^j p_s \} \\ & = \min_{i \leqslant k \leqslant j} \{C(i, k-1) + C(k+1, j)\} + \sum_{s=i}^j p_s \end{align}$$

• $1 \leqslant i \leqslant n+1, C(i, i-1)=0$：空树

• $1 \leqslant i \leqslant n, C(i, i)=p_i$：单节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

OptimalBST(P[1..n])
	// 动态规划法构建最优二叉查找树
	// 输入：P[1..n]n个键查找概率
	// 输出：在最优BST中查找成功的平均比较次数，最优BST子树根表
	for i = 1 to n do
		C[i, i-1] = 0
		C[i, i] = P[i]
		R[i, i] = i
	C[n+1, n] = 0
		// 初始化平均查找次数表、子树根表
	for d = 1 to n-1 do
		// d为二叉树节点数
		for i = 1 to n-d do
			// n-d是为了控制j的取值
			j = i + d
			minval = \infty
			for k = i to j do
				// 遍历设置二叉树根节点
				if C[i, k-1] + C[k+1, j] < minval
					minval = C[i, k-1] + C[k+1, j]
					kmin = k
			R[i, j] = kmin
			sum = P[i]
			for s=i+1 to j do
				sum += P[s]
			C[i, j] = minval + sum
	return C[1, n], R

算法特点

• 算法效率
  • 算法时间效率为立方级
  • 算法空间效率为平方级

AVL Tree

AVL树：要求其节点在左右子树高度差不能超过1的平衡二叉树

• 基本思想：总能通过一次简单的节点重排使树达到平衡

  • 如果树插入操作使得一棵AVL树失去平衡，利用旋转对树作 变换
  • 若有多个这样的节点，找出最靠近新插入的叶子节点不平衡 结点，然后旋转以该节点为根的子树

• AVL树高度h即为其查找、插入效率

  • 包含n个节点AVL树高度h满足 $\lfloor log_2 n \rfloor \leq h < 1.4405log_2(n+2) - 1.3277$

  • 最差情况下，操作效率$\in \Theta(logn)$

  • 平均而言，在n不是太小时，高度h平均为 $1.01log_2 n + 0.1$（几乎同折半查找有序数组）

• AVL树缺点（平衡代价），阻碍AVL树成为实现字典的标准结构

  • 需要频繁旋转
  • 维护树的节点平衡
  • 总体比较复杂

旋转

按照节点平衡符号进行旋转：+左旋、-右旋

• 单旋：不平衡节点、不平衡子节点不平衡因子符号相同

  • 全为+：不平衡节点左旋
  • 全为-：不平衡节点右旋

• 双旋：不平衡节点、不平衡子节点不平衡因子符号不同

  • 先旋转不平衡子节点
  • 再旋转不平衡节点

• 优先考虑最底层、不平衡节点

插入节点

AVL树插入关键：查找不平衡节点

• 节点中应有存储其平衡因子的实例变量
• 插入过程中经过每个节点返回当前节点子树深度是否变化
• 比较节点平衡因子、子节点深度变化返回值判断是否平衡

• 插入过程中查询的每个节点都有可能不平衡
• 自下而上返回深度变化情况，优先旋转最底层不平衡节点

4种插入情况

根据插入情况的不同，对最靠近新插入叶子节点的不平衡点T

LL

插入T左儿子L的左子树LL：平衡因子全-

• 即T到最底层叶节点（只可能有一个）的路径为LL（中间省略）
• R-rotation：右单转，对T做一次右旋即可平衡

RR

插入T右儿子R的右子树R：平衡因子全+

• 即T到最底层叶节点（只可能有一个）的路径为RR（中间省略）
• L-rotation：左单转，对T做一次左旋即可平衡

LR

插入T左儿子L的右子树R：平衡因子-+

• 即T到最底层叶节点（只可能有一个）的路径为LR（中间省略）
• LR-rotation：左右双转
  • 先对左儿子L做一次左旋，变成LL模式
  • 在LL模式下，再对T做一次右旋

RL

插入T右儿子R的左子树L：平衡因子+-

• 即T到最底层叶节点（只可能有一个）的路径为RL（中间省略）
• RL-rotation：右左双转
  • 先对右儿子R做一次右旋，变成RR模式
  • 在RR模式下，再对T做一次左旋

实现

删除节点

• 在AVL树中删除键相对而言比较困难，但也是对数级的

实现

Red-Black Tree

红黑树：能够容忍同一节点的一棵子树高度是另一棵的2倍

Splay Tree

分裂树：

2-3树

2-3树：可以包含两种类型的节点2节点、3节点，树的所有叶子节点 必须位于同一层

• 2-3树的高度即决定其查找、插入、删除效率

  • 节点数为n的2-3数高度h满足 $log_3(n+1)-1 \leq h \leq log_2(n+1) - 1$
  • 最差、平均情况下，操作效率$\in \Theta(logn)$

• 2-3树总是高度平衡

  • 所有叶子节点位于同一层，即树根到其路径长度相同
  • 2-3树平衡代价
    • 树中节点可以有1或2个键，需要处理2种节点类型
    • 拆分3节点的情况有很多种

• 节点类型

  • 2节点：只包含1个键K、2个子女

    • 左子女：作为所有键都小于K的子树的根
    • 右子女：作为所有键都大于K的子树的根

  • 3节点：两个有序键$K_1 < K_2$、3个子女

    • 最左边子女：作为键值小于$K_1$的子树的根
    • 中间子女：作为键值位于$[K_1, K_2]$之间子树的根
    • 最右边子女：作为键值大于$K_2$的子树的根

• 类似的还有2-4树

查找

• 如果根是2节点，当作二叉树查找

  • 若K等于根键值，停止
  • 若K小、大于根键值，在左、右子树中查找

• 若根是3节点

  • 和两个键值比较，有相等，停止
  • 否则能确定应该在3棵子树中哪棵继续查找

插入节点

除非是空树，否则总是把新键K插入叶子节点中

• 查找K确定合适的插入位置（叶子节点）

• 若叶子节点2节点，根据大小关系将K作为第一个键或第二个键 插入

• 若叶子节点3节点，把叶子分裂为两个节点：3个键中最小的放入 第一个叶子中，最大的放入第二个叶子中，中间的键提升到原 叶子节点父母中

  

  • 若叶子就是根，则需要创建新根容纳中间键
  • 中间键的提升可能会导致父母节点分裂，并引起祖先链条上 多个节点的分裂

删除节点

B树

B树：允许节点可以有$1~m-1$个键（$2~m$个子女）

1
2
3
4
5
6
7

#define BTREE_M
typedef struct BTNode{
	unsigned int degree;				// 节点实际包含键数
	KeyType key_slots[BTREE_M-1];		// 节点存储键数组
	struct BTNode ptr_slots[BTREE_M];	// 指向子女节点指针
	struct BTNode * ptr_parent;			// 父节点指针
}BTNode, *BTNodePtr;

• $m$：B树阶数，节点允许最大子女数

  • 节点最多允许有$m-1$个条目
  • $m=2$即为二叉树、$m=3$即为2-3树

• 键：用于构建树的关键字，和具体条目类似于键值对

• 根节点具有$2~m$个子女，除非为叶子节点

• 非根、非叶节点具有$[\lceil m/2 \rceil, m]$个子女

  • 即具有$[\lceil m/2 \rceil - 1, m]$个有序键

  • 其中子树$T_0$所有键小于$K_1$，子树$T_1$中所有键大于 等于$K_1$小于 $K_2$，以此类推

• B树是完美平衡的：所有叶子节点在同一层上

查找

算法

• 输入：B树、目标查找键
• 输出：查找键所属B树节点（若存在）

• 从根节点开始，比较查找键k和节点中键序列大小

  • 节点中键有序，若B树阶数足够大，可考虑折半查找

• 若在节点键序列中找到匹配键，则查找成功、返回

• 否则根据比较结果选择合适分支，顺着指针链前进，在相应子女 节点中进行查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BTreeSearch(T, k):
	// 在B树中搜索键
	// 输入：B树根节点T、目标查找键k
	// 输出：目标键所在节点、目标键在节点中序号
	i = 0
	cur = T

	// 遍历寻找目标键对应键、分支
	while i < cur.degree and k > cur.key_slots[i]:
		i += 1

	if i < cur.degree and k == cur.key_slots[i]:
		return cur, i
	elif cur.is_leaf():			// 未找到目标键
		return cur, -1
	else:
		return BTreeSearch(cur.ptr_slots[i], k)

分裂

算法

• 输入：待分裂节点父节点、待分裂节点序号

• 计算待分裂节点分裂中心

  • 将分裂中心右侧数据移动至新节点

• 将节点分裂中心、新节点提升至父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

BTreeNodeSplit(T, ptr_idx):
	// 分裂B树中节点
	// 输入：待分裂节点父节点`T`、待分裂节点序号`ptr_idx`

	nnode = BTreeNode()
	fnode = T.ptr_slots[ptr_idx]

	// 分裂中心
	mid = fnode.degree // 2

	// 复制右半部分键至新节点
	nnode.key_slots[:fnode.degree - mid] = fnode.key_slots[mid:fnode.degree]
	fnode.key_slots[mid:fnode.degree] = NULL

	// 若原节点非叶子节点，复制右半部分指针至新节点
	if not fnode.is_leaf():
		nnode.ptr_slots[:fnode.degree + 1 - mid] = fnode.ptr_slots[mid: fnode.degree + 1]
		fnode.ptr_slots[mid: fnode.degree+1] = NULL

	// 修改两节点度
	nnode.degree = fnode.degree - mid
	fnode.degree = mid

	// 将分裂中心提升至父节点
	// 修改父节点指向子女节点指针
	T.key_slots.insert(fnode.key_slots[mid], ptr_idx)
	T.ptr_slots.insert(nnode, ptr_idx+1)	// 原节点指针不变

插入

• 输入：B树根T、待插入键K
• 假设B树中不存在键K，否则查找、更新对应值即可

• 根据需要插入键K，查找需要插入的叶子节点L
• 若叶子节点L键数小于m-1，直接插入结束
• 否则以叶子节点键值中位数mid为中心分裂
  • 将mid插入叶子节点L父节点P中
  • 将mid左子支指向分裂后左子树、右子支指向分裂后右子树
• 对父节点尝试操作

1
2
3
4
5
6
7
8
9
10
11
12
13

BTreeInsert(T, k)
	// 向B树中插入不存在键K
	// 输入：B树根T、待插入键k

	// 找到键`k`应该插入的叶子节点`L`
	L, _ = BTreeSearch(T, k)
	L.key_slots.insert_in_order(k)


	// 若节点已满、须分裂
	while L.is_full():
		BTreeNodeSplit(L.parent_ptr, L.get_index())
		L = L.parent_ptr

• 此实现是考虑节点都有空位容纳新键，节点插入新键后再 判断是否需要分裂

删除#todo

应用

• 类似一般查找树，把数据记录插入初始为空的树中构造B树

B+树

B+树：B树的一种变形树

• 其中非叶节点只有索引作用，跟记录相关信息均存放在 叶结点中
• B+树中所有叶结点构成有序链表，可以按照键次序遍历

查找

算法

• 从根开始，比较查找键K和节点中键大小，选择合适指针，顺着 指针链前进

• 指针链指向可能包含查找键的叶子节点，在其中查找K

  • 父母节点、叶子节点都是有序的，如果B树次数足够 大，可以考虑使用折半查找

算法效率

以B树作索引存储大型数据文件为例

• 查找指定查找键访问B树节点数量为B树高度$h+1$ （即磁盘访问次数）

• 次数为m、高度为h的B树能够包含最少节点数为 $n \geqslant 4 \lceiling m/2 \rceiling ^ {h-1} -1$， 即$h \leqslant \lfloor log_{[m/2]} \frac {n+1} 4 \rfloor + 1$

• 所以在B树中查找，访问磁盘次数$\in O(logn)$

  • 实际应用中，磁盘访问次数很少超过3，因为B树的根、甚至 是第一层节点会存储在内存中减少磁盘访问次数

插入

算法

• 查找新记录键K对应的叶子节点

• 若叶子节点中还有空间存放此记录，在保持键有序的情况下插入

• 若节点中没有空间

  • 将节点分裂，后半部分记录放在新节点中
  • 新节点中最小键$K^{‘}$、指向其的指针插入原叶子节点 父母节点中（原叶子节点键、指针之后）
  • 插入过程可以一直回溯到树根，甚至直到树根分裂

其他考虑

• 查找新记录对应叶子节点时就分裂满节点，可以避免递归分裂
• 将满叶子节点中部分键移动给兄弟节点，同时替换父母节点中的 键值（保证B树特点），增加少许复杂度以节约空间

算法特点

• 算法效率
  • 算法时间效率$\in O(logn)$

应用

• B+树是存储结构化记录数据集合最重要的索引结构
  • 所有数据记录（键）按照升序存储在叶子节点中，其父母 节点作为索引
  • B+树中节点常常对应磁盘中页
  • 考虑到访问磁盘页面是比较内存中键值比较时间多好几个 数量级，磁盘访问次数是衡量B树效率的主要指标

标

思想：最速下降&牛顿

对目标函数$f(x)$在$x^{(1)}$进行展开

• 最速下降法：只保留一阶项，即使用线性函数近似原目标函数
• Newton法：保留一阶、二阶项，即使用二次函数近似

• 利用近似函数求解元素问题极小值

  • 最速下降法：线性函数无极值，需要确定步长、迭代
  • Newton法：二次函数有极值，直接求导算出极值、迭代

• 最速下降法

  • 只考虑一阶导：甚至说根本没有考虑拟合原目标函数

• Newton法

  • 考虑二阶导：每步迭代还考虑了二阶导，即当前更新完毕 后，下一步能够更好的更新（二阶导的意义）
  • 甚至从后面部分可以看出，Newton法甚至考虑是全局特征， 不只是局部性质（前提目标函数性质足够好）
  • 二次函数拟合更接近函数极值处的特征

最速下降算法

思想

• 设$x=x(t)$为最优点$x$从初始点、沿负梯度方向经过的曲线， 则有

  $$\left \{ \begin{array}{l} & \frac {dx(t)} {dt} = -\nabla f(x(t)) \\ & x(t_1) = x^{(1)} \end{array} \right.$$

  • $t_1, x^{(1)}$：初始时刻、初始位置

• 可以证明，$x(t)$解存在，且$t \rightarrow \infty$时，有 $x(t) \rightarrow x^{ * }$，即得到无约束问题最优解

• 但微分方程组求解可能很麻烦，可能根本无法求解

  • 考虑将以上曲线离散化，每次前进到“不应该”前进为止
  • 然后更换方向，逐步迭代得到最优解

算法

• 搜索方向最速下降方向：负梯度方向
• 终止准则：$\nabla f(x^{(k)})=0$

1. 取初始点$x^{(1)}$，置k=1

2. 若$\nabla f(x^{(k)})=0$，则停止计算，得到最优解， 否则置

   $$d^{(k)} = -\nabla f(x^{(k)})$$

   以负梯度作为前进方向

3. 一维搜索，求解一维问题

   $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} + \alpha d^{(k)})$$

   得$\alpha_k$前进步长，置

   $$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$$

4. 置k=k+1，转2

• 最速下降算法不具有二次终止性

叠加惯性

模拟物体运动时惯性：指数平滑更新步长

Momentum

冲量方法：在原始更新步上叠加上次更新步，类似指数平滑

• $v^{(t)}$：第$t$步时第k个参数更新步
• $L(\theta)$：往往是batch损失函数

• 更新参数时，一定程度保持上次更新方向
• 可以在一定程度上保持稳定性，学习速度更快
• 能够越过部分局部最优解

Nesterov Momentum

NGA：在使用冲量修正最终方向基础上，使用冲量对当前 参数位置进行修正，即使用“未来”位置计算梯度

• 先使用冲量更新一步
• 再在更新后位置计算新梯度进行第二步更新

动态学习率

• 学习率太小收敛速率缓慢、过大则会造成较大波动
• 在训练过程中动态调整学习率大小较好

• 模拟退火思想：达到一定迭代次数、损失函数小于阈值时，减小 学习速率

Vanilla Gradient Descent

每次迭代减小学习率$\eta$

• 学习率逐渐减小，避免学习后期参数在最优解附近反复震荡

Adagrad

adaptive gradient：训练中不同参数学习率随着迭代次数、 梯度动态变化，使得参数收敛更加平稳

• $\epsilon$：fuss factor，避免分母为0
• $\theta^{(t)}_k$：第t轮迭代完成后待估参数第k个分量 （之前未涉及参数间不同，统一为向量）

• 特点

  • 较大梯度参数真正学习率会被拉小；较小梯度真正学习率 参数被拉小幅度较小
  • 可以和异步更新参数结合使用，给不常更新参数更大学习率

• 缺点

  • 在训练后期，分母中梯度平方累加很大，学习步长趋于0， 收敛速度慢（可能触发阈值，提前结束训练）

RMSprop

root mean square prop：指数平滑更新学习率分母

• 赋予当前梯度更大权重，减小学习率分母，避免学习速率下降 太快

Adam

adptive moment estimation：指数平滑更新步、学习率分母

• $\gamma_1$：通常为0.9
• $\gamma_2$：通常为0.99
• $\hat{v^{(t)}_k} = \frac {v^{(t)}_k} {1 - \gamma_1^t}$ ：权值修正，使得过去个时间步，小批量随机梯度权值之和为1

• 利用梯度的一阶矩$v^{(t)}$、二阶矩$s^{(t)}$动态调整每个 参数学习率

• 类似于mommentum、RMSprop结合

• 经过偏执矫正后，每次迭代学习率都有确定范围，参数比较平稳

Adadelta

指数平滑更新学习率（分子）、学习率分母

• $s, \Delta \theta$共用超参$\gamma_1$

• 在RMSprop基础上，使用$\sqrt {\Delta \theta}$作为学习率
• $\hat v$：中超参$\gamma_1$在分子、分母“抵消”，模型对 超参不敏感

样本量

Singular Loss/Stocastic Gradient Descent

SGD：用模型在某个样本点上的损失极小化目标函数、计算梯度、 更新参数

• 单点损失度量模型“一次”预测的好坏

  • 代表模型在单点上的优劣，无法代表模型在总体上性质
  • 具有很强随机性

• 单点损失不常用，SGD范围也不局限于单点损失

• 损失函数具体参见ml_xxxxx

全局估计

全局损失：用模型在全体样本点上损失极小化目标函数、计算梯度、 更新参数

• $\theta^{(t)}$：第t步迭代完成后待估参数
• $\eta$：学习率
• $L{total}(\theta) = \sum{i=1}^N L(\theta, x_i, y_i)$： 训练样本整体损失
• $N$：训练样本数量

• 若损失函数有解析解、样本量不大，可一步更新（计算） 完成（传统参数估计场合）

  • 矩估计
  • 最小二乘估计
  • 极大似然估计

• 否则需要迭代更新参数

  • 样本量较大场合
  • 并行计算

Mini-Batch Loss

mini-batch loss：用模型在某个batch上的损失极小化目标函数、 计算梯度、更新参数

• $L{batch}(\theta)=\sum{i \in B} L(\theta, x_i, y_i)$： 当前batch整体损失
• $B$：当前更新步中，样本组成的集合batch

• batch-loss是模型在batch上的特征，对整体的代表性取决于 batch大小

  • batch越大对整体代表性越好，越稳定；越小对整体代表 越差、不稳定、波动较大、难收敛
  • batch大小为1时，就是SGD
  • batch大小为整个训练集时，就是经验（结构）风险

• batch-loss是学习算法中最常用的loss，SGD优化常指此

  • 实际中往往是使用batch-loss替代整体损失，表示经验风险 极小化
  • batch-loss同样可以带正则化项，表示结构风险极小化
  • 损失极值：SVM（几何间隔最小）

优点

• 适合样本量较大、无法使用样本整体估计使用
• 一定程度能避免局部最优（随机batch可能越过局部极值）
• 开始阶段收敛速度快

缺点

• 限于每次只使用单batch中样本更新参数，batch-size较小时， 结果可能不稳定，往往很难得到最优解

• 无法保证良好的收敛性，学习率小收敛速度慢，学习率过大 则损失函数可能在极小点反复震荡

• 对所有参数更新应用相同学习率，没有对低频特征有优化 （更的学习率）

• 依然容易陷入局部最优点

Newton法

思想

• 若$x^{ * }$是无约束问题局部解，则有

  $$\nabla f(x^{ * }) = 0$$

  可求解此问题，得到无约束问题最优解

• 原始问题是非线性，考虑求解其线性逼近，在初始点$x^{(1)}$ 处泰勒展开

  $$\nabla f(x) \approx \nabla f(x^{(1)}) + \nabla^2 f(x^{(1)})(x - x^{(1)})$$

  解得

  $$x^{(2)} = x^{(1)} - (\nabla^2 f(x^{(1)}))^{-1} \nabla f(x^{(1)})$$

  作为$x^{ * }$的第二次近似

• 不断迭代，得到如下序列

  $$x^{(k+1)} = x^{(k)} + d^{(k)}$$

  • $d^{(k)}$：Newton方向，即以下方程解 $$\nabla^2 f(x^{(k)}) d = -\nabla f(x^{(k)})$$

算法

• 初始点 $x^{(1)}$、精度要求 $\epsilon$，置 $k=1$

• 考虑 $|\nabla f(x^{(k)})| \leq \epsilon$

  • 若满足，则停止计算，得到最优解 $x^{(k)}$

  • 否则求解如下方程，得到 $d^{(k)}$

    $$\nabla^2 f(x^{(k)}) d = -\nabla f(x^{(k)})$$

• 如下设置，并转2

  $$x^{(k+1)} = x^{(k)} + d^{(k)}, k = k+1$$

特点

• 优点

  • 产生点列 ${x^{k}}$ 若收敛，则具有二阶收敛速率
  • 具有二次终止性，事实上对正定二次函数，一步即可收敛

• 缺点

  • 可能会在某步迭代时目标函数值上升
  • 当初始点 $x^{(1)}$ 距离最优解 $x^{ * }$ 时，产生的点列 可能不收敛，或者收敛到鞍点
  • 需要计算 Hesse 矩阵
    • 计算量大
    • Hesse 矩阵可能不可逆，算法终止
    • Hesse 矩阵不正定，Newton 方向可能不是下降方向

阻尼/修正 Newton 法

• 克服 Newton 法目标函数值上升的缺点
• 一定程度上克服点列可能不收敛缺点

算法

• 初始点 $x^{(1)}$、精度要求 $\epsilon$，置 $k=1$

• 考虑 $|\nabla f(x^{(k)})| \leq \epsilon$

  • 若满足，停止计算，得到最优解 $x^{(k)}$
  • 否则求解如下方程得到 $d^{(k)}$ $$\nabla^2 f(x^{(k)}) d = -\nabla f(x^{(k)})$$

• 一维搜索，求解一维问题

  $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} + \alpha d^{(k)})$$

  得到 $\alpha_k$，如下设置并转2

  $$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}, k = k+1$$

其他改进

• Newton 法、修正 Newton 法的改进方向
  • 结合最速下降方向修正迭代方向
  • Hesse 矩阵不正定情形下的替代

结合最速下降方向

• 将 Newton 方向和最速下降方向结合

• 设 $\theta_k$ 是 $$ 之间夹角，显然希望 $\theta < \frac \pi 2$

• 则置限制条件 $\eta$，取迭代方向

  $$d^{(k)} = \left \{ \begin{array}{l} d^{(k)}, & cos\theta_k \geq \eta \\ -\nabla f(x^{(k)}), & 其他 \end{array} \right.$$

Negative Curvature

• 当 Hesse 矩阵非正定时，选择负曲率下降方向 $d^{(k)}$（一定存在）

• Hesse 矩阵非正定时，一定存在负特征值、相应特征向量 $u$

  • 取负曲率下降方向作为迭代方向

    $$d^{(k)} = -sign(u^T \nabla f(x^{(k)})) u$$

  • $x^{(k)}$ 处负曲率方向 $d^{(k)}$ 满足

    $${d^{(k)}}^T \nabla^2 f(x^{(k)}) d^{(k)} < 0$$

修正 Hesse 矩阵

• 取迭代方向 $d^{(k)}$ 为以下方程的解

  $$(\nabla^2 f(x^{(k)}) + v_k I) d = -\nabla f(x^{k})$$

• $v_k$：大于 $\nabla^2 f(x^{(k)})$ 最大负特征值绝对值

综述

特殊方法：python类中具有特殊名称的方法，实现由特殊语法 所引发的特定操作

• python实现操作符重载的方式

  • 允许每个类自行定义基于操作符的特定行为
  • 特定操作包括python内置的钩子函数

• 钩子函数不能简单的看作直接调用特殊方法

  • 尝试调用备用实现：iter、reversed
  • 修改方法返回值：dir

• 大部分情况下，若没有定义适当方法，尝试执行操作将 raise AttributeError、raise TypeError

  • 但__hash__、__iter__、__reversed__、 __contains__等方法即使未定义，其对应钩子函数 实现会尝试调用可能的其他方法完成操作 （直接obj.__xxx__调用方法仍然报错）

  • 将特殊方法设为None表示对应操作不可用，此时即使以上 hash、iter、reversed、in等操作也不会尝试调用 备用方法

实例创建、销毁

调用类时，元属性方法执行顺序

• __prepare__()：创建命名空间
• 依次执行类定义语句
• __new__()：创建类实例
• __init__()：初始化类
  • __new__返回的新实例的__init__方法将被调用
  • 用户定义__new__返回对象不一定期望类实例，调用的 __init__随之不一定是期望方法
• 返回__new__返回类实例

__prepare__

• 在所有类定义开始执行前被调用，用于创建类命名空间
• 一般这个方法只是简单的返回一个字典或其他映射对象

__new__

1
2

classmethod object.__new__(cls[, *args, **kwargs]):
	pass

• 用途：创建、返回cls类新实例

  • super().__new__(cls[,...])调用超类方法创建类实例， 然后根据需要修改新创建实例再返回

• 参数

  • cls：待实例化类
  • 其余参数：类构造器表达式参数

• 返回值：cls类新实例

  • __new__返回值就是类构造器的返回值，有绝对控制权

说明

• __new__：builtin_function_or_method

• __new__是静态方法：以需实例化类作为第一个参数

  • __new__方法绑定当前类对象
  • 特例，不需要显式声明为静态方法

• 原生有两个__new__函数，二者C实现不同

  • type.__new__：元类继承，用于创建类对象
  • object.__new__：其他类继承，用于创建实例

__init__

1
2

def object.__init__(self[, *args, *kwargs]):
	pass

• 用途：初始化类实例

  • 类构造器中__new__返回类实例调用此方法初始化
  • 若基类有用户定义__init__方法，则其派生类__init__ 应该显式调用基类__init__保证基类部分正确初始化

• 参数

  • self：当前类实例
  • 其余参数：类构造器表达式参数

• 返回值：None，否则raise TypeError

__del__

1

def object.__del__(self)

• 用途：实例销毁时（引用计数变为0）被调用
  • 若基类有__del__方法，则其派生类__del__方法中 需要显式调用基类__del__保证基类部分正确清除
  • 对象重生：在其中创建该实例的新引用推迟其销毁
    • 不推荐
    • 重生对象被销毁时__del__是否会被再次调用取决于 具体实现
    • 当前CPython实现中只会调用一次

说明

• 解释器退出时不会确保为仍然存在的对象调用__del__方法
• “钩子函数”：del
  • del x不直接调用x.__del__()
  • del x仅将x的引用计数减一

输出属性

__repr__

1
2

def object.__repr__(self):
	pass

• 用途：输出对象的“官方”字符串表示

  • 如果可能，应类似有效的python表达式，可以用于重建具有 相同取值的对象（适当环境下）
  • 若不可能，返回形如<...some useful description...> 的字符串
  • 常用于调试，确保内容丰富、信息无歧义很重要

• 返回值：字符对象

  • 内置钩子函数：repr
  • 交互环境下直接“执行”变量的结果

__str__

1
2

def object.__str__(self):
	pass

• 用途：生成对象“非正式”、格式良好的字符串表示

  • 返回较方便、准确的描述信息

• 返回值：字符串对象

  • 内置钩子函数：str

说明

• object.__str__方法默认实现调用object.__repr__

  • 所以若未定义__str__，需要实例“非正式”字符串表示时 也会使用__repr__

• format、print函数会隐式调用对象__str__方法

  • 此时若__str__返回非字符串会raise TypeError

__bytes__

1
2

def object.__bytes__(self):
	pass

• 用途：生成对象的字节串表示

• 返回值：bytes对象

  • 内置钩子函数：bytes

__format__

1

def object.__format__(self, format_spec)

• 用途：生成对象的“格式化”字符串表示

  • 内部常调用format、str.format实现格式化
  • object.__format__(x, '')等同于str(x)

• 参数

  • fomrat_spec：包含所需格式选项描述的字符串
    • 参数解读由实现__format__的类型决定
    • 大多数类将格式化委托给内置类型、或使用相似格式化 语法

• 返回值：字符串对象

  • 内置钩子函数：format

__hash__

1
2

def object.__hash__(self):
	pass

• 用途：计算对象hash值返回

  • 相等的对象（即使类型不同）理应具有相同hash值
  • 建议把参与比较的对象的全部组件的hash值打包为元组， 对元组做hash运算

    1 2	def __hash__(self): return hash((self.name, self.nick, self.color))

• 返回值：整数

  • 内置钩子函数：hash()

说明

• hash()会从对象自定义的__hash__()方法返回值中截断为 Py_ssize_t大小

  • 64bits编译平台通常为8bytes、32bits为4bytes
  • 若对象__hash__()需要在不同位大小的平台上互操作， 需要检查支持的平台位宽

  • 查看sys.hash_info.width

• set、frozenset、dict这3个hash集类型中成员的操作 会调用相应__hash__()

• 类的__hash__方法设置为None时

  • 尝试获取实例hash值时将raise TypeError
  • isinstance(obj, collecitons.abc.Hashable)返回 False
  • 单纯在__hash__中显式raise TypeError会被错误 认为是可hash

关联__eq__

hash绝大部分应用场景是比较是否相等，所以__hash__、__eq__ 密切相关

• 类未定义__eq__

  • 也不应该定义__hash__，单独hash结果无法保证比较结果

• 类实现__eq__

  • 未定义__hash__：其实例将不可被用作hash集类型的项
  • 类中定义了可变对象：不应该实现__hash__，因为hash集 实现要求键hash值不可变

• 类重载__eq__方法

  • 默认其__hash__被隐式设为None
  • 否则须设置__has__ = <ParentClass>.__hash__显式保留 来自父类__hash__实现

默认实现

• float、integer、decimal.Decimal等数字类型hash运算 是基于为任意有理数定义的统一数学函数

  • 详细参考https://docs.python.org/zh-cn/3/library/stdtypes.html#hashing-of-numeric-types

• str、bytes、datetime对象__hash__值会使用不可预知 值随机加盐

  • 盐在单独python进程中保持不变，但在重复执行的python 进程之间是不可预测的
  • 目的是为了防止某种形式的DDos服务攻击

• 改变hash值会影响集合迭代次序

  • python也不保证次序不会改变

__bool__

1
2

def object.__bool__(self):
	pass

• 用途：返回True、False实现真值检测

  • 未定义：调用__len__返回非0值时对象逻辑为真
  • __len__、__bool__均未定义：所有实例逻辑为真

• 返回值：False、True

  • 内置构造函数：bool()

例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Pair:
	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __repr__(self):
		# 返回实例代码表示形式
		# 通常用于重新构造实例
		return "Pair({0.x!r}, {0.y!r})".format(self)
			# 格式化代码`!r`指明输出使用`__repr__`而不是默认
				# 的`__str___`
			# 格式化代码`0.x`表示第一个参数`x`属性

	def __str__(self):
		return "({0.x!s}, {0.y!s})".format(self)
			# 格式化代码`!s`指明使用默认`__str__`

	def __format__(self):
		if self.x == 0:
			return self.y
		elif self.y == 0:
			return self.x
		return "{0.x!r}, {0.y!r}".format(self)

Rich Comparison Methods

富比较方法

1
2
3
4
5
6
7
8
9
10
11
12

def object.__lt__(self, other):
	pass
def object.__le__(self, other):
	pass
def object.__eq__(self, other):
	pass
def object.__ne__(self, other):
	pass
def object.__gt__(self, other):
	pass
def object.__ge__(self, other):
	pass

• 用途：比较运算符重载

  • x < y：调用x.__lt__(y)
  • x <= y：调用x.__le__(y)
  • x == y：调用x.__eq__(y)
  • x != y：调用x.__ne__(y)

• 返回值

  • 成功比较返回False、True
  • 若指定方法没有相应实现，富比较方法会返回单例对象 NotImplemented

• 比较运算默认实现参见cs_python/py3ref/expressions

说明

• 默认情况下，__ne__会委托给__eq__，并将结果取反，除非 结果为NotImplemented

• 比较运算符之间没有其他隐含关系

  • x < y or x == y为真不意味着x <= y
  • 要根据单个运算自动生成排序操作可以利用 functools.total_ordering()装饰器简化实现

• 以上方法没有对调参数版本（左边参数不支持该操作，右边参数 支持该操作）

  • 若两个操作数类型不同、且右操作数是左操作数直接或间接 子类，优先选择右操作数的反射方法，否则左操作数 方法（不考虑虚拟子类）
  • 反射方法
    • __lt__、__gt__互为反射
    • __le__、__ge__互为反射
    • __eq__、__ne__各为自身反射

内部信息

__dict__

• 钩子函数：vars、dir（部分）

  • vars是真正对应的钩子函数，返回键值对
  • dir执行过程中会访问__dict__、__class__，而且 只返回keys

• 对象底层字典，存储对象属性、方法

  • 注意区分开：实例属性、类属性、基类属性，__dict__ 只包括当前实例属性、方法
  • 返回结果是dir结果的子集

• 调用实例obj的属性时，按照以下顺序查找

  • obj.__dict__：当前实例的__dict__中
  • type(obj).__dict__：实例所属类的__dict__中
  • type(obj).mro().__dict__：基类的__dict__中

• 在大部分情况下__dict__会自动更新，如setattr函数时， 或说实例的属性、方法更新就是__dict__的变动

  • 一般情况下不要直接访问__dict__，除非真的清楚所有 细节，如果类使用了cls.__slots__、@property、 描述器类等高级技术时代码可能会被破坏

  • 尽量使用setattr函数，让python控制其更新

__class__

• 用途：返回实例所属类

• 返回值：实例（狭义）返回类、类返回元类

  • 钩子函数：type

__objclass__

• 用途：被inspect模块解读为指定实例所在的类
  • 合适的设置可以有助于动态类属性的运行时检查
  • 对于可调用对象：指明第一个位置参数应为特定类型的 实例、子类
    • 描述器类：instance参数

      todo

__slots__

• 用途：显式声明数据成员、特征属性，限制实例添加属性

  • 可赋值为：字符串、可迭代对象、实例使用的变量名构成的 字符串序列

    • 可迭代对象中元素可以是任何类型
    • 还可以映射类型，未来可能会分别赋给每个键特殊含义 的值

  • __slots__会为已声明变量保留空间

    • 直接访问将raise AttributeError
    • dir可以找到__slots__中声明的变量

• 阻止默认为每个实例创建__dict__、__weakref__的 行为，除非在__slots__中显式声明、或在父类中可用

  • 无__dict__属性实例无法给未在__slots__中列出 的新变量赋值

    • 但是python很多特性依赖于普通的依赖字典实现，定义 __slots__的类不再支持普通类某些特性
    • 大多数情况下，应该只在经常使用到作为数据结构的 类上定义__slots__
    • 不应该把__slots__作为防止用户给实例增加新属性 的封装工具

  • 无__weakref__属性实例不支持对实例的弱引用

• 是阻止给实例创建__dict__，类本身仍然有__dict__属性 （dir返回值中无__dict__，__dir__返回值中有）

说明

• __slots__声明的行为不只限于定义其的类

  • 父类中声明__slots__可以在子类中使用，但子类将获得 __dict__、__weakref__，除非其也定义了__slots__

  • 子类__slots__中定义的slot将覆盖父类中同名slot

    • 需要直接从基类直接获取描述器才能访问
    • 这会导致程序未定义，以后增加检查避免

  • 多重继承中只允许一个父类具有非空__slots__，否则 raise TypeError

• __slots__是在类层次上的实现：为每个变量创建描述器

  • 类属性不能被用于给在__slots__中定义变量设置默认值
  • 否则类属性会覆盖描述器赋值，变成只读属性

• 非空的__slots__不适用于派生自“可变长度”内置类型，如 int、bytes、tuple

• 定义类属性__slots__后，python会为实例属性使用紧凑内部 表示

  • 实例属性使用固定大小、很小的数组构建，而不是为每个 实例定义字典
  • 在__slots__列出的属性名在内部映射到数组指定下标上
  • 类似于R中factor类型、C中enum类型
  • 相比__dict__可以显著节省空间、提升属性查找速度

1
2
3
4
5
6

class Date:
	__slots__ = ["year", "month", "day"]
	def __init__(self, year, month, day):
		self.year = year
		self.month = month
		self.day = day

• 继承自未定义__slots__类时，实例中__dict__、 __weakref__属性将总是可访问的

• __class__赋值仅在两个类具有相同__slots__值时才有用

自定义属性访问

__getattr__

1
2

def object.__getattr__(self, name):
	pass

• 用途：.默认属性访问引发AttributeError而失败时调用

  • 如果属性通过正常机制找到，__getattr__不会被调用
    • 在__getattr__、__setattr__之间故意设置的 不对称性
    • 出于效率考虑
  • 对实例变量而言，无需在实例属性字典中插入值，就可以 模拟对其的完全控制

• 返回值：计算后的属性值、或raise AttributeError

说明

• 可能引发AttributeError

  • 调用__getattribute__时因为name不是实例属性、 或是类关系树中属性
  • 对调用__get__获取name描述器

• 调用__getattr__是.运算符中逻辑

  • __getattribute__显式调用raise AtttributeError 不会调用__getattr__

• __getattr__甚至不是object具有的 <wrapper_descriptor>

• 相较于__getattribute__其实更常用，因为修改所有对 对对象的访问逻辑没啥价值

__getattribute__

1
2
3
4
5
6

def __getattribute__(self, key):
	"Emulate type_getattro() in Objects/typeobject.c"
	v = object.__getattribute__(self, key)
	if hasattr(v, "__get__"):
		return v.__get__(None, self)
	return v

• 用途：访问对象属性时无条件被调用

  • 判断访问属性类型、做对应操作
    • 描述器：调用描述器方法
    • 实例方法：为类中函数绑定实例
    • 类方法：为类中函数绑定类
    • 静态方法：不绑定
    • 普通属性
  • 作为通过特定语法、内置函数隐式调用的结果情况下， 查找特殊方法时仍可能被跳过

• 返回值：找到的属性值、或raise AttributeError

• __getattribute__仅对继承自object的新式类实例可用

说明

• 内置类型均有各自__getattribute__函数实例

  • 其均为wrapper_descriptor类型（C实现的函数）
  • 各函数实例标识符不同，若其均“继承自object”，其 应为同一个函数实例
  • 自定义类真继承自object类，其__getattribute__同 object.__getattribute__

• 自定义实现

  • 为避免方法中无限递归，实现总应该调用具有相同名称 基类方法访问所需要的属性

钩子函数

• .运算符：首先调用__getattribute__，若无访问结果， 调用__getattr__

  • .运算符说明参见cs_python/py3ref/cls_basics

• getattr：基本同.运算符，除可捕获异常，设置默认返回值

• hasattr：内部调用getattr，根据raise Exception判断 属性是否存在

  • 可以通过@property.getter中raise AttributeError 使得属性看起来不存在
  • 内部有更多boilerplate相较于getattr更慢
  • 则按照字面意思使用不需要考虑过多

__setattr__

1
2

def object.__setattr__(self, name, value):
	pass

• 用途：属性被尝试赋值时被调用

  • 默认实现：将值保存到实例字典
  • 若__setattr__要赋值给实例属性，应该调用同名基类 方法

• 返回指：None

  • 钩子函数：setattr

__delattr__

1
2

def object.__delattr__(self, name):
	pass

• 用途：删除实例属性时被调用

  • 默认实现：从实例字典中删除对应项
  • 应该在del obj.name对该对象有意义时才实现

• 返回值：None

  • 内置钩子函数：delattr、del

__dir__

1
2

def object.__dir__(self):
	pass

• 用途：返回实例中“可访问”名称的字符串列表

  • 默认实现：返回实例、类、祖先类所有属性
  • 交互式解释器就是在__dir__/dir返回列表中进行查询 进行补全

• 返回值：序列

  • 内置钩子函数：dir
    • dir()获取__dir__返回序列，转换为列表、排序
    • dir()会剔除__dir__返回值中部分值
    • 若__dir__返回值不可迭代，报错

自定义模块属性访问

• __getattr__、__dir__可以用于自定义对模块属性的访问

  • 模块层次__getattr__类似普通类
    • 接受属性名作为参数
    • 返回计算后结果、或raise AttributeError
    • 若正常查找__getattribute__无法在模块中找到某个 属性，调用__getattr__
  • 模块层次__dir__类似普通类
    • 不接受参数
    • 返回模块中可访问名称的字符串列表

• 可以将模块的__class__属性设置为types.ModuleType子类

  1 2 3 4 5 6 7 8 9 10 11

  import sys import types import ModuleType class VersboseModule(ModuleType): def __repr__(self): return f"verbose {self.__name__}" def __setattr__(self, attr, value): print(f"settting {attr}") super().__setattr__(attr, value) sys.modules[__name__].__class__ = VerboseModule

• 设置模块__getattr__、__class__只影响使用属性访问 语法进行查找，直接访问模块全局变量（通过模块内代码、对 模块全局字典引用）不受影响

描述器类

描述器：具有“绑定行为”的对象属性

• 类中定义其中任意一个方法，则其实例被称为描述器

  • __set__
  • __get__
  • __delete__

• 所有对描述器属性的访问会被__get__、__set__、 __delete__方法捕获/重载

  • 如果只是想简单的自定义某个类的属性处理逻辑，使用 @porperty装饰器简化实现

• @property参见cs_python/py3ref/cls_basics

描述器协议

• 以下方法仅包含其的类的实例出现在类属性中才有效
  • 即以下方法必须在（祖先）类__dict__中出现，而不是 实例__dict__中
  • 即描述器只能定义为类属性，不能定义为实例属性

__get__

1
2

def object.__get__(self, instance, owner=None):
	pass

• 用途：访问描述器属性时调用，重载实例属性访问

  • 若描述器未定义__get__，则访问属性会返回描述器对象 自身，除非实例字典__dict__中有同名属性
  • 若仅仅只是从底层实例字典中获取属性值，__get__方法 不用实现

• 参数

  • instance：用于方法属性的实例
  • owner：实例所属类，若通过类获取属性则为None

• 返回值：计算后属性值、或raise AttributeError

• 示例

  1 2 3 4 5 6 7 8 9 10 11 12

  def __get__(self, instance, cls): if instance is None: # 装饰器类一般作为类属性，需要考虑通过类直接访问 # 描述器类属性，此时`instance is None` # 常用操作是返回当前实例 return self else: return instance.__dict__[self.name] # self：描述器类当前实例 # instance：定义描述器作为类属性的类的实例 # cls：定义描述器作为类属性的类

__set__

1
2

def object.__set__(self, instance, name, value):
	pass

• 用途：设置实例instance的“描述器属性”值为value，重载 实例属性赋值

  • 常用实现：操作实例instance.__dict__存储值，使得 看起来是设置普通实例属性

• 示例

  1 2 3 4 5 6 7 8 9 10

  def __set__(self, instance, name, value): if instance is None: pass else: if not instance(value, int): raise TypeError("expect an int") instance.__dict__[self.name] = value # 操作实例底层`__dict__` # `value`：赋给描述器类属性的值

__delete__

1
2

def object.__delete__(self, instance):
	pass

• 用于：“删除”实例instance的“描述器属性”，重载实例属性 删除

  • 具体实现应取决于__set__实现

• 示例

  1 2 3 4 5 6

  def __delete__(self, instance): if instance is None: pass else: del instance.__dict__[self.name] # 操作实例底层`__dict__`

__set_name__

1
2

def object.__set_name__(self, owner, name):
	pass

• 用途：类owner被创建时调用，描述器被赋给name

实现原理

• 描述器的实现依赖于object.__getattribute__()方法

  • 可以通过重写类的__getattribute__方法改变、关闭 描述器行为

• 描述器调用：描述器x定义在类A中、a = A()

  • 直接调用：x.__get__(a)
  • 实例绑定：a.x
    • 转换为：type(a).__dict__['x'].__get__(a)
  • 类绑定：A.x
    • 转换为：A.__dict__['x'].__get__(None,A)
  • 超绑定：super(a, A).x

实例绑定—资料描述器

• 资料描述器：定义了__set__、__delete__方法
• 非资料描述器：只定义了__get__方法

• 访问对象属性时，描述器调用的优先级取决于描述器定义的方法

  • 优先级：资料描述器 > 实例字典属性 > 非资料描述器
  • 实例属性会重载非资料描述器
  • 实例属性和资料描述器同名时，优先访问描述器，否则优先 访问属性

• 只读资料描述器：__set__中raise AttributeError得到

描述器调用

todo

Python设计

• function类中定义有__get__方法，则其实例（即函数） 都为非资料描述器

  • 所以实例可以覆盖、重载方法
  • __getattribute__会根据不同方法类型选择绑定对象
    • staticmethod：静态方法
    • classmethod：类方法
    • 实例方法

• super类中定义有__get__方法，则其实例也为描述器

• @property方法被实现为资料描述器

特殊描述器类

todo

• wrapper_descripter：<slot wrapper>，封装C实现的函数

  • 等价于CPython3中函数
  • 调用__get__绑定后得到<method-wrapper>
  • object的方法全是<slot wrapper>

• method-wrapper：<method-wrapper>，封装C实现的绑定方法

  • 等价于CPython3中绑定方法

function描述器类

function描述器类：实例化即得到函数

1
2
3
4
5
6
7
8
9

class function:
	function(code, globals[, name[, argdefs[, closure]]])

	def __call__(self, /, *args, **kwargs):
		# 作为一个函数调用自身

	def __get__(self, instance, owner, /):
		# 返回`owner`类型实例`instance`的属性
		# 即返回绑定方法

method描述器类

method描述器类：实例化即得到(bound )method，绑定方法

1
2
3
4
5
6
7
8

class method:
	method(function, instance)

	def __call__(self, /, *args, **kwargs):
		# 作为函数调用自身

	def __get__(self, instance, owner, /):
		# 返回自身

• (bound )method：绑定方法，（首个参数）绑定为具体实例 的函数，即实例属性

XXmethod描述类

• 代码是C实现，这里是python模拟，和help结果不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class classmethod:
	def __init__(self, method):
		self.method = method
	def __get__(self, obj, cls):
		return lambda *args, **kw: self.method(cls,*args,**kw)

class staticmethod:
	def __init__(self, callable):
		self.f = callable
	def __get__(self, obj, cls=None):
		return self.f
	@property
	def __func__(self):
		return self.f

• 类中静态方法、类方法就是以上类型的描述器

  • 静态方法：不自动传入第一个参数
  • 类方法：默认传递类作为第一个参数
  • 描述器用途就是避免默认传入实例为第一个参数的行为

• 静态方法、类方法均是非资料描述器，所以和实例属性重名时 会被覆盖

• 所以类静态方法、类方法不能直接通过__dict__获取、调用， 需要调用__get__方法返回绑定方法才能调用

  • 直接访问属性则由__getattribute__方法代劳

例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Integer:
	# 描述器类
	def __init__(self, name):
		self.name = name

	def __get__(self, instance, cls):
		# 描述器的每个方法会接受一个操作实例`instance`
		if instance is None:
			# 描述器只能定义为类属性，在这里处理直接使用类
				# 访问描述器类的逻辑
			return self
		else:
			return instance.__dict__(self.name)

	def __set__(self, instance, value):
		if not instance(value, int):
			rasie TypeError("expect an int")
		instance.__dict__[self.name] = value
			# 描述器方法会操作实例底层`__dict__`属性

	def __delete__(self, instance):
		del instance.__dict__[self.name]

class Point:
	x = Integer("x")
	y = Integer("y")
		# 需要将描述器的实例作为类属性放在类的定义中使用

	def __init__(self, x, y):
		self.x = x
		self.y = y

def test():
	p = Point(2, 3)
	print(p.x)
		# 调用`Point.x.__get__(p, Point)`
	print(Point.x)
		# 调用`Point.x.__get__(None, Point)`
	p.y = 5
		# 调用`Point.y.__set__(p, 5)`

自定义类创建

__init_subclass__

1
2

classmethod object.__init_subclass__(cls):
	pass

• 用途：派生类继承父类时，基类的__init_subclas__被调用
  • 可以用于编写能够改变子类行为的类
  • 类似类装饰器，但是类装饰其影响其应用的类，而 __init_subclass__影响基类所有派生子类
  • 默认实现：无行为、只有一个参数cls
  • 方法默认、隐式为类方法，不需要classmethod封装

• 参数

  • cls：指向新的子类
  • 默认实现无参数，可以覆盖为自定义参数

  1 2 3 4 5 6 7

  class Philosopher: def __init_subclass__(self, default_name, **kwargs): super().__init_subclass__(**kwrags) cls.default_name = default_name class AstraliaPhilosopher(Philosopher, default_name="Bruce"): pass

  • 定义派生类时需要注意传递参数
  • 元类参数metaclass会被其他类型机制消耗，不会被传递 给__init_subclass__

元类

• 默认情况下，类使用type构建

  • 类体在新的命名空间中执行，类名被局部绑定到 元类创建结果type(name, bases, namespace)

• 可在类定义部分传递metaclass关键字参数，自定义类创建 过程

  • 类继承同样继承父类元类参数
  • 其他类定义过程中的其他关键字参数会在以下元类操作中 进行传递
    • 解析MRO条目
    • 确定适当元类
    • 准备类命名空间__prepare__
    • 执行类主体
    • 创建类对象

解释MRO条目

1
2

def type.__mro_entries__():
	pass

• 用途：若类定义中基类不是type的实例，则使用此方法对 基类进行搜索

  • 找到结果时，以原始基类元组作为参数进行调用

• 返回值：类的元组替代基类被使用

  • 元组可以为空，此时原始基类将被忽略

元类确定

• 若没有显式给出基类、或元类，使用type()
• 若显式给出的元类不是type()的实例，直接用其作为元类
• 若显式给出type()实例作为元类、或定义有基类，则选取 “最派生”元类
  • 最派生元类从显式指定的元类、基类中元类中选取
  • 最派生元类应为所有候选元类的子类型
  • 若没有满足条件的候选元类则raise TypeError

准备类命名空间

1
2

def type.__prepare__(name, bases, **kwds):
	pass

• 用途：确定合适的元类之后，准备类命名空间

  • 若元类没有__prepare__属性，类命名空间将被初始化为 空ordered mapping

• 参数：来自于类定义中的关键字参数

执行类定义主体

1
2

exec(body, globals(), namespace)
	# 执行类主体类似于

• 普通调用和exec()区别
  • 类定义在函数内部时
    • 词法作用域允许类主体、方法引用来自当前、外部 作用域名称
    • 但内部方法仍然无法看到在类作用域层次上名称
    • 类变量必须通过实例的第一个形参、类方法方法

创建类对象

1
2

metaclass(name, base, namespace, **kwds):
	pass

• 用途：执行类主体填充类命名空间后，将通过调用 metaclass(name, base, namespace, **kwds)创建类对象

• 参数：来自类定义中的关键字参数

说明

• 若类主体中有方法中引用__class__、super，则__class__ 将被编译器创建为隐式闭包引用

  • 这使得无参数调用super可以能基于词法作用域正确 定位类
  • 而被用于进行当前调用的类、实例则是基于传递给方法 的第一个参数来标识

自定义实例、子类检查

• 以下方法应该的定义在元类中，不能在类中定义为类方法

  • 类似于实例从类中查找方法

• 元类abc.ABCMeta实现了以下方法以便允许将抽象基类ABC 作为“虚拟基类”添加到任何类、类型（包括内置类型）中

__instancecheck__

1
2

def class.__instancecheck__(self, instance):
	pass

• 用途：若instance被视为class直接、间接实例则返回真值

  • 重载instance内置函数行为

• 返回：布尔值

  • 内置钩子函数：isintance(instance, class)

__subclasscheck__

1
2

class.__subclasscheck__(self, subclass):
	pass

• 用途：若subclass被视为class的直接、间解子类则返回 真值

  • 重载issubclass内置函数行为

• 返回：布尔值

  • 内置钩子函数：issubclass(subclass, class)

模拟范型类型

__class_getitem__

1
2

classmethod object.__class_getitem__(cls, key):
	pass

• 用途：按照key指定类型返回表示泛型类的专门化对象

  • 实现PEP 484规定的泛型类语法
  • 查找基于对象自身
  • 主要被保留用于静态类型提示，不鼓励其他尝试使用
  • 方法默认、隐式为类方法，不需要classmethod封装

• 参数

  • cls：当前类
  • key：类型

模拟可调用对象

__call__

1
2

def object.__call__(self[,args...]):
	pass

• 用途：实例作为函数被调用时被调用
  • 若定义此方法x(arg1, arg2, ...)等价于 x.__call__(arg1, args2, ...)

模拟容器类型

• collections.abc.MutableMapping为抽象基类
  • 其实现基本方法集__getitem__、__setitem__、 __delitem__、keys()
  • 可以方法继承、扩展、实现自定义映射类

__len__

1
2

def object.__len__(self):
	pass

• 用途：计算、返回实例长度

  • 若对象未定义__bool__，以__len__是否返回非0作为 布尔运算结果

• 返回值：非负整形

  • 钩子函数：len()

• CPython：要求长度最大为sys.maxsize，否则某些特征可能 会raise OverflowError

__length_hint__

1
2

def object.__length_hist__(self):
	pass

• 用途：返回对象长度估计值

  • 存粹为优化性能，不要求正确无误

• 返回值：非负整形

  • 钩子函数：operator.length_hint()

__getitem__

1
2

def object.__getitem__(self, key):
	pass

• 用途：实现根据索引取值

• 参数

  • 序列key：整数、切片对象

    • key类型不正确将raise TypeError
    • key在实例有效范围外将raise IndexError

  • 映射key：可hash对象

    • key不存在将raise KeyError

• 返回值：self[key]

__setitem__

1
2

def object.__setitem__(self, key, value):
	pass

• 用途：实现根据索引赋值

• 参数：同__geitem__

__delitem__

1
2

def object.__delitem(self, key):
	pass

• 用途：实现删除索引对应项

• 参数：同__getitem__

__missing__

1
2

def object.__missing__(self, key):
	pass

• 用途：__getitem__无法找到映射中键时调用

__reversed__

1
2

def object.__iter__(self):
	pass

• 用途：为容器类创建逆向迭代器

• 返回值：逆向迭代对象

  • 内置钩子函数：reversed()

说明

• 若未提供__reversed__方法，reversed函数将回退到使用 序列协议：__len__、__getitem__

• 支持序列协议的对象应该仅在能够提供比reversed更高效实现 时才提供__reversed__方法

__contains__

1
2

def object.__contains__(self, item):
	pass

• 用途：实现成员检测

  • 若item是self成员则返回True、否则返回False
  • 对映射应检查键

• 返回值：布尔值

  • 钩子运算：in

说明

• 若未提供__contains__方法，成员检测将依次尝试

  • 通过__iter__进行迭代
  • 使用__getitem__旧式序列迭代协议

• 容器对象可以提供更有效率的实现

模拟数字

数字运算

定义以下方法即可模拟数字类型

• 特定类型数值类型不支持的运算应保持未定义状态
• 若不支持与提供的参数进行运算，应返回NotImplemented

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def object.__add__(self, other):
	# `+`
def object.__sub__(self, other):
	# `-`
def object.__mul__(self, other):
	# `*`
def object.__matmul__(self, other):
	# `@`
def object.__truediv__(self, other):
	# `/`
def object.__floordiv__(self, other):
	# `//`
def object.__mod__(self, other):
	# `%`
def object.__divmod__(self, other):
	# `divmod()`
def object.__pow__(self, other[, modulo=1]):
	# `pow()`/`**`
	# 若要支持三元版本内置`pow()`函数，应该接受可选的第三个
		# 参数
def object.__lshift__(self, other):
	# `<<`
def object.__rshift__(self, other):
	# `>>`
def object.__and__(self, other):
	# `&`
def object.__or__(self, other):
	# `|`
def object.__xor__(self, other):
	# `~`

反射二进制算术运算

以下成员函数仅在左操作数不支持相应运算、 且两操作数类型不同时被调用

• 实例作为作为相应运算的右操作数

• 若右操作数类型为左操作数类型子类，且字类提供如下反射方法

  • 右操作数反射方法优先于左操作数非反射方法被调用
  • 允许子类覆盖祖先类运算符

• 三元版pow()不会尝试调用__rpow__（转换规则太复杂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def object.__radd__(self, other):
	# `+`
def object.__rsub__(self, other):
	# `-`
def object.__rmul__(self, other):
	# `*`
def object.__rmatmul__(self, other):
	# `@`
def object.__rtruediv__(self, other):
	# `/`
def object.__rfloordiv__(self, other):
	# `//`
def object.__rmod__(self, other):
	# `%`
def object.__rdivmod__(self, other):
	# `divmod()`
def object.__rpow__(self, other[, modulo=1]):
	# `pow()`/`**`
	# 若要支持三元版本内置`pow()`函数，应该接受可选的第三个
		# 参数
def object.__rlshift__(self, other):
	# `<<`
def object.__rrshift__(self, other):
	# `>>`
def object.__rand__(self, other):
	# `&`
def object.__ror__(self, other):
	# `|`
def object.__rxor__(self, other):
	# `~`

扩展算术赋值

实现以下方法实现扩展算数赋值

• 以下方法应该尝试对自身进行操作

  • 修改self、返回结果（不一定为self）

• 若方法未定义，相应扩展算数赋值将回退到普通方法中

• 某些情况下，扩展赋值可导致未预期错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def object.__iadd__(self, other):
	# `+=`
def object.__isub__(self, other):
	# `-=`
def object.__imul__(self, other):
	# `*=`
def object.__imatmul__(self, other):
	# `@=`
def object.__itruediv__(self, other):
	# `/=`
def object.__ifloordiv__(self, other):
	# `//=`
def object.__imod__(self, other):
	# `%=`
def object.__ipow__(self, other[, modulo=1]):
	# `**=`
def object.__ilshift__(self, other):
	# `<<=`
def object.__irshift__(self, other):
	# `>>=`
def object.__iand__(self, other):
	# `&=`
def object.__ior__(self, other):
	# `|=`
def object.__ixor__(self, other):
	# `~=`

一元算术运算

1
2
3
4
5
6
7
8

def object.__neg__(self):
	# `-`
def object.__pos__(self):
	# `+`
def object.__abs__(self):
	# `abs()`
def object.__invert__(self):
	# `~`

类型转换运算

1
2
3
4
5
6

def object.__complex__(self):
	# `complex()`
def object.__int__(self):
	# `int()`
def object.__float__(self):
	# `float()`

整数

1
2

def object.__index__(self):
	pass

• 存在此方法表明对象属于整数类型

  • 必须返回整数
  • 为保证以一致性，同时也应该定义__int__()，两者返回 相同值

• 调用此方法以实现operator.index()、或需要无损的转换为 整数对象

  • 作为索引、切片参数
  • 作为bin()、hex()、oct()函数参数

精度运算

1
2
3
4
5
6
7
8

def object.__round__(self[, ndigits]):
	# `round()`
def object.__trunc__(self):
	# `math.trunc()`
def object.__floor__(self):
	# `math.floor()`
def object.__ceil__(self):
	# `math.ceil()`

• 返回值：除__round__中给出ndigits参数外，都应该为 原对象截断为Integral（通常为int）

• 若未定义__int__，则int回退到__trunc__

元属性查找

• 元属性查找通常会绕过__getattribute__方法，甚至包括元类

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  class Meta(type): def __getattribute__(*args): print("Metaclass getattribute invoked") return type.__getattribute__(*args) class C(object, metaclass=Meta): def __len__(self): return 10 def __getattribute__(*args): print("Class getattribute invoked") return object.__geattribute__(*args) if __name__ == "__main__": c = C() c.__len__() # 通过实例显式调用 # 输出`Class getattribute invoked\n10" type(c).__len__(c) # 通过类型显式调用 # 输出`Metaclass getattribute invoked\n10" len(c) # 隐式查找 # 输出`10`

  • 为解释器内部速度优化提供了显著空间
  • 但是牺牲了处理特殊元属性时的灵活性
    • 特殊元属性必须设置在类对象本身上以便始终一致地 由解释器发起调用

• 隐式调用元属性仅保证元属性定义在对象类型中能正确发挥 作用

  1 2 3 4 5 6 7 8

  class C: pass if __name__ == "__main__": c = C() c.__len__() = lambda: 5 len(c) # `rasie TypeError`

  • 元属性定义在实例字典中会引发异常
  • 若元属性的隐式查找过程使用了传统查找过程，会在对类型 对象本身发起调用时失败

  • 可以通过在查找元属性时绕过实例避免

    1 2	>>> type(1).__hash__(1) == hash(1) >>> type(int).__hash__(int) == hash(int)

上下文管理器协议

上下文管理器：定义了在执行with语句时要建立的运行时上下文 的对象

• 上下文管理器为执行代码块，处理进入、退出运行时所需上下文

  • 通常使用with语句调用
  • 也可以直接调用协议中方法方法

• 典型用法

  • 保存、恢复各种全局状态
  • 锁、解锁资源：避免死锁
  • 关闭打开的文件：自动控制资源释放

• 可利用contextlib模块方便实现上下文管理器协议

__enter__

1
2

def contextmanager.__enter__(self):
	pass

• 用途：创建、进入与当前对象相关的运行时上下文

  • 在执行with语句块前设置运行时上下文

• 返回值

  • with子句绑定方法返回值到as子句中指定的目标，如果 方法返回值

__exit__

1
2

def contextmanger.__exit__(self, exc_type, exc_value, traceback):
	pass

• 用途：销毁、退出关联到此对象的运行时上下文

  • with语句块结束后，__exit__方法触发进行清理工作
  • 不论with代码块中发生什么，即使是出现异常， __exit__控制流也会执行完

• 参数：描述了导致上下文退出的异常，正常退出则各参数为 None

  • exc_type
  • exc_value
  • traceback

• 返回值：布尔值

  • 若上下文因异常退出
    • 希望方法屏蔽此异常（避免传播），应该返回真值， 异常被清空
    • 否则异常在退出此方法时将按照正常流程处理
  • 方法中不应该重新引发被传入的异常，这是调用者的责任

例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

from socket import socket, AF_INET, SOCK_STREAM

class LazyConnection:
	def __init__(self, address, family=AF_INET, type=SOCK_STREAM):
		self.address = address
		self.family = family
		self.type = type
		self.connections = []

	def __enter__(self):
		sock = socket(self.family, self.type)
		sock.connect(self.address)
		self.connections.append(sock)
		return self.sock

	def __exit__(self, exc_ty, exc_val, tb):
		self.connections.pop().close()

from functools import partial

def test():
	conn = LazyConnection("www.python.org", 80))
	with conn as s1:
		# `conn.__enter___()` executes: connection opened
		s.send(b"GET /index.html HTTP/1.0\r\n")
		s.send(b"Host: www.python.org\r\n")
		s.send(b"\r\n")
		resp = b"".join(iter(partial(s.recv, 8192), b""))
		# `conn.__exit__()` executes: connection closed

		with conn as s2:
			# 此版本`LasyConnection`可以看作是连接工厂
			# 使用列表构造栈管理连接，允许嵌套使用
			pass

迭代器协议

• 可迭代对象：实现__iter__方法的对象
• 迭代器对象：同时实现__next__方法的可迭代对象

• 使用collections.abc模块判断对象类型

__iter__

1
2

def object.__iter__(self):
	pass

• 用途：创建迭代器对象，不负责产生、返回迭代器元素

  • 容器对象要提供迭代须实现此方法
    • 容器支持不同迭代类型，可以提供额外方法专门请求 不同迭代类型迭代器
  • 迭代对象本身需要实现此方法，返回对象自身
    • 允许容器、迭代器均可配合for...in...语句使用

• 返回值：迭代器对象

  • 映射类型应该逐个迭代容器中键
  • 内置钩子函数：iter()

• 此方法对应Python/C API中python对象类型结构体中 tp_iter槽位

__next__

1
2

def object.__next__():
	pass

• 用途：从迭代器中返回下一项

  • 若没有项可以返回，则raise StopIteration
  • 一旦引发raise StopIteration，对后续调用必须一直 引发同样的异常，否则此行为特性无法正常使用

• 返回值：迭代器对象中下个元素

  • 映射类型返回容器中键
  • 内置钩子函数：next()

• 此方法对应Python/C API中python对象类型结构体中 tp_iternext槽位

协程/异步

__await__

1
2

def object.__await__(self):
	pass

• 用途：用于实现可等待对象

• 返回值：迭代器

  • 钩子运算：await

• asyncio.Future实现此方法以与await表达式兼容

Awaitable Objects

可等待对象：异步调用句柄，等待结果应为迭代器

• 主要是实现__await__方法对象

  • 从async def函数返回的协程对象

• type.coroutine()、asyncio.coroutine()装饰的生成器 返回的生成器迭代器对象也属于可等待对象，但其未实现 __await__

• 协程对象参见cs_python/py3ref/dm_gfuncs
• py3.7前多次await可等待对象返回None，之后报错

异步迭代器协议

• 异步迭代器常用于async for语句中

• 其他参见迭代器协议

__aiter__

1
2

def object.__aiter__(self):
	pass

• 用途：返回异步迭代器对象，不负责产生、返回迭代器元素
  • 返回其他任何对象都将raise TypeError

• 其他参见__iter__方法

__anext__

1
2

async def object.__anext__(self):
	pass

• 返回：从异步迭代器返回下个结果值

  • 迭代结束时应该raise StopAsyncIteration

• 用途

  • 在其中调用异步代码

• 其他参见__next__方法

例

1
2
3
4
5
6
7
8
9
10

class Reader:
	async def readline(self):
		pass
	def __aiter__(self):
		return self
	async def __anext__(self):
		val = await self.readline()
		if val == "b":
			raise StopAsyncIteration
		return val

异步上下文管理器协议

• 异步上下文管理器常用于async with异步语句中

• 其他参见上下文管理器协议

__aenter__

1
2

async def object.__aenter__(self):
	pass

• 用途：异步创建、进入关联当前对象的上下文执行环境

  • 由async def定义为协程函数，即在创建上下文执行环境 时可以被挂起

• 返回：可等待对象

• 其他参见__enter__

__aexit__

1
2

async def object.__aexit__(self):
	pass

• 用途：异步销毁、退出关联当前对象的上下文执行环境

  • 由async def定义为协程函数，即在销毁上下文执行环境 时可以被挂起

• 返回：可等待对象

• 其他参见__exit__函数

并发和并行

• Parallel：并行，同时做多件事情，关于执行、实现
• Concurrent：并发，能够处理多件事情，关于结构、逻辑

• 并发问题可以使用并行方式解决，也可以串行解决

  • 100并发任务同时运行在4核CPU上，最多可能有4个并发任务 并行处理，其余只能是串行处理

• 并行角度：硬件技术的物理限制瓶颈

  • 单计算核心能力不足，所以需要多核并行运算
  • 进程、线程可认为是实现并行的基本逻辑实体

• 并发角度：程序执行的逻辑重用需求

  • 程序要求重用一组逻辑，所以需要将一组指令集打包，重复 调用该组指令集
  • 子程序、协程可认为是方便重用的基本逻辑实体，因此更 应是语言内建机制
    • 子程序：无状态保存，同样重入得到同样结果
    • 协程：有保存状态，重入会改变协程状态，结果可能 不同

• 线程作为任务执行的实体，可以认为是子程序、协程的具体执行

  • 内核线程作为可以独立执行的实体，逻辑上更会被设计为 完成独立任务，即没有保存状态需求，因此多是子程序的 具体执行
  • 用户线程则用程序负责调度，二者执行实例均可
  • 某种意义上线程、子程序是对应的执行实体、逻辑实体

子程序、协程

• 子程序可以看作时协程的特例
  • 只有一个状态，每次进入时局部状态重置
  • 唯一入口点
• 协程可视为子程序的组成
  • 维护自身状态，所以逻辑上不独立 ，应该是作为被 调用对象
  • 对于每次返回部分结果值的协程（也称生成器迭代器）， 可以直接视为类似链表之类的数据结构 （在某些语言中可以所有数据都是类，从这个角度这也都是 统一的）

• 现代指令集通常提供对调用栈的指令支持，便于实现可递归 调用的子程序，在提供续体的语言环境（如Scheme），恰好 可用此抽象状态表示实现协程

Subroutine/Procedure/Function/Routine/Method

子程序：打包为整体、用于执行特定任务的指令集序列

• 子程序是依赖可重入能力的弱化版本

  • 一旦唤醒，于起始点开始执行
  • 一旦退出，子程序结束
  • 子程序实例只返回一次，两次激活间不保存状态

• 子程序中局部变量在每次调用/重入函数时都是相同的

  • 相同输入得到相同输出

• procedure：过程，有时特指无返回值、仅有副作用

线程安全

线程安全：子程序在多线程环境调用时，能够正确处理多个线程之间 的共享变量，使程序功能能正确完成

• 线程安全函数应该为每个调用其的线程分配专门空间，存储需要 单独保存的状态

• Atomicity：原子性，操作不会被线程调度机制打断，一旦 开始就会运行到结束，中间不会有任何线程切换

  • 可以通过lock、synchronized确保原子性
• Visibility：可见性，某线程修改变量值后，其他线程能够 立刻感知
  • 一般可以通过volatile保证可见性，强制要求被修改值 从寄存器同步至主存
  • lock、synchronized也可以通过限制其他线程访问变量 的方式保证可见性
• Ordering：有序性/一致性，程序按照代码顺序执行
  • 可以通过volatile保证一定的有序性
  • 也可通过lock、synchronized提供单线程执行环境保证 有序性

Instruction Reorder

指令重排：编译器对无相互依赖的指令重新排序执行

• as-if-serial语义：指令可以为优化而重排序，但是必须保证 最终执行结果不变

  • 规则：重排序过程不破坏数据依赖关系
  • 只能保证单线程执行结果有效，但不保证多线程并发执行 的正确性

  

• happens-before原则：保证前后两个操作间不会被重排序，

  • 程序次序规则：线程中每个操作happens-before该线程中 任意后续操作
  • 锁定规则：锁的解锁happens-before加锁
  • volatile变量规则：volatile变量写操作happens-before 其读操作
  • 传递规则：若A happens-before B、B happens-before C，则A happens-before C
  • 线程启动规则：线程对象启动happens-before线程中每个 动作
  • 线程中断规则：线程中断方法的调用happens-before被 中断线程代码检测到的中断事件的发生
  • 线程终结规则：线程中所有操作happens-before线程的 终止检测
  • 对象终结规则：对象的初始化happens-before其final 方法的开始

• happens-before原则被JVM用于规定（跨线程）操作之间偏序 关系，若操作之间的关系可以由此原则退出，则两个操作有序

Reentrant

• A computer program or routine is described as reentrant if it can be safely executed concorrently; that is, the routine can be re-entered while it is already running

可重入函数：对于相同（合法）的函数参数，多次重复调用（包括 执行过程中被中断再重入）结果总是可预期的

• 可重入需要满足条件

  • 不在函数内部使用静态或全局数据，所有数据都由函数 调用者提供
    • 全局变量区
    • 中断向量表
  • 使用本地数据，或制作全局数据的本地拷贝保护全局数据
  • 不返回静态或全局数据
  • 不调用不可重入函数

• 不可重入后果主要体现在信号处理函数这样需要重入情况中， 若在信号处理函数中使用了不可重入函数，则可能导致程序错误

• 可重入函数总是线程安全的，反之不一定成立

  • 线程安全可以通过“并发不冲突”实现
  • 可重入则要求“并行不冲突”

Coroutine

协程：为非抢占式多任务产生子程序的程序组件，允许执行过程 中挂起、恢复

• 挂起、恢复：协程可以通过yield（让步）调用其他协程暂时 退出，之后可在退出位置恢复执行

  • 从协程角度看，这是调用其他协程而不是退出
  • 但实际是各协程之间是对称的，而不像子程序调用 中主调-被调关系
  • 这即暗含
    • 协程可包含多个入口点
    • 允许在不同入口点暂停、开始执行程序

• 局部状态维护：协程实例保持上次退出时状态

  • 则协程被唤醒时状态可能不同
  • 可能同时有多个给定协程实例

• 协程将原在子程序外、输入状态管理工作交由自身逻辑维护
• 原生不支持协程的语言也可以使用循环等构建
• 经典状态机、对象已经具有协程特性

用途

• 协程可以简化异步代码的实现，使得需要使用异步+回调的代码 可以使用看似同步方式写出

  • 协程本身只涉及状态保存、过程重入，和并发/异步无关系
  • 但协程本身蕴含的状态保存使得状态切换几乎无成本，适合 高并发任务

• 协程在线程中调度完全由用户控制，可以视为用户态轻量级线程

  • 避免陷入无效内核级别上下文切换造成的性能损失
  • 较线程在IO密集任务上性能上更好

进程、线程

• 这里仅讨论理论上的异同，不考虑各平台具体实现

• 进程：具有独立功能的程序关于某数据集合的一次运行活动
• 线程/子程序：进程内某特定任务的执行活动
• 协程：推广协作式多任务的子程序

• 进程、线程、协程可以看作是控制权逐渐从系统已经移交到自身 的过程

• 这里的协程强调其在实现方面的资源、调度特点，其与子程序间 功能差异参加cs_program/parallel/implementation
• 通信：参见cs_program/parallel/#todo
• 移植性：基于进程分支多进程和windows模型有很大冲突，往往 不能在windows平台上使用

Process

进程：具有独立功能的程序关于某数据集合的一次运行活动

• 进程是处于运行期的程序和相关资源的总称

  • 程序：代码、指令
  • 运行：对CPU的占用，逐渐发展为线程，标识进程中指令的执行
  • 资源：执行上下文，由进程内线程共享

• 从系统调度方面看

  • 进程是系统进行资源分配、调度的独立单位
  • 在系统中有进程控制块（进程描述符）描述进程相关信息， 系统通过此控制块控制系统相关行为

• 从资源分配方面看

  • 有独立的存储空间（虚拟寻址空间）
    • 独享的用户空间
    • 进程专用的“共享内核空间”
  • 可执行的程序代码

• 线程可能对系统是可感知的，则进程不定是资源分配的基本 单位
• Linux线程实现即类似进程，但不包含独立存储空间

调度角度

• 内核跟踪进程运行所需的状态信息（上下文）

  • 主存、虚拟内存内容
  • 寄存器文件值
  • 栈
  • 文件句柄

• 调度：分配CPU执行进程

  • 内核决定CPU控制权在进程间的转移

• 上下文切换：进程状态的记录、恢复、切换

  • 保存当前进程上下文、恢复新进程上下文
  • 通过处理器在进程间切换，实现单个CPU“看似”并发执行 多个进程
  • 上下文进程间切换开销比较大，但相对比较稳定安全

资源角度

• 独立内存空间/虚拟地址空间：每个进程“独占的”使用 内存、看到一致的存储器

• 用户空间

  • 程序代码、数据：对所有进程，代码从同一固定位置开始， 直接按照可执行目标文件的内容初始化
  • （运行时）堆：可在运行时动态扩展、收缩
  • 共享库：共享库代码和数据，如：C标准库、数学库
  • 栈：用于实现函数调用，运行时动态扩展、收缩，位于虚拟 地址空间顶部

• 内核空间

  • 内核虚拟存储器：内核总是驻留在内存中，为其保留地址 空间顶部
  • 不允许程序读写区域内容或直接调用内核代码定义的函数

Thread

线程：进程执行实体，进程中包含指令的执行活动

调度角度

• 线程是CPU调度、分派的基本单位，有时被称为轻量级进程 （在Linux系统中也是按照轻量级进程实现）

• 线程引入逻辑

  • 进程内部可能存在多个不同task，task需要共享进程数据
  • 同时task操作的数据具有独立性，多个task不需要按照时序 执行
  • task间需根据不同策略进行调度，因此产生了线程概念， 并被引入作为内核调度基本单位

• 线程：比进程更小的、能独立运行的基本单位

  • 线程能/是“独立运行”，但不一定能被内核感知到，也一定由 内核调度
  • 只能说线程是针对某个task的执行活动

资源角度

• 线程运行在进程的上下文中，共享同样代码和全局数据

  • 进程代码段、公有数据
  • 进程打开的文件描述符、信号的处理器
  • 进程当前目录
  • 进程用户ID、进程组ID

• 线程还独享某些个性以实现并发性

  • 线程ID：进程中唯一标识
  • 寄存器组值：线程间并发运行，线程有不同运行线索， 切换时需要保存当前线程的寄存器集合状态
  • 线程堆栈：独立函数堆栈保证线程内函数调用可以正常 执行，不受其他线程影响
  • 错误返回码：线程的系统调用错误可能未及时处理，独立 错误返回码避免其被其他线程修改
  • 线程的信号屏蔽码：线程感兴趣的信号不同，因此信号 屏蔽码应由自己管理
  • 线程优先级：线程需要像进程被调度，需要有相应的优先级

线程实现理论

User-Level Thread

用户级线程：由用户程序自身负责支持、调度

• 特点

  • 相当于实现自己的线程调度内核，实现线程数据结构、 创建、销毁、调度维护
  • 线程运行在内核（可感知的）进程内

• 优点

  • 即使系统不支持线程，也可通过库函数支持在系统中实现 真实的多线程
  • 线程只在用户态，减少内核态到用户态切换开销

• 缺点：线程对系统透明，对系统每个进程只有一个线程， 系统直接调用进程

  • 当线程进行系统调用而阻塞时，系统会阻塞整个进程
  • 用户空间没有时钟中断机制，若线程长时间不释放CPU， 会导致阻塞其他线程

Kernel-Level Thread

内核级线程：系统内核支持的线程，通过内核完成线程切换

• 优点/特点：系统负责线程的创建、销毁、调度、维护

  • 内核通过操纵调度器对线程进行调度，并负责将线程 的任务映射到各个处理器上
  • 程序可以直接使用系统调用已实现线程，无需实现线程 调度、对CPU资源抢占使用

• 缺点：内核线程需要内核支持

  • 创建、销毁、调度、维护往往都需要系统调用，代价较高
  • 需要消耗内核资源，不能大量创建

线程调度模型

• X对Y是指X task对应Y内核调度单位

N对1模型

N对1模型：线程库有实现用户级线程，内核未实现内核级线程

• 系统只负责调用进程
• 线程对系统透明，由进程自身负责调用

• 此模型中内核没有实现内核级线程，所以内核调度单位就是进程 S

  1对1模型

1对1模型：线程库未实现用户级线程，内核实现有内核线程

• 程序（逻辑）层面

  • 创建执行独立task的线程
  • 程序创建的线程直接由内核负责调度

• 内核（实现）层面

  • 每次创建线程都是调用系统调用创建内核级线程
  • 可视为每个“用户创建的线程”同内核级线程绑定，二者一一 对应

• 此模型中内核调度单位就是内核级线程
• 此模型中不存在上述定义的用户级线程，图中Thread实际上 应该就是Kernel Thread，仅拆分出来表示是程序创建的线程

M对N模型

M对N模型：线程库实现有用户级线程，系统也实现有内核级线程

• 程序（逻辑）层面

  • 创建执行独立task的用户级线程
  • 创建可独立被内核调度的内核级线程
  • 将若干和用户线程同内核线程相关联，即task组总体由内核 负责调度，task组内task由程序自身负责调度

• 内核（实现）层面

  • 调用系统调用创建内核级线程
  • 内核线程执行指令中包含用户线程创建、调度指令

• 优点

  • 用户级线程创建、切换、析构等均在用户空间中，依然 廉价，支持大规模用户线程并发
  • 内核级线程作为用户线程在内核中调度、执行的桥梁， 降低整个进程被完全阻塞的风险

• 此模型中内核调度单位为内核级线程、task单位为用户线程， 二者比例不定
• 有的说法里面会使用Light Weighted Process表示内核级线程

通用调度算法

• 耗时相差不大的task队列总是比较好处理，难以调度的task是

  • 耗时相差大
  • IO任务、计算任务混合

• 内核调度除考虑任务（线程）外，还会考虑进程因素

  • Gang Scheduling：尽量将同进程中线程同时调度，而非 随机从多个进程中挑选CPU数量线程调度
  • Space Sharing：将CPU划分，各进程仅允许占用部分CPU 执行并发

• 从任务角度，调度需要考虑

  • Responsiveness
  • Schedule Overload
  • Starvation-Freedom：饥饿避免
  • Fairness

First-In-First-Out

先进先出：按task在队列中的顺序依次调用，执行完task再执行下个 task，仅在task结束后才会切换task

• 优点

  • 最少task切换开销
  • 最大吞吐量（总处理效率）
  • 朴实公平

• 缺点

  • 平均相应时间高

Shortest task First/Shortest Remained Time task

最短耗时task优先：有限调度耗时短task

• 优点

  • 平均相应时间短：长耗时task不断推移，必然统计出较短 平均响应时间

• 缺点

  • 不公平，长耗时task难被调度，容易饥饿
  • 频繁task切换，调度额外开销大

Round Robin

时间片轮转：给队列中每个task时间片，时间片结束之后task移至 队列末尾，切换到执行下个task

• 优点

  • 每个task可以得到公平调度
  • 耗时短task即使在耗时长task之后也可以较快得到执行

• 缺点

  • task切换引起的调度开销大，需要多次切换task上下文
  • 时间片不好设置
    • 时间片足够小则退化为SFJ
    • 时间片足够大则退化为FIFO
  • 需要知道task（剩余）执行时间

(Weighted) Max-Min Fairness

（带权重的）最大最小公平：资源按照需求递增的顺序分配，不存在 需求得到资源超过自身需求，未得到满足得到需求等价分享资源

• 具体方案
  • 每轮开始将资源按照权重分配
  • 若需求大于被分配资源则推迟执行，进入下轮
  • 若需求小于被分配资源则执行，并将多余资源继续按照权重 分配给无法执行资源

Multi-level Feedback Queue

多级反馈队列：监控task处理耗时，若task未用尽分配资源则提高 优先级，否则降低其优先级

• 具体方案

  • task、分片时长具有相对应的不同优先级
    • 分片时长越长优先级越低
    • 高级优先级task可以抢占低优先级task
    • 新task位于高优先级task
  • 同一优先级task使用Round Robin （事实上仅有最低优先级task使用Round Robin算法， 其他优先级都是FIFO）
    • 时间片用完后task结束则正常退出系统，否则优先级 下滑一等级
    • 若是主动让出CPU（IO等），则停留在当前优先级或 提升

• 多核场景

  • 应该为每个CPU分配单独MFQ，同时采用 Affinity Scheduling保证task尽量同一CPU核上执行， 避免CPU cache频繁失效
  • 若共用MFQ，则容易出现
    • 随CPU增长，对MFQ锁争抢严重
    • task每次执行位于的CPU不同，CPU Cache需要在不同 CPU间转移

同步问题

生产者-消费者问题/缓存绑定问题

• 生产者生成数据放入缓存，消费者从缓存获取、移除、消费数据 ，问题核心在于保证不让生产者在缓存已满时放入数据、不让 消费者在缓存为空时读取数据

• 若缓存满：生产者者停止工作
• 若缓存空：消费者停止消费
• 消费者从缓存中取走数据，通知生产者工作
• 生产者向缓存中放入数据，通知消费者消费

• 不完善的解决方案会造成死锁：生产者、消费者均等待对方唤醒

信号量解决方案

• mutex信号量：互斥信号量，确保只有一个生产者、消费者 操作缓存区，单一消费者、生产者可省略此信号量
• fill_count信号量：已使用缓存区数量
• empty_count信号量：空闲缓存区数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

semaphore mutex = 1
semaphore fill_count = 0
semaphore empty_count = BUFFER_SIZE

producer():
	while true:
		item = produce_item()
		down(empty_count)
		down(mutex)
		put_item_into_buffer(item)
		up(mutex)
		up(fillcount)

consumer():
	while true:
		down(fill_count)
		down(mutex)
		item = remove_item_from_buffer()
		up(mutex)
		up(empty_count)
		consume_item(item)

状态监控解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

item_count = 0
condition full
condition empty

add(item):
	while item_count == BUFFER_SIZE:
		wait(full)

	item_count = item_count + 1
	put_item_into_buffer(item)

	if item_count == 1:
		notify(empty)

remove():
	while item_count == 0:
		wait(empty)

	item_count = item_count - 1
	item = remove_item_from_buffer()

	if item_count == BUFFER_SIZE - 1:
		notify(full)

produer():
	while true:
		item = produce_item()
		add(item)

consumer():
	while true:
		item = remove()
		consume_item(item)

• 互斥信号没有保护关键区，监控方法更好

其他

• 协调生产者、消费者的关闭

  • 可在在队列中放置特殊的值，消费者读到时终止执行，结束 消费者线程
  • 有多个消费者时，消费者读取特殊值之后可将特殊值放回 队列中继续传递，直至关闭所有消费者

哲学家就餐问题

• 哲学家围坐在圆桌旁，只能吃饭或者思考，每两个哲学家 之间只有一根筷子，只有同时拿到左右两根筷子才能正常吃饭

• 实际计算机问题中，筷子视为共享资源

服务生

• 引入服务生判断资源是否能被获取

• 引入服务生，哲学家必须经过其允许才能拿起筷子

• 服务生知道有哪些筷子正在被使用，能够判断是否会死锁

资源分级

• 为资源（筷子）分配偏序关系

  • 约定所有资源都按此偏序获取、相反顺序释放
  • 且保证不会有无关资源同时被同一工作获取

• 哲学家只能拿左右侧筷子：不会有无关资源被同一工作获取

• 将筷子按顺序编号：资源分配偏序关系

  • 哲学家只能先拿左右筷子中编号较小者
  • 哲学家需要先放下筷子中编号较大者

• 最实用的解法：为锁指定常量分级，强制获取顺序的顺序
• 策略不总是实用的，尤其是所需资源列表事先不知道，可能需要 先释放已获取资源、获取低编号资源、重新获取资源，效率不高

Chandy/Misra解法

• 标记资源，保留未使用资源、交出已使用资源，初始所以资源 已使用

• 每根筷子分为干净、脏，最初所有筷子都脏

• 对每对竞争同一筷子的哲学家，新拿筷子给编号较低者

• 当哲学家需要某筷子时

  • 向其竞争对手发送请求
  • 拥有筷子的哲学家收到请求
    • 若筷子干净则保留
    • 否则擦干净交出

• 哲学家吃完东西后，筷子变脏

  • 若有哲学家之前请求过该筷子，擦干净交出

• 有很大并行性，适合任意大问题

读者-写者问题

• 多线程同时访问共享内存地址，线程写入时其他线程不能读取、 写入，多个线程可以同时读取

• 一般使用readers-writer lock解决问题

读者优先

• 若共享内存被读取，其他读者可以立即、同时读取
• 若一直有读者开始读取，则写者会一直被插队、无法修改

写者优先

• 如果写者在排队，应该尽快写入共享内存
• 若一直有写者准备写入，则读者会一直被插队、无法读取

限定时间

• 共享内存区的锁定权要在限定时间内结束
• 能避免读者、写者一直排队

熟睡的理发师问题

• 理发店只有一名理发师、一张理发时坐的椅子、若干普通椅子 供顾客等待

  • 没有顾客时理发师在理发椅子上睡觉，顾客到达后离开、 或者叫醒理发师
  • 有顾客时，理发师为别人立法，顾客达到后若有空闲普通 椅子则坐下休息、否则离开
  • 理完发后，任选顾客开始理发

• 理发师等待顾客、顾客等待理发师，造成死锁
• 有顾客不按顺序等待，让某些顾客永远不能理发

3信标解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

semaphore customer = 0
semaphore barber = 0
semaphore mutex = 1
empty_chairs = BUFFER_SIZE

barber():
	while true:
		if empty_chairs == BUFFER_SIZE:
			sleep()

		down(mutex)
		item = get_customer_from_chairs()
		empty_chairs += 1
		up(mutex)

		down(barber)
		cut_hair(item)
		up(barber)

customer():
	while true:
		down(mutex)
		if empty_chairs > 0:
			empty_chairs -= 1

		else:
			wait() or leave()

		up(mutex)

三个烟鬼问题

• 香烟需要：烟草、卷烟纸、火柴，三个烟鬼分别有无限各一种， 不吸烟协调人会随机安排两个烟鬼各拿出一份材料放在桌上， 另外一个烟鬼拿到材料卷烟、抽

  • 桌上空了后，协调人就随机要求烟鬼拿出材料
  • 烟鬼只会在抽完手中烟后才会卷另一只
  • 若烟草、卷烟纸在桌上，有火柴的烟鬼在吸烟，直到该烟鬼 吸完烟拿走桌上材料才会继续

• 问题模拟程序中4种角色，展示信标方法作用有限

Heap

堆/大根堆：每个节点包含一个键、且大于等于其子女键、基本完备 的二叉树

• 认为非叶子节点自动满足大于其子女键值
• 根到某个叶子节点路径上，键值序列递减（允许键值相等则是 非递增）
• 键值之间没有从左到右的次序，即树的同一层节点间没有任何 关系，或者说左右子树之间没有任何关系

堆特性

• 完全二叉树特性参见完全二叉树
• 堆的根总是包含了堆的最大元素
• 堆的节点及该节点子孙也是一个堆

• 堆这种数据结构经常被用于实现优先队列

最小堆

min-heap：（最大）堆的镜像

• 堆的主要特性最小堆也满足，但
  • 最小堆根节点包含最小元素
• 可通过给元素取反构造（最大）堆得到最小堆

堆算法

Bottom-Up Heap Construction

自底向上堆构造：先利用所有元素构造二叉树，从倒数第二层开始 修改使得整棵树满足堆要求

算法

• 将给定线性表对应为（初始化）一棵完全二叉树
• 对二叉树进行堆化，从最后父母节点开始、到根为止，算法检查 节点键是否满足大于等于其子女键
  • 若不满足，交换节点键K和其子女最大键值
  • 在新位置上检查是否满足大于子女键值，直到满足为止
• 对以当前节点为根的子树满足堆化条件后，算法对节点直接前趋 进行检查，直到树根满足堆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

HeapAdjust(H[0..n-1], cur):
	// 左右子树已经为堆，仅根节点元素不一定满足
	// 输入：待调整堆H、根节点cur，cur左右子树已经为堆
	// 输入：调整后堆
	while 2*cur+2 < n:

		// 获取左右子女中最大者
		if 2*cur+2 < n:
			_tmp = argmax(H[2*cur+1], H[2*cur+2])
		else:
			_tmp = 2*cur+1

		// 交换自身和最大子女
		if H[_tmp] > H[cur]:
			swap(H[cur], H[_tmp])
			cur = _tmp
		else:
			// 从底向上建堆，左、右子树均为堆
			// 则此时已经满足堆性质
			break

	return H

HeapBottomUp(H[0..n-1]):
	// 用自底向上算法，从给定数组元素中构造一个堆
	// 输入：可排序数组H[0..n-1]
	// 输出：堆H[0..n-1]
	for i=floor((n-1)/2) to 0:
		HeapAdjust(H, i)
	return H