Posted 2019-03-26Updated 2021-07-19Probability2 minutes read (About 329 words)

概率不等式

Inequality

Azuma-Hoeffding Inequality

Azuma-Hoeffding 不等式：设 ${Xi:i=0,1,2,\cdots}$ 是鞅差序列，且 $|X_k - X{k-1}| < c_k$，则

$\begin{align*} super-martingale: P(X_N - X_0 \geq t) \leq exp \left ( \frac {-t^2} {2\sum^N_{k=1} c_k^2} \right ) \\ sub-martingale: P(X_N - X_0 \leq -t) \leq exp \left ( \frac {-t^2} {2\sum^N_{k=1} c_k^2} \right ) \\ martingale: P(|X_N - X_0| \geq t) \leq exp \left ( \frac {-t^2} {2\sum^N_{k=1} c_k^2} \right ) \end{align*}$

Hoeffding Inequality

Hoeffding 不等式：考虑随机变量序列 $X_1, X_2, \cdots, X_N, X_i \in [a_i, b_i]$

对随机变量 $\bar X = \frac 1 N \sum_{i=1}^N {X_i}$，对任意 $t>0$ 满足
$\begin{align*} P(\bar X - E \bar X \geq t) \leq exp(\frac {-2N^2t^2} {\sum_{i=1}^N (b_i - a_i)^2} ) \\ P(E \bar X - \bar X \geq t) \leq exp(\frac {-2N^2t^2} {\sum_{i=1}^N (b_i - a_i)^2} ) \\ \end{align*}$
对随机变量 $SN = \sum{i=1}^N X_i$，对任意 $t>0$ 满足
$\begin{align*} P(S_N - E S_N \geqslant t) & \leqslant exp \left ( \frac {-2t^2} {\sum_{i=1}^n (b_i - a_i)^2} \right ) \\ P(E S_N - S_N \geqslant t) & \leqslant exp \left ( \frac {-2t^2} {\sum_{i=1}^n (b_i - a_i)^2} \right ) \\ \end{align*}$

两不等式可用绝对值合并，但将不够精确

Bretagnolle-Huber-Carol Inequility

Bretagnolle-Huber-Carol 不等式：${X_i: i=1,2,\cdots,N} i.i.d. M(p1, p_2, \cdots, p_k)$ 服从类别为 $k$ 的多项分布

$p{\sum_{i=1}^k |N_i - Np_i| \geq \epsilon} \leq 2^k exp \left ( \frac {- n\epsilon^2} 2 \right )$

$N_i$：第 $i$ 类实际个数

Posted 2019-03-24Updated 2019-03-24Algorithm / Data Structure15 minutes read (About 2182 words)

无向图衍生

Bipartite Graph

二分图：所有顶点可以分为两个不相交集合U、V，两个集合大小不定相等，但每条边都连接两个集合中各一顶点

可以证明：当且仅当图中不存在奇数长度回路时，为二分图
二分图中顶点可以可以染成两种颜色，使得每条边两头顶点颜色不同
矩阵存储二分图时，因为U、V内部节点之间无边，大部分场景只需要$|V| * |U|$的矩阵（对有序、加权适用）
性质
- 二分图匹配意义：同类型（集合内部）之间没有连接

Augmenting-Path

（二分图）增益路径：对合法匹配M，简单路径两端连接V、U中的自由顶点，路径中边交替出现在$E-M, M$中，称M的增益路径

增益路径长度总为奇数，为M中匹配两倍+1
则路径中奇数边组成新的匹配，比M多一条边

增益路径-最大匹配证明

当且仅当G中不存在M增益路径时，M为G最大匹配

必要性

若M存在增益路径，则可以扩展M得到更多匹配，M不是最大匹配

充分性

