4 探究Presto SQL引擎-统计计数( 二 ) _生活百科

2.2 Linear Count算法Linear Count简称LC算法，LC算法的流程非常简单(背后的数学思想不简单) 。
算法描述如下：

初始化：给定m个房间，房间存储数字，初始化为0 。
迭代执行：对于要进行基数统计的集合，用一个哈希函数处理集合中的每一个元素。通过哈希函数处理后，元素就可以放置到一个房间中。
收尾：统计m个房间中空房间的数量U 。
结论：集合中不重复元素的个数估计值可以通过如下公式计算：n=-m*log(U/m) 。

这样就把一个统计问题转换成了一个数学问题。公式非常简洁，看到这里大脑中一定会出现许多的问题：

这个公式是怎么得到的？

这里涉及到概率论与数理统计知识，简单来说就是分布、期望、方差、最大似然估计。数学相关的知识比较初级，陈希孺的《概率论与数理统计》基本能覆盖这个公式的数学原理。

这个算法的精确度怎么样？

这个问题从数学的角度，就是问方差(标准差) 。这里没法给一个具体的值，跟满桶率控制，m的选择有关。
这个算法相比精确计数很省空间吗？
这个毋庸置疑，不然直接精确统计就可以了。

m和最终结果n需要满足什么关系？

（毕竟当没有空房间时，这个公式就有问题了。）这里直接给结论吧，随着m和n的增大， m大约为n的十分之一。
2.3 HyperLogLog算法HyperLogLog简称HLL算法，它有如下的特点：

可以实现由极小的内存开销统计出巨量的数据。在 Redis中实现的HyperLogLog，只需要12K内存就能统计2^64个数据。
可以方便实现分布式扩展。(这个点对算法在业务系统中落地非常关键)

理解HLL算法，需要如下几个知识点的铺垫：伯努利实验、调和平均数。
伯努利实验有很多的呈现方式，本文例举其中的一种：取一枚硬币，不断抛掷，直到硬币落地结果为正面朝上。这样的执行过程称为一轮实验。从描述可以看出一轮实验完成抛掷硬币的次数是随机的。
一轮实验对应的Java代码实现如下：
private Random random = new Random(); /*** 0代表正面* 1代表反面* 抛掷直到出现正面* @return 抛掷的次数*/ public int tossCoin(){int r,cnt=0;do{r=random.nextInt(2);cnt++;}while (r<1);return cnt; }可以看出，每执行一轮实验就会得到一个数字，代表这轮实验抛掷硬币的次数。例如：
执行了10轮，可能的结果如下：
3,1,4,1,1,2,3,4,1,1执行了100轮，可能的结果如下：
1,1,2,1,1,2,1,4,2,1,3,1,1,1,1,3,1,2,1,1,2,4,2,3,2,1,1,1,3,1,2,2,6,1,2,4,1,2,2,1,1,3,1,1,1,1,1,1,1,1,1,4,2,1,1,1,1,1,3,1,2,4,4,4,1,3,2,1,5,1,1,1,1,1,1,1,5,1,1,7,1,1,4,1,3,2,1,1,5,2,1,1,5,2,1,1,4,1,1,1执行了1000轮，可能的结果如下：
1,2,1,2,1,3,3,3,1,1,2,2,1,2,1,1,1,1,1,2,1,7,1,1,1,2,2,1,1,3,5,2,3,2,3,1,1,3,1,...,4,1,1,1,2,2,1,3,1,1,1,2,1,1,1,2,1,4,2,2,1,2,2,2,1,1,1,2,2,2,1,1,1,2,2,1,1,3,2,6,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,2,1这时候问题就来了，我们这样按上面的规则不停的抛硬币只是为了应付无聊的时间吗？当然不是！我们关注的重点是：

文章插图
当然，这个最大值是随机变动的，它不是一个固定的值。但是隐约中有个规律：执行的轮次越多，轮次对应的最大值也越大。数学上可以给一个很粗略的公式来拟合这种关系：n=2^p 。
换言之，我们可以通过p来估计n 。到这里就出现了问题解决思路的转换：

将基数统计问题转换成概率论里面参数估计的问题。

思维转换到了数学领域，就可以用数学的工具来解决问题。通常用概率论的思维解决问题，会面临如下几个拦路虎。
问题一：最大值不稳定，容易受到极值影响。
在概率上，对于极值我们的处理策略是多实验几轮，通过平均值来消除极值的影响。这个就引出了第二基础知识点：调和平均数。
数学上其实有许多的平均数计算方式：算术平均数、几何平均数、平方平均数。这里选用调和平均数主要是消除极值的影响。通常有个笑话说，我的收入是1万，老板的收入是1亿，我们平均收入是5000万，我被平均了。如果用调和平均数，得到的结果就是1999.98 。
关于调和平均数的公式，非常容易理解：