HyperLogLog¶

伯努利试验¶

假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验

试验次数/n	抛掷次数/k_max
1	3
2	2
3	6
n	12

估算n等于多少： $n=2 ^ {k\_max}$ $ n= 2 ^{12}$

$3 \neq 2^6$ 当试验次数很小的时候，这种估算方法的误差是很大

估算的优化(LogLong) $DV_{LL} = constant * m * 2^\overline{R}$¶

$DV_{LL}$ 代表n
constant 修正因子
m 试验次数
R 平均数 $\frac{k\_max\_1+ \cdots + k\_max\_m}{m}$
调和平均数 $H_n=\frac{1}{\frac{1}{n}\sum_{i=1}^{n}\frac{1}{x_i}} = \frac{n}{\sum_{i=1}^{n}\frac{1}{x_i}}$

$H_n=\frac{m}{\frac{1}{k\_max\_1}+\cdots+\frac{1}{k\_max\_m}}$

HyperLogLog步骤¶
比特串
通过hash函数将数据转换为64为比特串

0:代表反面 1:代表正面

1th  0111010110001000    3
2th  0101000010000000    7
3th  0001010010100000    5
4th  1001010000000000    9
nth  1001010000000000    k
      k16=========> n=?

分桶
分组 [第0组] [第1组] ....[第16833组] [000 000] [000 000] .... [000 000] 占用内存为16834*6/8/1024 =12K
选后14位来表达桶的编号$\(2^{14}=16384$\) 剩下50位出现1的位置50 转换为2进制他是110010 每个桶是6bit
对应

分桶: 每个比特串前多少位转换为10进制后其值就是桶的编号

存储: 剩下的比特串从低位往高位看第一次出现1的位置就是k_max

更新: 14位置是一样时,更新为大的k_max

HyperLogLog¶

伯努利试验¶

估算的优化(LogLong) \(DV_{LL} = constant * m * 2^\overline{R}\)¶

HyperLogLog步骤¶