若存在M无增益路径，但不为最大匹配，设$M{}$是G中的最大匹配，则$M{}$中边至少比M中边数量大1，有 $|M^{}| > |M|, |M^{} - M| > |M - M^{*}|$
则两者对称差集为 $M \bigoplus M^{} = (M - M^{}) \cup (M^{*} - M)$
设$G^{‘} \subseteq G$为二者差集中所有边、点，根据匹配定义，$G^{‘}$中任何单个点和$M, M^{*}$相连接不会超过一条边
则$G^{‘}$中顶点连通度不大于2，其中连通分量为
- 偶数长度回路，其中边交替属于 $|M^{} - M|, |M - M^{}|$，在两者中数量相同
  - 若不交替，则说明连续两条边在同个匹配中，有交点，和匹配定义冲突
  - 若不为偶数长度，同样的首、尾两条边在同一匹配中，和匹配定义冲突
- 交替路径（无环）
  - 因为$|M^{} - M| > |M - M^{}|$，所以$G^{*}$中不可能仅有回路
  - 所以至少存在一条具有交替边路径，起点终点都是 $M^{*} - M$同一条边（如单边路径），M具有增益路径，矛盾

最大匹配求解匈牙利算法实现详见graph

Konig Theorem

Konig定理：二分图中最大匹配数|M| = 最小点覆盖数|C|

已经通过匈牙利算法求出最大匹配M
从集合V中每个未被匹配点开始，走一条类似增益路径的交替路径，标记路径中的所有点
- 只是因为已经找到了最大匹配，所以路径另外一端不可能是自由顶点
- 允许重复走过同一条边
路径中V到U的均为非匹配边、U到V均为匹配边

当然也可以从U的所有未匹配顶点开始

记集合V中中未被访问、U集合中已被访问的已匹配顶点点集为C，则 $顶点数目|C| = 最大匹配数 = 最小点覆盖数$ biparttite_konig

因为每个点都是M中某边端点，且V中已标记同U中未标记、V中未标记顶点同U中已标记一一对应，为匹配边两端点，所以
$顶点数 = V中未被访问 + U中已访问 = \\ V中未访问 + V中已访问 = （最大）匹配数$
在最大匹配情况下，所有边至少有一个端点为已匹配点
- 对于匹配边，肯定被C中顶点覆盖
- 若非匹配顶点在V中，则一定在某个路径中被访问，则被U 中某个已访问匹配顶点覆盖
- 若非匹配顶点在U中，则被V中未访问顶点覆盖的
- 或者说不存在这样的边：其左端点没有标记、而右端点有标记
  - 匹配边肯定不是起点，不可能
  - 非匹配边，右端有标记则能直接访问左端，标记左端（通样广度优先搜索遍历所有邻接有顶点点）
而要覆盖匹配边需要至少$|M|$个点，所以$|M|$是最小覆盖点数

推论 1

二分图中：最小边覆盖|W| = 图中顶点数|V| - 最小点覆盖数|C|

$|W| = |V| - |M| = |V| - |C|$

Ordered Bipartite Graph

有序二分图：以同一顶点作为端点的边的有优先级（独立于其他点）

即：V中顶点对U中顶点都有优先级排序，U中顶点对V中顶点也有优先级排序

Marriage Matching

婚姻匹配问题可以使用特殊的完全有序二分图代表

集合V（男士集合）、U（女士集合）大小相同为n
任意男士、女士都有之间都有边连接，即任意男士、女士都需要给出所有女士、男士优先级

存储、表示方法

优先列表：各男士、女士按照异性优先级排序列表，共2n个
- 对实现匹配算法而言效率更高
等级矩阵：男士、女士为分别作为矩阵行、列，矩阵元素$P_ij$ 为男士$m_i$对女士$w_j$优先级排序、女士$w_j$对男士$m_i$ 优先级排序元组
- 更容易看出集合元素匹配
- 只需要$n * n$阶方阵

Stable Marriage Matching

对包含n个对的婚姻匹配M

Block Pair：受阻对，满足$m \in V, w \in U$，而$(m, w)$ 更倾向于对方，而不是匹配M中对象
Stable Marriage Matching：稳定婚姻匹配，不存在受阻对的婚姻匹配

