我们经常会在sql中使用select count(distinct xx) from xxx 来计算一列中到底有多少个值。但是sql往往计算的很慢当数据量很大的时候，这个时候就需要HyperLogLog算法，虽然它计算会有误差，但在可接受的范围内。接下来就看看HyperLogLog的牛逼路数。
首选得说说linear counting.这个跟跟布隆过滤器的图很像
其哈希结果有m个值且服从均匀分布（允许冲突），初始化长度为m的bitmap，将n个元素通过哈希算法后在bitmap对应位上设置为1，此时bitmap上0的个数为u，可以通过0的个数估算出元素的个数：n = m * log( m / u )
也就是通过计算log(m/u)的比例来估算到底有多少个值
接下来得说说LogLog counting.
这个是怎么算的呢？大概就跟之前算概率的方式差不多。
我通过抛硬币的方式然后来估算。
算法思路：以抛硬币（正反面概率相同）为例，连续抛硬币直到出现正面时停止，记录下抛掷次数（这个过程称之为伯努利过程），n次伯努利过程会得到n个首次出现正面的抛掷次数，其中最大抛掷次数为k，可以通过最大抛掷次数估算出总抛掷过程数：n = 2^k
LogLog Counting为了避免偶然性，会先进行分桶，每次抛硬币先随机分配到其中一个桶，每个桶保存最大抛掷次数，最后通过所有桶最大抛掷次数的均值计算，但是在抛掷次数小时误差还是会比较大
接下来是真正的主角出场了。HyperLogLog Counting
算法思路：同样也是Linear Counting与LogLog Counting的结合，但是会比Adaptive Counting复杂一些，它采用调和平均数来计算所有桶的均值，这样可以有效抵抗离群值的影响，同时还根据基数量级提供了一个分段的偏差修正方案。adaptive是这样的当空桶的概率达到0.051的时候那么你用linear 否则用llc
HyperLogLog 只是把这个0.051做了修正，我用个高级点的公式给你调整。
什么公式呢？
m = 2^b #m为桶数，如redis的实现（b=14 m=16384）
switch (m) { #alpha为偏差修正参数
case 16: {
alpha = 0.673
break;
}
case 32: {
alpha = 0.697
break;
}
case 64: {
alpha = 0.709
break;
}
default: {
alpha = 0.7213 / ( 1 + 1.079 / m )
}
}
registers = [0] * m #将每桶的值初始化为0
#添加元素过程
for h in hashed(data): #元素哈希值（哈希服从均匀分布）
register_index = 1 + get_register_index( h,b ) #将哈希值二进制最右边b位转为十进制作为桶索引
run_length = run_of_zeros( h,b ) #从哈希值二进制右边第b+1位开始从右往左首次出现1经过的位数（形同抛硬币，0为反面，1为正面）
registers[ register_index ] = max( registers[ register_index ], run_length ) #桶中只保存最大值
#基数估算过程
DV_est = alpha * m^2 * 1 / sum( 2^-register ) #HyperLogLog估算值（调和平均数）
if DV_est <= ( 5 / 2 ) * m: #小范围修正
V = count_of_zero_registers( registers ) #计算空桶数量
if V == 0: #空桶数量为0，Linear Counting失效，采用HyperLogLog估算值
DV = DV_est
else:
DV = m * log( m / V ) #采用Linear Counting算法
if DV_est <= ( 1 / 30 * 2^32 ): #不用修正
DV = DV_est
if DV_est > ( 1 / 30 * 2^32 ): #大范围修正
DV = -2^32 * log( 1 - DV_est / 2^32)
这个是redis的实现的类似代码。
添加的过程如下：
添加过程
1 假设我们需要64个桶那么的就用2^6方 6位数表示就行了。
2 输入元素值为12125880，其哈希值为1927385862
3 将哈希值转换成二进制：1110010111000011001001100000110
4 计算桶索引：取二进制最右边6位000110转换为10进制等于6（和数据库中分库分表的取余法类似，平均分配到桶中）
5 计算桶数值：从二进制最右边第7位开始，从右往左首次出现1经过的位数，数值等于3
将第6桶的值设置为3（若第6桶原有值大于3则不设置），完成元素添加.
本文由 妖言君 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 21, 2022 at 05:03 pm