要想了解HyperLogLog ,必须先要了解伯努利实验
- 作用:能够使用极少的内存,大数据量亿级数据去重复统计uv
- 伯努利实验
一次伯努利实验,抛硬币不管进行抛掷次数多少次,只要出现一个正面,就称之为为一次伯努利实验
对于这n
次伯努利试验中,必然会有一个最大的抛掷次数k
k_max
表示在所有次伯努利实验中,它是抛掷次数最高的
最终结合极大似然估算的方法,发现在n和k_max中存在估算关联:n = 2^(k_max)
结论:可以通过伯努利实验中最大抛掷次数来估算总伯努利实验次数 - 比特串
hash(id) = 比特串
不同的用户 id,必然拥有不同的比特串。每一个比特串,也必然会至少出现一次 1 的位置。我们类比每一个比特串为一次伯努利试验
不同的用户 id,必然拥有不同的比特串。每一个比特串,也必然会至少出现一次 1 的位置。我们类比每一个比特串为一次伯努利试验。
现在要分轮,也就是分桶。所以我们可以设定,每个比特串的前多少位转为10进制后,其值就对应于所在桶的标号。假设比特串的低两位用来计算桶下标志,此时有一个用户的id的比特串是:1001011000011
。它的所在桶下标为:11(2) = 1*2^1 + 1*2^0 = 3
,处于第3个桶,即第3轮中。
上面例子中,计算出桶号后,剩下的比特串是:10010110000
,从低位到高位看,第一次出现 1 的位置是 5 。也就是说,此时第3个桶,第3轮的试验中,k_max = 5。5 对应的二进制是:101,又因为每个桶有 p 个比特位。当 p>=3 时,便可以将 101 存进去。
模仿上面的流程,多个不同的用户 id,就被分散到不同的桶中去了,且每个桶有其 k_max。然后当要统计出 mian 页面有多少用户点击量的时候,就是一次估算。最终结合所有桶中的 k_max,代入估算公式,便能得出估算值。
注意:如果入了同一个桶,如何更新桶里的值?取值大的那个 -
分桶
分桶数组是为了消减因偶然性带来的误差,提高预估的准确性
分桶平均的基本原理是将统计数据划分为m个桶,每个桶分别统计各自的k_max,并能得到各自的基数预估值 n ,最终对这些 n 求平均(调和平均数)得到整体的基数估计值。
DV - 就是要求的基数n
const -是修正因子
m - 表示第几轮次实验:进行一轮次实验,只能得到一个k_max,若进行的伯努利试验次数少,估算不准确,
所以采用多轮次实验,得到多个k_max值,然后根据以下公式进行评估得到相对准确的伯努利试验次数,也就是基数
RJ - 表示调和平均数
以下是调和平均数公式,调和平均数可以减轻大数的影响
image.png
- redis 实现源码
// 密集模式添加元素
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
uint8_t oldcount, count;
long index;
// 计算该元素第一个1出现的位置
count = hllPatLen(ele,elesize,&index);
// 得到第index个桶内的count值
HLL_DENSE_GET_REGISTER(oldcount,registers,index);
if (count > oldcount) {
// 如果比现有的最大值还大,则添加该值到数据部分
HLL_DENSE_SET_REGISTER(registers,index,count);
return 1;
} else {
// 如果小于现有的最大值,则不做处理,因为不影响基数
return 0;
}
}
// 用于计算hash后的值中,第一个出现1的位置
int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
uint64_t hash, bit, index;
int count;
// 利用MurmurHash64A哈希函数来计算该元素的hash值
hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
// 计算应该放在哪个桶
index = hash & HLL_P_MASK;
// 为了保证循环能够终止
hash |= ((uint64_t)1<<63);
bit = HLL_REGISTERS;
// 存储第一个1出现的位置
count = 1;
// 计算count
while((hash & bit) == 0) {
count++;
bit <<= 1;
}
*regp = (int) index;
return count;
}
感谢这两位位大神
https://juejin.im/post/5c7900bf518825407c7eafd0
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html
网友评论