稳定婚姻存在性

V中存在自由男士时，任选求婚、回应之一执行，直至不存在自由男士

求婚：自由男士m向女士w求婚，w为其优先级最大、之前未拒绝过其女士（可以是已匹配）

回应：若女士w自由则接受男士m求婚，与之配对；女士w不自由则把m同当前配偶匹配，选择其中优先级较高者

当不存在自由男士时，得到匹配M就是稳定匹配

若M是不稳定的，设存在受阻对$(m, w)$
因为m按照降序求婚，所以m必然在某次迭代向w求过婚，则w当前对偶必然比m拥有更高优先级，和受阻对假设矛盾

稳定婚姻问题求解算法参见graph

Weighted Bipartite Graph

加权二分图；每条边都有权重的二分图

Distribution Problem

分配问题可以使用特殊的完全加权二分图代表

集合V（人员集合）、U（任务集合）大小相同为n
任意人员、任务有边相连，人员、任务内部之间无边

存储方法

使用$n * n$阶成本矩阵C存储，其元素$c_{ij}$表示人员$i$ 完成任务$j$的成本
则问题转化为：从成本矩阵中每行分别选择元素，且元素不属于同一行，使得和最小

（最小成本）分配问题算法参见graph

Biconnected Graph

articulation point：关节点，删除顶点v、与v相连的各边之后，将图一个连通分量分割成两个、两个以上连通分量，则称顶点v为图的一个关节点

biconnected graph：重连通图，没有关节点的连通图

重连通图中任意一对结点之间至少存在两条路径
若在重连通图中至少删除k个顶点才能破坏图的连通性，则称图的连通度为k

求解关节点

利用DFS可以求出图的关节点，判断图是否是重连通的，对DFS生成树

生成树有两棵及以上子树，则根节点为关节点
- 因为不同子树之间不存在连通不同子树顶点的边
非叶子顶点v某棵子树中没有指向v前驱的回边，则v为关节点

算法参见algorithm/problems/graph

Posted 2019-03-23Updated 2019-03-23Algorithm / Data Structure4 minutes read (About 670 words)

无向图

点集

点覆盖集

Vertex Covering Set：点覆盖（集），顶点子集$S \subseteq V$ ，满足每条边至少有一个顶点在集合中
Minimum Vertex Covering Set：最小顶点覆盖集，最少顶点的点覆盖集

点支配集

Vertex Dominating Set：点支配集，顶点子集$D \subseteq V$ ，满足$\forall u \in V-D, \exists v \in D, (u, v) \in E$
- 即V中顶点要么是D中元素，要么同D中一个顶点相邻
Minimum Vertext Dominating Set：最小支配集，顶点数目最小支配集
极小支配集：真子集都不是支配集的支配集

点独立集

Vertext Independent Set：（点）独立集，顶点子集 $I \subseteq V$，满足I中任意两顶点不相邻
Maximum Vertext Independent Set：最大独立点集，顶点数最多的独立点集
极大点独立集：超集都不是独立集的独立集

性质

Thoerem 1

若无向图$G(V, E)$中无孤立顶点，则G的极大点独立集都是G的极小支配集（反之不成立）

Thoerem 2

一个独立集是极大独立集，当前且仅当其为支配集

Thoerem 3

若无向图$G=(V, E)$中无孤立点，顶点集$C \subseteq V$为G点覆盖，当且仅当$V - C$是G的点独立集

边集

边覆盖

Edge Covering Set：边覆盖（集），边子集$W \subseteq E$，满足$\forall v \in V, \exists e \in W$，使得v是e端点
- 即G中所有点都是便覆盖W的邻接顶点
Minimum Edge Covering Set：边数最少的边覆盖集
极小边覆盖集：任意真子集都不是边覆盖集的边覆盖

边独立集

