See You Again

HyperLogLog算法初探

业务有一次用了 redis 的 HyperLogLog 接口计算个数,后来发现踩坑了,这个接口的结果是一个估算值!看了下,这个算法还是很牛逼的,只用12K的存储空间就可以估算几亿量级的数据,很适合大数据领域。最常用的场景应该就是“统计一段时间的UV”。
假设有1亿个不重复的 IP,每个IP用一个 bit 表示,那么准确存储的话,大概需要 10**8/8/1000/1000 = 12M 的空间,而使用上面的估算模型,只需要千分之一的空间!(误差大概有 3%)

基本原理大概有两个核心点:

以 redis 估算一亿个 IP 为例:

通过概率模型进行局部估算,以及分桶平均可以取得较好的效果。实际需要的存储空间为:
6*16384/8/1000=12K

具体算法细节就不探讨了,比较深奥~~
这里有一个动画模型可以参考

2017-11-01 喜欢

Copyright © 2015-2018 转载请注明出处

回到顶部 ↑