img

不一样它要去重同一个用户一天之内的多次访问请求只能计数一次。

这就要求每一个网页请求都需要带上用户的

set

集合来统计这就非常浪费空间。

如果这样的页面很多那所需要的存储空间是惊人的。

为这样一个去重功能就耗费这样多的存储空间值得么其实老板需要的数据又不需要太精确105w

106w

这两个数字对于老板们来说并没有多大区别So有没有更好的解决方案呢

HyperLogLog

提供不精确的去重计数方案虽然不精确但是也不是非常不精确标准误差是

HyperLogLog

的高级数据结构它非常有用但是令人感到意外的是使用过它的人非常少。

使用方法

pfcount根据字面意义很好理解一个是增加计数一个是获取计数。

pfadd

用法和

简单试了一下发现还蛮精确的一个没多也一个没少。

接下来我们使用脚本往里面灌更多的数据看看它是否还可以继续精确下去如果不能精确差距有多大。

人生苦短我用

PythonPython

统计需求来说误差率也不算高。

然后我们把上面的脚本再跑一边也就相当于将数据重复加入一边查看输出可以发现pfcount

pfadd

比如在网站中我们有两个内容差不多的页面运营说需要这两个页面的数据进行合并。

其中页面的

访问量也需要合并那这个时候

这个数据结构不是免费的不是说使用这个数据结构要花钱它需要占据一定

12k

的存储空间所以它不适合统计单个用户相关的数据。

如果你的用户上亿可以算算这个空间成本是非常惊人的。

但是相比

set

的存储进行了优化在计数比较小时它的存储空间采用稀疏矩阵存储空间占用很小仅仅在计数慢慢变大稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵才会占用

12k

的使用非常简单但是实现原理比较复杂如果读者没有特别的兴趣下面的内容暂时可以跳过不看。

HyperLogLog

这张图的意思是给定一系列的随机整数我们记录下低位连续零位的最大长度

py复制代码import

ThreadLocalRandom.current().nextLong(2L

32);

BitKeeper然后进行加权估计就可以得到一个比较准确的值。

py复制代码import

ThreadLocalRandom.current().nextLong(1L

32);

(倒数的平均)。

普通的平均法可能因为个别离群值对平均结果产生较大的影响调和平均可以有效平滑离群值的影响。

img

要比上面的示例代码更加复杂一些也更加精确一些。

上面的这个算法在随机次数很少的情况下会出现除零错误因为

maxbits0