Matching/Edge Indepdent Set：匹配（边独立集），边子集 $I \subseteq E$，满足I中所有边没有公共顶点
Maximum (Cardinality) Matching：最大（基数）匹配，包含最多边的匹配
极大匹配：任意超集都不是匹配的匹配
Perfect Matching：完美匹配，匹配所有点的最大匹配
Mate：对偶，匹配中相互连接的一对顶点

性质

Thoerem 1

M为G一个最大匹配，对G中每个M未覆盖点v，选取一条与v关联边组成集合N，则边集$W = M \cup N$为G中最小边覆盖

Thoerem 2

若W为G最小边覆盖，其中每存在相邻边就移去其中一条，设移去边集为N，则边集$M = W - N$为G中一个最大匹配

Thoerem 3

最大匹配、最小边覆盖满足：$|M| + |W|= |V|$

Posted 2019-03-23Updated 2021-08-02Algorithm / Data Structure3 minutes read (About 501 words)

图衍生

度

Laplacian矩阵

$L=D-A$：Laplacian矩阵，其中

$A$：邻接矩阵
$D$：度矩阵（对角线为各个顶点度）

性质

若$c$为图中各个节点权重，则$c^T L C$为各个节点与其邻接节点差值平方和
- 展开即可证明

边数量

Multigraph

多重图：含有平行边，即顶点之间边数大于1

允许顶点通过边和自己相连

边权

欧几里得类型加权图

欧几里得类型加权图：权重满足欧式几何条件

三角不等式：任意3点$i,j,k, d{ij} \leqslant d{ik}+d{kj}
对称性：任意两个点$i,j, d_{ij}=d{ji}$

连通性

Transitive closure

传递闭包：表示所有节点两两直接连通性的n阶布尔矩阵T

$T={t{ij}}$，若节点i到节点j直接存在有效（长度>0）有向路径，则$t{ij}=1$，否则为0

Hamiltonian Circuit

哈密顿回路：对图每个顶点只穿过一次的回路

可以理解为：n+1个相邻顶点的一个排列，其中首尾顶点相同，而其余顶点互不相同
- 因为是回路，可以不失一般性的假定回路开始、结束于相同顶点，这样不影响回路性质

Eular Circuit

欧拉回路：将给定图每条边都只遍历一次的回路

无向图：当且仅当连通多重图的每个顶点连通度都为偶数时，才具有欧拉回路
有向图：当且仅当图中所有顶点是否出度、入度相等时，才存在欧拉回路
在$\O(n^)$内解决问题

State-Space Graph

状态空间图：把问题化简为标准图问题

顶点：表示问题可能状态
边：表示状态之间的可能转换
原问题转换为求初始状态到目标状态顶点路径问题

Posted 2019-03-21Updated 2021-08-04CS / Program Design2 minutes read (About 351 words)

函数设计

Hook/Callback

callback：回调函数，实现与调用者分离
- 在API中注册、用于在处理流中的合适时刻调用的函数
- 可以看作是hook的一种
hook：钩子函数
- 更广义的、用于修改对API调用的函数
- callback、hook意义其实差不多，很多情况下名词混用
register：注册函数
- 提供参数作为hook的挂载点
- register通过挂载点调用hook

优点

让用户实现hook然后注册，框架调用用户自定义的hook，提供更好的泛用性
框架不再处理hook函数中涉及的问题，降低系统耦合程度
hook函数可以随时更换，提升框架的灵活性、扩展性

实现

函数指针作为函数参数，API通过函数指针调用函数实现定制API

`C`实现

 # include<stdlib.h>
 # include<stdio.h>

void populate_array(
	int *array, 
	size_t array_size,
	int (*get_next_value_hook)(void)
	// `get_next_value_hook`就是函数指针
	// hook的“挂载点”
){
	for (size_t i=0; i<array_size; i++){
		array[i] = get_next_value();
	}
}

int get_next_random_value(){
	return rand();
}

