基数估算算法LogLog

一个数据集中不同数据的数量叫做基数(cradinality)，现实中有很多计算基数的需求，如统计网站的UV，统计商城中某一件物品的独立ip点击量。

使用bitmap可以精确地计算基数，并且利用位运算，可以方便地统计以小时、天、周为单位的数据集。但当数据量的范围十分庞大的时候，即使bitmap用一个bit标识一条数据，让要消耗比较多的内存（1亿条数据约需12M内存）。

LogLog是一种估算基数的方法，其以基数统计精度为牺牲，换来很少的内存消耗（1亿条数据仅需1K内存）。LogLog得名于其基数统计内存消耗约为log2log2(N)，算法描述如下：

• 对数据集中的数据进行哈希
• 取哈希后的哈希值后K bit作为桶编号
• 计算除用作桶编号的后K bit，哈希值还有多少个0尾缀
• 最后该数据集中基数约为 2**X*num_buckets*0.79402（其中X=最大0尾缀数/num_buckets）

以上魔数0.79402是一个估算经验值，LogLog简单的算法实现如下：

参考：Damn Cool Algorithms: Cardinality Estimation

          LogLog counting of large cardinalities

Have fun!