python模块---Bounter，用少量内存为海量数据做基数统计

1. 什么是基数统计

援引文章HyperLogLog中的解释：

基数计数(cardinality counting) 通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。要实现基数计数，最简单的做法是记录集合中所有不重复的元素集合S_u，当新来一个元素X_i
，若S_u 中不包含元素X_i，则将X_i 加入S_u，否则不加入，计数值就是S_u的元素数量。

这种做法存在两个问题：

当统计的数据量变大时，相应的存储内存也会线性增长
当集合S_u变大，判断其是否包含新加入元素X_i的成本变大

我们平时做基数统计时，首选集合set，集合对于千万级设置亿级别的数据获取尚有良好的表现，但对于超大数据集，几十亿，几百亿的数据，也是无能为力的。

在大数据场景下，还没有特别好的准确计算基数的高效算法，人们退而求其次，选择牺牲一部分准确性，从而获得内存和性能上的突破，这便是概率算法。

概率算法，虽然不能做精确的基数统计，但贵在内存消耗少，只需要很少量的内存，就可以对海量数据做基数统计。

2. Bounter

Bounter是一个用C语言编写的Python库，用于仅使用很小的固定内存占用空间，即可快速地对大量数据集中的项目频率进行概率统计。

其内部实现了HyperLogLog算法和Count-min Sketch算法，这些算法都太难了，感兴趣的朋友自行研究吧。

安装该模块

from bounter import bounter

counts = bounter(need_iteration=False, size_mb=200)
counts.update(['a', 'b', 'c', 'a', 'b'])

print(counts.cardinality())  #  去重统计  3 
print(counts.total())        #  不去重统计  5 
print(counts['b'])          # b出现的次数  2

从结果上看，是准确的，但这只是因为数据量很少，在处理海量数据时，会用0.81%的标准误差，如果应用场景可以接受误差，Bounter是一个非常好的选择。

在github主页上，开发团队对比了内置的counter和Bounter的表现，Bounter的内存只有counter内存的31分之1的情况下，却得到了100%的准确率和99.27%召回率。

3. redis支持HyperLogLog

redis 支持HyperLogLog结构，可以使用PFADD、PFCOUNT、PFMERGE 这3个命令进行运算。

3.1 PFADD

127.0.0.1:6379> pfadd ip_05_11 192.168.0.1
(integer) 1
127.0.0.1:6379> pfadd ip_05_11 192.168.0.2
(integer) 1
127.0.0.1:6379> pfadd ip_05_11 192.168.0.2
(integer) 0
127.0.0.1:6379> pfadd ip_05_11 192.168.0.3
(integer) 1

使用pfadd命令向集合中添加元素时，如果元素已经存在，则返回0，不存在返回1

3.2 PFCOUNT

PFCOUNT 命令用于输出集合内元素的数量

127.0.0.1:6379> PFCOUNT ip_05_11
(integer) 3

3.3 PFMERGE

127.0.0.1:6379> pfadd ip_05_10 192.168.0.8
(integer) 1
127.0.0.1:6379> pfadd ip_05_10 192.168.0.9
(integer) 1
127.0.0.1:6379> pfadd ip_05_10 192.168.0.1
127.0.0.1:6379> pfmerge ip_05 ip_05_10 ip_05_11

pfmerge 命令将ip_05_10和ip_05_11合并，合并后的key是ip_05

在计算日活，月活这种并不需要精确计算的场景下，使用redis提供的HyperLogLog结构，将非常简单高效。