int main(){
	int array[10];
	poppulate_array(array, 10, get_next_random_value);
		// 这里`get_next_random_value`就是钩子函数
	for(int i=0; i<10; i++){
		printf("%d\n", array[i]);
	}
	printf("\n");
	return 0;

Python实现

python中虽然没有明确的C中的函数指针，但是实现原理仍然类似，都是“函数指针”作为参数，由API负责调用实现定制API

import random

populate_array(l, len, func):
	# `func`就类似于`C`中的函数指针，hook的挂载点
	for i in range(len):
		l[l] = func()

get_next_random_value():
	return random.random()

def test():
	l = [ ]
	populate_array(l, 10, get_next_random_value)
		# `get_next_random_value`就是钩子函数
	print(l)

Closure

闭包：一个函数及与其相关的组合

将回调函数与数据封装成单独的单元
实现方式
- 允许在函数定义的同时，使用函数内部变量支持闭包，如： python
- 使用特定数据结构实现闭包，如：C++使用函数类实现

Cache

固定大小：存储空间有上限
快速获取：插入、查找操作必须快速，最好$\in O(1)$
达到存储空间上限时可以替换已有缓冲项

Least Recently Used Cache

LRU Cache：优先排除least recently缓冲条目

function_design_lru_cache

hashmap存储键、节点地址：常数时间查找

双向链表存储数据：利用地址可常数时间插入、删除

缓冲条目每次被获取后，移至双向链表头
缓冲区满后，删除双向链表最后节点条目，新条目插入表头

https://medium.com/@krishankantsinghal/my-first-blog-on-medium-583159139237

Posted 2019-03-21Updated 2021-08-04CS / Program Design4 minutes read (About 610 words)

继承、Mixin

多重继承

多重继承问题

结果复杂化：相较于单一继承明确的父类，多重继承父类和子类之间的关系比较复杂
优先顺序模糊：子类同时继承父类和“祖先类”时，继承的方法顺序不明确
功能冲突：多重继承的多个父类之间可能有冲突的方法

多重继承优点

todo

解决方案

规格继承

使用inteface、traits这些结构实现“多重继承” （普遍意义上的单一继承）

类只能单一继承父类
但是可以继承多个interface、traits，其中只能包含方法，而没有具体实现

方案问题

即使继承interface也需要重新实现方法
只是通过规定解决多重继承的问题，但是也损失优点

弥补技巧delegate

delegate（代理）

对interface itf实现一个公用实现class impl
其他“继承”itf的类itf_cls声明一个itf类型的变量 itf_var
将公用实现的一个实例赋值给itf_var
这样itf_cls中interface itf方法的实现就可以直接使用 itf_var调用impl的方法

interface itf{
	pulic void itf_func()=0;
}

class itf_impl implements itf{
	public void itf_func(){
	}
}

class itf_cls implements itf, others{
	itf itf_var;

	public itf_cls(String args[]){
		itf_var = new itf_impl;
	}

	public void func(){
		itf_var.func();
	}
}

实现继承

方法+实现的集合，普遍意义上多重继承

类可以继承多个父类
多个父类没有要求其中不能包含方法的实现

方案问题

即多重继承的普遍问题

弥补技巧mixin

mixin（混入）

每个类只“逻辑上”继承一个类，其他只继承mixin类
- mixin类单一职责
- mixin对宿主类（子类）无要求
- 宿主类（子类）不会因为去掉mixin类而受到影响，不调用超类方法避免引起MRO查找顺序问题
mixin思想同规则继承
- 均是将父类划分为
  - 逻辑父类
  - 逻辑特性族
- 但是规则继承是禁止（普遍意义）多重继承，而mixin 只是有效方案，并没有从规则上真正禁止“多重继承”
- mixin对开发者要求更严格，需要自查是否符合mixin原则

class MixinCls:
	pass

class SubCls(SuperCls, MixinCls1, MixinCls2):
	pass

Posted 2019-03-21Updated 2021-08-04CS / Network6 minutes read (About 865 words)

ISO9001标准

OSI/RM

物理层

数据链路层

网络层

传输层

会话层

表示层

应用层

硬件

高层设备物理上兼并底层设备功能，逻辑上只考虑其该部分功能

RP repeater

中继器：连接网络线路的装置，信号放大器

最简单的网络互联设备
主要完成物理层功能

功能

双向转发两个网络节点的物理信号
在物理层上按位传递信息
完成信号的复制、调整、放大
延长网络的长度

Hub

集线器：多口中继器

局域网中的星形连接点
实现多台机器之间的互联

功能

基本功能是分发，把一个端口接收到所有信号向所有端口分发
有些在分发前将弱信号重新生成
有些会整理信号的时序以提供所有的端口间的同步数据通信

Bridge

网桥/桥接器：连接两个局域网的存储转发设备

工作在数据链路层
用于完成具有相同、相似体系结构、数量不多LAN的连接

功能

根据MAC地址转发帧
- 对所接收的信息帧只作少量包装，不做任何修改
- 可以采用另外一种协议转发信息
- 网桥有足够大的缓冲空间，以满足高峰期要求
- 具有寻址、路径选择能力
有效的连接两个LAN
- 限制本地通信在本网段内
- 转发相应信号至另一网段

Switch

交换机：采用交换技术增加数据输入输出总和、安装介质的带宽

可以理解为高级的网桥，拥有网桥的功能，性能比网桥强
交换机转发延迟很小，能经济把网络分成小的冲突网域

功能

Router

路由器：网络层上的连接

路由器在网络上处于关键地位
- 路由器能够跨越不同的网络类型
- 在逻辑上将整个互联网分割成独立的网络单位

功能

为每个数据帧寻找最佳传输路径，把数据（IP报文）传送到正确的网络

IP数据报的转发，包括数据报的寻址、传送
子网隔离，抑制广播风暴
维护路由表，与其他路由器交换路由信息，这是IP报文转发基础
IP数据报的差错处理、简单的拥塞控制
对IP数据报的过滤、记账

Gateway

网关：协议转换器，网络层上具有协议转换功能的设施

网关不一定是一台设备，可能在一台主机中实现网关功能
用于一下场合的异构网络互联
- 异构型局域网
- 局域网与广域网的互联
- 广域网与广域网的互联
- 局域网与主机相连（主机操作系统、网络操作系统不同时）

字体杂记

字体文件

TTF：Truetype Font
- 苹果公司创建，Mac 和 Win 上最常用的字体文件格式
- 由数学表达式定义、基于轮廓的字体文件
- 保证了屏幕、打印输出的一致性，同时也可以和向量字体一样随意缩放
TTC：TrueType Collection
- 微软开发的新一代字体文件，多个 TTF 文件合并而成
- 可以共用字体笔画文件，有效的节约空间
- 兼容性不如 TTF，有些应用无法识别
FON
- Win 上最小的字体文件格式
- 固定大小的位图格式，难以调整字体大小

字体分类

西文字体分类

西文字体分类方法有很多种，但是太学术，不常用，常用分类的可以看计算机字体族

Thibaudeau 分类法
- 法国字体排印师 Francis Thibaudeau 于 1921 年提出
Vox-ATypl 分类法
- Maximilien Vox 于1954年提出，是比较早、基础、业内有过影响力的分类法
Fontshop 自家的分类法
- 在已有的思路的基础上，基于字体开发的独特的分类法
- 适合网上搜索字体，网罗了超过 15 万字体
Linotype 提供的3种分类法
- by category + by usage+ by theme
- 后 2 者是面向一般字体用户，重视字体的用途来合理分类

中文字体分类

中文字体则没有一个明确的分类体系，仅能大概分类

宋体（明体）：最能代表汉字风格的印刷字头
仿宋：相当于雕版时代的魏碑体
楷体：标准化的楷书，毛体书法的产物
黑体：汉字在西方现代印刷浪潮冲击下的产物
圆体：海外地区率先开发、使用

计算机字体分类

serif：有衬线字体
- 特点
  - 笔画有修饰，末端向外展开、尖细或者有实际衬线
  - 文字末端在小号字体下容易辨认，大号可能模糊或有锯齿
- 例
  - Times New Roman、MS Georgia、DejaVu Serif
  - 宋体、仿宋
- 两种衍生字体
  - petit-serif：小衬字体，可以当作无衬线
  - slab-serif：雕版衬线，末端变化非常明显
san-serif：无衬线字体
- 特点
  - 末端笔画清晰，带有一点或没有向外展开、交错笔画
  - 与serif相比，字体较小时可能难以分辨、串行（阅读）
- 举例
  - MS Trebuchet、MS Arial、MS Verdana
  - 黑体、圆体、隶书、楷体
monospace：等宽字体
- 特点
  - 每个字形等宽，因此常作为终端所用字体
- 举例
  - Courier、MS Courier New、Prestige
  - 多数中文字体（中文字体基本都等宽）
cursive：手写字体
- 举例
  - Caflisch Script、Adobe Poetica
  - xx手写体、xx行草
fantasy：梦幻字体（艺术字）
- 举例
  - WingDings、WingDings2、Symbol
  - 各种奇怪名字的字体

serif、san-serif 是西文字体的两大分类

而后应该是计算机的出现带来的monospace的兴起

最后面两种在正式场合中不常用

Posted 2019-03-21Updated 2019-03-07C/C++9 minutes read (About 1401 words)

库

C++库结构

定义C++库时，需要提供：interface、implementation

类库向用户提供了一组函数、数据类型，以实现 programming abstraction
类库像函数一样，提供了可用于降低复杂度的方法，但也需要在建库时考虑更多细节，简化程度取决于接口设计的优劣

接口、实现

接口：允许库用户在不了解库实现细节的情况下使用库中库函数
- 典型接口可提供多种定义、声明，称为interface entry
  - 函数声明
  - 类型定义
  - 常量定义
实现：说明库的底层实现细节
C++接口通常写在.h头文件中，实现在同名.cpp文件

接口设计原则

unified：统一性，接口必须按照统一主题来定义一致的抽象
simple：简单性，接口必须向用户隐藏实现的复杂性
sufficient：充分性，接口必须提供足够功能满足用户的需求
general：通用性，良好设计的接口必须有高度适用性
stable：稳定性，接口在函数底层实现改变时也要有不变的结构、功能

使用

$ g++ -o a.out src.cpp -L /path/to/library -l lib_name
	// 动态、静态链接库均可
	// `-L`指定（额外）库文件搜索路径
$ g++ -o a.out src.cpp liblib_name.a
	// 静态链接库可以类似于`.o`文件使用

编译时使用指定链接库名只需要指定lib_name，编译器自动解析为lib[lib_name].so
gcc/ld为可执行文件链接库文件时搜索路径
- /lib、/usr/lib64、/usr/lib、/usr/lib64
- LIBRARY_PATH中包含的路径

Static Link Library

静态链接库.a/.lib：二进制.o中间目标文件的集合/压缩包

链接阶段被引用到静态链接库会和.o文件一起，链接打包到可执行文件中
程序运行时不再依赖引用的静态链接库，移植方便、无需配置依赖
相较于动态链接库浪费资源、空间
相较于.o二进制的文件，管理、查找、使用方便

生成静态链接库

linux下使用ar、windows下使用lib.exe，即可将目标文件压缩得到静态链接库

库中会对二进制文件进行编号、索引，以便于查找、检索

1
2
3

$ g++ -c src.cpp src.o
$ ar -crv libsrc.a src.o
	// 生成静态库`libsrc.a`

linux下静态库命名规范：lib[lib_name].a（必须遵守，因为链接时按此规范反解析名称）

Dynamic Link Library

动态链接/共享库.so/.dll

动态链接库在程序链接时不会和二进制中间文件一起，被打包进可执行文件中，而时在程序运行时才被 dynamic linker/loader载入
不同程序调用相同库，在内存中只需要该共享库一份实例，规避空间浪费、实现资源共享
解决了静态库对程序更新、部署、发布的麻烦，可以通过仅仅更新动态库实现增量更新
执行环境需要安装依赖、配置环境变量（或者是编译时指定依赖搜索路径）

生成动态链接库

直接使用编译器即可创建动态库

$ g++ -f PIC -c src.cpp -o src.o
	# PIC: position independent code
	# 创建地址无关的二进制目标文件w
$ g++ -shared -nosname libsrc.so -o libsrc.so.1 src.o
	# 生成动态链接库

动态链接库命名规则：lib[libname].so（必须按照此规则命名，因为链接时按照此规则反解析库名称）

dynamic linker/loader

动态载入器：先于executable模块程序工作，并获得控制权

对于linux下elf格式可行程序，即为ld-linux.so*
按照一定顺序搜索需要动态链接库，定位、加载

搜索次序

ld-linux.so*依次搜索以下，定位动态链接库文件、载入内存

elf文件的DT_RPATH段：链接/编译时指定的搜索库文件的路径，存储在elf文件中

g++通过添加-Wl,rpath,、ld通过-rpath参数指定添加的路径
若没有指定rpath，环境变量LD_RUN_PATH中路径将被添加

$ objdump -x elf_exe
	# 查看elf文件的`DT_RPATH`
$ g++ -Wl,-rpath,/path/to/lib
	# 在g++命令中直接给出链接参数
	# 也可以使用链接器`ld`链接时给出
$ g++ -Wl,--enable-new-tags,-rpath,'$ORIGIN/../lib'
	# 使用相对路径
	# Makefile中使用时需要转义`$$ORIGIN/../lib`

LD_LIBRARY_PATH环境变量
- 优先级较高，可能会覆盖默认库，应该避免使用，会影响所有动态链接库的查找
- 不需要root权限，同时也是影响安全性
/etc/ld.so.cache文件列表（其中包括所有动态链接库文件路径）
- /lib、/lib64、/usr/lib、/usr/lib64隐式默认包含，优先级较低、且逐渐降低
- 其由ldconfig根据/etc/ld.so.conf生成，库文件添加进已有库路径、添加路径至/et/ld.so.conf后，需要通过 ldconfig更新缓存才能被找到
- ldconfig具体参见linux/shell/cmd_sysctl

因为LD_LIBRARY_PATH的缺点，建议使用LD_RUN_PATH，在链接时就指定动态库搜索路径

Posted 2019-03-21Updated 2019-03-08C/C++ / STLa few seconds read (About 0 words)

Inequality

Azuma-Hoeffding Inequality

Hoeffding Inequality

Bretagnolle-Huber-Carol Inequility

Bipartite Graph

Augmenting-Path

增益路径-最大匹配证明

Konig Theorem

推论 1

Ordered Bipartite Graph

Marriage Matching

存储、表示方法

Stable Marriage Matching

稳定婚姻存在性

Weighted Bipartite Graph

Distribution Problem

存储方法

Biconnected Graph

求解关节点

点集

点覆盖集

点支配集

点独立集

性质

Thoerem 1

Thoerem 2

Thoerem 3

边集

边覆盖

边独立集

性质

Thoerem 1

Thoerem 2

Thoerem 3

度

Laplacian矩阵

性质

边数量

Multigraph

边权

欧几里得类型加权图

连通性

Transitive closure

Hamiltonian Circuit

Eular Circuit

State-Space Graph

Hook/Callback

优点

实现

C实现

Python实现

Closure

Cache

Least Recently Used Cache

多重继承

多重继承问题

多重继承优点

todo

解决方案

规格继承

方案问题

弥补技巧delegate

实现继承

方案问题

弥补技巧mixin

OSI/RM

物理层

数据链路层

网络层

传输层

会话层

表示层

应用层

硬件

RP repeater

功能

Hub

功能

Bridge

功能

`C`实现