rsd计算公式(rsd%怎么计算)

大家好，我是讯享网，很高兴认识大家。

关注微信官方账号:xy的技术圈

计数基数

在应用系统的开发中，我们经常会有这样的需求:统计一个网站的UV，用户搜索的关键词数量等等。我们可以使用基数计数来实现这个功能。基数计数通常用于计算一个集合中非重复元素的数量。

在应用数据分析、网络监控、数据库优化等方面都需要基数。

要计算基数，最简单的方法是使用一个集合，将出现的元素相加，然后计算集合的大小。但是如果数据量很大，使用set会浪费很多空时间。

上一篇文章介绍了位图，位图也可以用来计算基数。但是如果数据量很大，使用位图也会有这个问题。如果要统计1亿个数据的基值，需要12M左右的内存。如果用32位的int类型来表示每个数据，32 * 12大约是381M。

可见位图的使用仍然不适合数据量较大的基数计数场景。

概率算法

连位图都不适合，那么有没有更好的方法来统计大数据的基数呢？

当然，数学是神奇的。利用概率论的一些数学原理，我们可以在一定的误差条件下有效地估计基数的近似值。

具体算法是什么？

Log Counting (LLC)就是为了解决这个问题而发明的，并且空之间的复杂度只有log(log(N))。但LLC的误差较大，超对数计数(HLL)是在LLC的基础上改进的，在空相同的复杂度下，基数估计的误差比LLC小。

HLL有多强大？redis中实现的HyperLogLog只需要12K内存，在标准误差0.81%的前提下可以统计2 ^ 64个数据。

但是，由于HyperLogLog只根据输入元素计算基数，并不存储输入元素本身，因此HyperLogLog不能像集合一样返回输入元素。

HLL原则

请谨慎食用以下内容。

超对数算法来自论文“超对数近似最优基数估计算法的分析”

比如，假设你抛一枚硬币很多次，如果正面抛，继续抛；如果是抛到后面，记录在此之前已经抛到前面K多少次，然后开始下一轮。

如果你告诉我，最多是连续两次投正面，然后再投反面。那我觉得你可能没投多少回合。它可能在三或四个回合中发生。

但是如果你告诉我，你最多是连续投10次头，然后再投一次尾，那么我觉得你可能会投更多轮，因为连续投10次头的概率很小。根据这些已知信息，你需要估计掷硬币的次数？这是HLL的原则。

HLL背后是一个著名的数学概率论原理:伯努利分布。这和上面扔硬币的例子是一样的。头和尾都出现的概率是1/2。继续抛硬币，直到出现人头，并记录投掷次数k，这个多次抛硬币直到出现人头的过程被记录为伯努利过程。对于n个伯努利过程，我们将得到n个投掷时间k1，k2，k3…出现人头的KN，最大值记为k_max，可以是n次实验中最大的。

n = 2 ^ k_max

具体推导过程有点麻烦，有兴趣的朋友可以下来自己研究一下。

回到基数统计的问题，我们需要统计一组数据中不重复元素的个数。哈希函数后，集合中的每个元素都可以表示为由0和1组成的二进制字符串。一个二进制字符串可以比作一个抛硬币实验，1抛到前面，0抛到后面。

从低位开始的二进制串中第一个1的位置，可以理解为抛硬币实验中第一个正抛数K。那么基于以上结论，我们可以通过多次抛硬币实验的最大抛硬币次数来估算实验总数。同样，我们可以通过前1位的最大值k_max来估计不同数的总数(整体基数)。

然后根据上面的公式，就可以计算出基数N。

但是这个误差还是有点大，只能是2的指数，显然不合理。

既然误差大，那就尽量减小。LLC的做法是把所有的数字分成不同的桶，得到每个桶的估计值n1，n2，n3……然后计算它们的几何平均值。

但是这个误差还是有点大，尤其是数据量比较小的时候，某个N可能比较大，会大大增加整体的评论数。比如我的工资是1000元，老板的工资是10000元，那么我们工资的几何平均数就是(1000+10000)/2 = 50500元。好像又被“平均”了。我觉得不太公平，不能展现我们公司真实的薪资情况。所以我们用调和平均的方法来计算:

2 / (1/1000 + 1/10,000) = 1980.2

嗯，这个看起来比较接近真实水平。“调和平均”的结果会倾向于集合中较小的数。HLL使用基于LLC的调和平均值。

HLL实施Redis

Redis在2.8.9版本中增加了HyperLogLog结构。

Redis首先对元素进行哈希运算，生成64位数字。14位用于划分桶，剩余的50位用于计算n的值..每个桶占用的元素相对平均。

在它的实现中，有16384个桶，即:2 ^ 14 = 16384，每个桶有6位，桶中存储这个桶的k_max的值，每个桶中能表示的最大数是63，二进制数是:111 ^ 111。所有桶占用的总内存=16834 * 6/8/1024 = 12K。

组0，组1…第16833组[000000][000000][000000][000000]…[000 000]

为什么是14位和16384桶？这是根据相对标准偏差(RSD)公式计算的。RSD值与桶数m之间存在以下计算关系:

因为我们可以使用每个元素的哈希值的二进制表示的前几位来指示数据属于哪个桶，所以桶的数量必须是2的指数。前面提到Redis的标准误差是0.81%，所以得到的m是2 ^ 14。

Redis在元素少的时候用稀疏矩阵，所以不用12k。

Java的HLL实现

Stream-lib是一个开源的Java流计算库，里面有很多大数据估值算法的实现，包括HyperLogLog算法。HyperLogLog实现类的代码地址如下，有兴趣的朋友可以研究一下:github.com/addthis/str…

HLL Redis的使用

Redis中有三个主要的HLL命令:PFADD、PFCOUNT和PFMERGE。分别添加、计数和合并两个键。

PF是什么意思？

它是数据结构HyperLogLog的发明者Philippe Flajolet的首字母缩写。

认真写文章，用心分享。

个人网站:yasinshaw.com

微信官方账号:xy的技术圈