大数据计数原理1+0=1这你都不会算(十)No.77

大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet

大数据计数原理1+0=1这你都不会算(二)No.50 <- BitMap

大数据计数原理1+0=1这你都不会算(三)No.51 <- BloomFilter

大数据计数原理1+0=1这你都不会算(四)No.52 <- B-Tree

大数据计数原理1+0=1这你都不会算(五)No.55 <- B+Tree

大数据计数原理1+0=1这你都不会算(六)No.57 <- LinearCounting（一）

大数据计数原理1+0=1这你都不会算(七)No.59 <- LinearCounting（二）

大数据计数原理1+0=1这你都不会算(八)No.60 <- RoaringBitMaps

大数据计数原理1+0=1这你都不会算(九)No.64

完结篇。 这个系列写到这里算是结束了，真是不容易说实话，查了好多好多的资料，真的很难相信懒得要命的我能写完这个系列 T_T。有兴趣的小伙伴可以在菜单看看整个系列。

好啦，开始今天的主题，今天主要呢，聊最后两个基数估计算法，一个是 Adaptive Counting ，一个是 HyperLogLog Counting 。话不多说，直接简单粗暴从 Adaptive Counting 开始吧。

Adaptive Counting 其实就是一个组合算法。

原始论文是 《 Fast and accurate traffic matrix measurement using adaptive cardinality counting 》 。思路很简单粗暴，就是将 LC 和 LLC 组合起来使用，我们假设 LC 与 LLC 在同样的条件下，在总统计值 m 等于 M 的时候误差达到一致，那么当 m 小于 M 的时候使用 LC ，当 m 远大于 M 的时候使用 LLC。 为什么呢？我们都知道 LC 其实只是 BitMap 的进化版，如果基数太大的话，那么会占用非常多非常多的内存，如果桶设置得太小的话所有的桶基本都满了，那么这样子误差会很大。而 LLC 则非常稀疏，如果 m 太小的话，那么会出现非常多的空桶，这样子误差也非常大。所以总结起来就是，组合起来用，总统计量小的话用 LC ， 统计量太大的话用 LLC 。

HyperLogLog Counting 其实就是 LC 基数估计法从算术平均数换成调和平均数。

先补充一下小学算术，什么叫算术平均数什么叫调和平均数哈。首先是算术平均数，其实就是加起来求和。

第二是调和平均数，其实就是倒数求和除n的倒数。

呐，这样就可以解释清楚了。LC 里边是对 m 个桶里边的值进行求算术平均数然后直接进行基数估计，而 LLC 则是使用调和平均数。那么，这样做有什么道理呢？

对比一下，LLC 是第一个，HyperLogLog Counting 是第二个。

看得出差别了吗？一个是直接求和平均，一个是倒数平均。其中 LLC 使用算术平均数，那么如果数值比较稀疏的时候，也即是有一些偏离值的时候，整个数据的求和会变得很偏远。用人话来说就是，我跟姚明平均身高两米。。。非常容易受到异常值的影响。而 HyperLogLog Counting 使用调和平均数则可以有效降低偏离值的影响。虽然来说也有一点影响但是影响程度没有算术平均数那么大。

最后放出各大算法的空间占用及误差率，看时机使用吧，别什么东西都直接丢一个 HyperLogLog ，有些场景下可能直接丢一个 HashSet 更靠谱喔。

好了这个系列到此结束，总得来说基数估计算法的套路都差不了太多，基本都输基于 BitMap 的思想，然后进行分桶，接着对桶进行统计这样的思路来进行超大数据量的基数估计。