HyperLogLog
这是一个基于LogLog改进而来的算法，用于估算给定的数据中有多少个唯一值：
def LogLog(input: list) -> int:
return len(set(input))
-
每个数据通过一个散列函数转化为64bit
-
64bit拆成14bit msb和50bit lsb
-
14bit msb用于决定计算LogLog在哪一轮，2^14为16384，要执行16384轮
-
50bit lsb用于统计第一个1出现在第N位，可能出现在0位到50位
-
计算每一轮的最大的N，N可能为0到50，用6bit记录即可
-
求出所有轮的N的调和平均值，用于伯努利估计
-
HyperLogLog在此基础上加入校正
-
占用空间16384轮*6位/8/1024=12KB