Posted 2021-05-13Updated 2021-05-13Algorithm / Specificationa few seconds read (About 90 words)

Random

线性同余法

线性同余法：产生伪随机数最常用方法

$\left \{ \begin{array}{l} a_0 = & d \\ a_n = & (ba_{n-1} + c) % m, & n=1,2,\cdots \end{array} \right.$

$d \leq m$：随机序列种子

$b \geq 0, c \geq 0, m \geq 0$：关系到产生随机序列的随机性能

$m$：应该取得充分大

$gcd(m ,b)=1$：可以取b为素数

Posted 2021-04-06Updated 2021-08-02Algorithm / Specification11 minutes read (About 1672 words)

架构相关算法

无符号整形二进制

`1`数量

目标：统计 unsinged 二进制表示中 1 数量
思路方向
- 移位遍历
- 分治统计

仅遍历`1`

int population(unsigned int bits){
	int result = 0;
	while (bits != 0){
		bits &= bits - 1;
		++result;
	}
	return result;
}

遍历减少：仅仅遍历无符号整形二进制表示中 1 次数
- bits &= bits - 1 将末尾 1 消除

分治+查表

int * initialization(){
	int * table = new int[256];
	for (int i = 1; i < 256; i++){
		table[i] = (i & 0x1) + table[i >> 1];
	}
	return table;
}
int population(int bits, int * table){
	return table[bits & 0xff] +
		table[(bit >> 8) & 0xff] +
		table[(bit >> 16) & 0xff] +
		table[(bit >> 24) & 0xff]
}

思路
- 建表：为 8bits 数建立 256 长度的 1 数量表
  - 递推建立：f(n) = f(n >> 1) + last_bit(n)
- 分治：将无符号整型分4块查表、加和结果

分治

int population(unsigned int bits){
	// 分组计算
	bits = (bits & 0x55555555) + ((bits >> 1) & 0x55555555);
	bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
	bits = (bits & 0x0f0f0f0f) + ((bits >> 4) & 0x0f0f0f0f);
	bits = (bits & 0x00ff00ff) + ((bits >> 8) & 0x00ff00ff);
	bits = (bits & 0x0000ffff) + ((bits >> 16) & 0x0000ffff);
	return bits;
}

unsigned_population__division

分治统计：依次将相邻 2bits、 4bits 分组，计算组内 1数量
- 移位、求并：将组内无效 bits 置 0、并对齐
- +：计算组内 1 数量
  - 0x0 + 0x0 = 0x0
  - 0x0 + 0x1 = 0x1
  - 0x1 + 0x1 = 0x10：进位，符合逻辑
改进方式：考虑避免不必要的 &
- 根据进位特性替换 2bits 组对应语句
- 考虑组内空位是否可容纳 + 后结果
  - 8bits 组：有效半组 4bits 足够存储中的最大 1 数量 8，但无法存储 16 或更大，需要及时置空无效bit
  - 16bits 组及之后：有效半组足够存储最大 1 数量 32，可以计算完之后再取值

int population(unsigned int bits){
	// 等于上述首行
	bits = bits - ((bits >> 1) & 0x55555555);
	bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
	// 4bits 足够存储组内 8bits 中 `1` 最大数量 8
	bits = (bits + (bits >> 4)) & 0x0f0f0f0f;
	// 8bits 足够存储全部 32bits 中 `1` 最大数量 32
	bits = bits + (bits >> 8);
	bits = bits + (bits >> 16);
	return bits & 0x3f
}

奇偶性

目标：判断 unsigned 二进制表示中 1 数量奇偶性
思路方向
- 移位遍历，注意语言特性
  - 逻辑移位和算术移位
  - 求余结果
- 分治统计

分治统计

// 原始版本
unsigned char parity(unsigned int i){
	// 相邻2bit一组异或确定奇偶
	i = i ^ (i >> 1);
	// 相邻4bit一组，依赖以上结果确定奇偶
	i = i ^ (i >> 2);
	i = i ^ (i >> 4);
	i = i ^ (i >> 8);
	i = i ^ (i >> 16);
	// 奇偶性保存在最后1bit，取出
	return i & 0x1;
}

分治统计：依次将相邻 2bits、 4bits 分组，统计组内奇偶性
- 分组方式顺序调换仅影响中间结果中存放奇偶性统计结果 bits 位置
  - 奇偶性统计结果存放在组内最后 bit
  - 其中每次分组统计事实上都是统计 2bits 的奇偶性
改进方式
- 调整分组顺序，将存储奇偶性 bits 位置移至最后
- 计算奇偶性 bits 对应奇偶性表，查表得到结果
  - 一般可以设置长度为 0x0f 长度的数组，其中取值为索引奇偶性
  - 0x6996 即为对应奇偶性表，其中各位序 bit 取值为位序值对应的奇偶性

// 改进版本
unsigned char parity_k(unsigned int i){
	// 将存储奇偶性 bits 移至最后
	i = i ^ (i >> 4);
	i = i ^ (i >> 8);
	i = i ^ (i >> 16);
	// 查表得到结果
	return (0x6996 >> (i & 0x0f )) & 0x01;
}

奇偶性填充

目标：将 unsigned char 中最高位作为校验位，保证整体的二进制标表示的奇偶性
思路方向
- 求1数量并设置标志位
- 按位乘积后取模

取模

unsigned char even(unsigned char i){
	return ((i * 0x10204081) & 0x888888ff) % 1920;
}
unsigned char odd(unsigned char i){
	return ((i * 0x00204081) | 0x3DB6DB00) % 1152;
}

各数字二进制含义（设 i 的二进制表示为 abcdefg）
- 0x10204081 * i 得到 i 二进制重复 5 次（溢出被截断）
- 0x888888ff & 抽取所需 bits d000a000e000b000f000c000gabcdefg
- 1920 = 15 * 128：对其取模即得到[X]abcdefg （将被除数表示为 16 进制分块可证）

位元反序

目标：返回 6bits 长二进制的反序

1
2
3

unsigned char revert(unsigned char i){
	return ((i * 0x00082082) & 0x01122408) % 255;
}

各数字二进制含义（设 i 的二进制表示为 abcdef）
- 0x00082082 * i 得到 i 二进制重复 4 次
- 0x01122408 & 抽取所需 bits 0000000a000e00b000f00c000000d000
- 对 255 取模即得到反序*（将被除数表示为 256 进制分块可证）

前导 `0`

目标：获取 unsigned 的二进制表示中前导 0 数量
思路方向
- 移位遍历
- 区间映射：将原始 unsigned 映射为较小范围的取值

区间映射

unsigned char nlz(unsigned int i){
	static unsigned char table[64] = {
		32, 31, 'u', 16, 'u', 30, 3, 'u', 15, 'u', 'u', 'u', 29,
		10, 2, 'u', 'u', 'u', 12, 14, 21, 'u', 19, 'u', 'u', 28,
		'u', 25, 'u', 9, 1, 'u', 17, 'u', 4, 'u', 'u', 'u', 11,
		'u', 13, 22, 20, 'u', 26, 'u', 'u', 18, 5, 'u', 'u', 23,
		'u', 27, 'u', 6, 'u', 24, 7, 'u', 8, 'u', 0, 'u'
	}

	i = i | (i >> 1);
	i = i | (i >> 2);
	i = i | (i >> 4);
	i = i | (i >> 8);
	i = i | (i >> 16);
	i = i * 0x06eb14f9;
	return table[i >> 26];
}

区间映射
- 移位取或：将最高位 1 传播至所有低位，原始值映射至 33 种取值
- 0x06eb14f9：将 33 种值映射为低 6 位取值均不同值
  - 此类数的共同特点是因子均为 $2^k \pm 1$ （此类数乘法容易通过移位操作实现）
  - 最小的此性质的数为 0x45bced1 = 17 * 65 * 129 * 513

速算

无符号整形除法

目标：大部分计算机架构中除法耗时，寻找方法将特定除数的除法转换为其他指令
思路：除数为常数时，用移位、乘法、加法替代除法运算
- 常数除法（有符号或无符号）基本都有对应的乘法版本
- 注意类型溢出

除数为3

unsigned div3(unsigned int i){
	// 在更高级别优化过程实际就会转化为类似指令
	// 但此语句可能会导致类型溢出
	return (i * 2863311531) >> 33;
}

$\begin{align*} 2863311531 &= \frac {2^{33} + 1} 3 \\ i/3 &= \lfloor i * \frac {2^{33} + 1} 3 * \frac 1 {2^{33}} \rfloor \\ &= \lfloor \frac i 3 + \frac i {3 * 2^{33}} \rfloor = \frac i 3 \end{align*}$

快速求平方根倒数

float i_sqrt(float a){
	union {
		int ii;
		float i;
	};
	i = a;
	float ihalf = 0.5f * i;

	// 得到较好的初始估算值
	ii = 0x5f000000 - (ii >> 1);

	// 牛顿法迭代，可以重复以下语句多次提高精度
	i = i * (1.5f - ihalf * i * i);

	return i;
}

移位获取初始值
- 考虑（规格化）单精度浮点数 $a$ 的二进制表示
  $\begin{align*} a &= 2^{E-127} * (1+F) \\ \frac 1 {\sqrt a} &= 2^{\frac {127 - E} 2 + 127} * (1+F)^{-\frac 1 2} \\ &= 2^{190.5 - \frac E 2} * (1+F)^{-\frac 1 2} \end{align*}$
- 则 0x5f000000 - (ii >> 1) 可以满足指数部分得到近似结果 $190 - \frac E 2$
- 其他细节使得存在比 0x5f000000 实践更优值，如：0x5f375a86
  - 规格化值的底数接近 1
  - 移位运算指数最后位部分移至尾数
  - 减法运算尾数部分向指数借位
牛顿法：$x{n+1} = xn - \frac {f(x_n)} {f^{‘}(x__n)}$
- 求 $\frac 1 {\sqrt x}$，即求 $f(x) = x^{-2} - a$ 零点
- 则迭代为 $x{n+1} = xn(1.5 - 0.5 a x__n^2)$

http://www.lomont.org/papers/2003/InvSqrt.pdf

https://zhuanlan.zhihu.com/p/33543750

Posted 2019-07-21Updated 2019-07-21Algorithm / Specification9 minutes read (About 1299 words)

随机算法

数值随机化算法

数值化随机算法：常用于数值问题求解，往往得到的是近似解

近似解的精度随计算时间、采样数量增加不断提高
很多情况下计算问题的精确解不可能、无必要，数值化随机算法可以得到较好的解

随机投点法

随机投点法：在给定范围内生成均匀分布随机数模拟随机投点

计算$\pi$值：在正方形、内切圆中随机撒点，计算圆内、正方形内点数量之比
计算黎曼积分：在包括积分区域单位矩形内随机投点，计算积分区域、矩形区域点数量之比

平均值法

平均值法：结合随机数分布、目标问题构造统计量，估计目标问题

计算黎曼积分

假设独立同分布随机变量${\eta_i}$在$[a, b]$中服从分布 $f(x)$、待积函数为$g(x)$
记$g^{*}(x) = \frac {g(x)} {f(x)}$，则有
$\begin{align*} E(g^{*}(\eta)) & = \int_a^b g^{*}f(x) dx \\ & = \int_a^b g(x) dx = I \end{align*}$
由强大数定理
$P_r(\lim_{x \rightarrow \infty} \frac 1 n \sum_{i=1}^n g^{*}(\eta_i) = I) = 1$
选择$\bar I = \frac 1 n \sum_{i=1}^n g^{*}(\eta_i)$，则$\bar I$依概率收敛为$I$
选择抽样方法简单的概率密度函数$f(x)$满足
$\left \{ \begin{array}{l} f(x) \neq 0, & g(x) \neq 0, a \leq x \leq b \\ \int_a^b f(x) dx = 1 \end{array} \right.$
可以取$f(x)$为均匀分布
$f(x) = \left \{ \begin{array}{l} \frac 1 {b-a}, & a \leq x \leq b \\ 0, & x < a, x > b \end{array} \right.$
则积分
$I = \int_a^b g(x)dx = (b-a) \int_a^b g(x) \frac 1 {b-a}dx$
取均值
$\bar I = \frac {b-a} n \sum_{i=1}^n g(x_i)$
可作为求分I的近似值

解非线性方程组

$\left \{ \begin{array}{l} f_1(x) & = f_1(x_1, x_2, \cdots, x_n) & = 0 \\ f_2(x) & = f_2(x_1, x_2, \cdots, x_n) & = 0 \\ \vdots \\ f_n(x) & = f_n(x_1, x_2, \cdots, x_n) & = 0 \end{array} \right.$

线性化方法、求函数极小值方法有时会遇到麻烦，甚至使方法失效而不能获得近似解
随机化方法相较而言要耗费较多时间，但设计简单、易于实现
对于精度要求较高的问题，随机化方法可以提供一个较好的初值

步骤

构造目标函数
$\Phi(x) = \sum f_i^2(x)$
则目标函数的极小值点即为所求非线性方程组的一组解
随机选择点$x_0$作为出发点，不断随机生成搜索方向，迭代为使得目标函数值下降的搜索点
- 一般以目标函数变化幅度、迭代轮数作为终止条件
- 搜索方向为随机生成，迭代步长比例每轮缩小指定幅度

真正的随机次梯度下降

Monte Carol Method

蒙特卡洛算法：一定能给出问题解，但未必正确

要求在有限时间、采样内必须给出解，解未必正确
求得正确解的概率依赖于算法所用时间，算法所用时间越多，得到正确解概率越高
无法有效判断得到的解是否肯定正确

Las Vegas Method

拉斯维加斯算法：找到的解一定是正确解，但是可能找不到解

找到正确解的概率随着计算所用时间增加而提高
用同一拉斯维加斯算法反复对实例求解多次，可使得求解失效概率任意小

Sherwood Method

舍伍德算法：能求得问题的一个解，所求得得解总是正确的

确定性算法在最好情况、平均情况下计算复杂度有较大差别，在确定性算法中引入随机性将其改造成舍伍德算法，消除、减少问题的好坏实例间差别
精髓不是改进算法在最坏情形下的行为，而是设法消除最坏情形与特定问题实例的关联性

思想

问题输入规模为n时，算法A所需的平均时间为
- $X_n$：算法A输入规模为n的实例全体
- $t_A(x)$：输入实例为x时所需的计算时间
显然存在$x \in X_n, t_A(x) >> \bar t_A(x)$
希望获得随机化算法B，使得对问题的输入规模为n的每个实例 $x \in X_n$均有$t_B(x) = \bar t_A(x) + s(n)$
- 对具体实例，存在$x \in X_n$，算法B需要时间超过 $\bar t_A(x) + s(n)$，但这是由于算法所做的概率引起，与具体实例无关
- 算法B关于规模为n的随机实例平均时间为
  
  $\begin{align*} \bar t_B(n) & = \sum_{x \in X_n} t_B(x) / (X_n) \\ & = \bar t_A(n) + s(n) \end{align*}$ K
  
  当$s(n)$与$\bar t_A(n)$相比可以忽略时，舍伍德算法可以获得较好平均性能

todo

Posted 2019-06-04Updated 2019-06-04Algorithm / Specification5 minutes read (About 768 words)

高维数据检索方法

相似性检索

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

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：视觉单词，每个代表一个聚类类别

Posted 2019-05-25Updated 2021-08-02Algorithm / Specificationa minute read (About 164 words)

Infomation Security

Hash/摘要方法

文件校验

MD4

附加填充bits：在末尾对消息填充，使得消息$M$长度满足 $len(M) mod 512 = 448$
- 填充最高位位为1、其余为0
分块：将填充后消息512bits分块为$M_1,M_2,\cdots,M_K$
初始化MD4缓存值
- MD4使用128bits缓存存储哈希函数中间、最终摘要
- 将其视为4个32bits寄存器初始化为
  - A = 0x67452301
  - B = 0xefcbab89
  - C = 0x98badcfe
  - D = 0x10325476
使用压缩函数迭代计算K个消息分块、上次计算结果
- $H_{i+1} = C(H_i, M_i)$
- 最终$H_K$即为MD4摘要值