做a免费网站,新河网新河吧,如何编写一个软件,重庆景点排行榜Redis HyperLogLog是用来做基数统计的算法#xff0c;HyperLogLog在优点是#xff0c;在输入的元素的数量或者体积非常大时#xff0c;计算基数占用的空间总是固定的、并且非常小。在Redis里每个HyperLogLog键只需花费12KB内存#xff0c;就可以计算接近 264 个元素的基数。…Redis HyperLogLog是用来做基数统计的算法HyperLogLog在优点是在输入的元素的数量或者体积非常大时计算基数占用的空间总是固定的、并且非常小。在Redis里每个HyperLogLog键只需花费12KB内存就可以计算接近 264 个元素的基数。因为HyperLogLog只是计算输入元素的基数而不会储存元素的本身因此HyperLogLog不会返回输入的元素。
1、什么是基数
比如数据集{1,3,5,7,9,3,5,7}那么这个数据集的基数集为{1,3,5,7,9}基数为5(不重复的元素)。基数估计就是在误差可接受的范围内快速计算基数。
2、常用命令
pfadd key element[element…]将数据添加到HyperLogLog数据结构中。pfcount key [key…]返回给定HyperLogLog的基数估计值。pfmerge destKey sourceKey[sourceKey]将多个HyperLogLog合并为一个HyperLogLog。
3、HyperLogLog特点
1、占用内存小12KB的内存大小可以统计将近264 个元素。 2、计数存在一定的误差但整体误差率较低。标准误差为0.81%。
*在Java中我们知道long类型占用8字节1byte8位即long类型能表示的最大数值为263 -1。对应上面的 264个数。假设现在有264个数。那么按照long以及1KB1024字节。那么264个数占用的内存为(264 8)/1024。其占用的内存远远高于12KB。
4、HyperLogLog原理
4.1、伯努利实验
在了解为什么HyperLogLog能在占用内存那么小的情况下来统计那么大的数据。需要先了解下伯努利实验。 伯努利试验是数学中概率论的一部分内容。它的典故来源于抛硬币。 硬币只有正反两面(正好对应计算机中的0和1)最终出现正反面的概率都是50%。假设我们一直抛硬币只要出现一次正面就记为一次完整实验。中间可能一次就出现正面也可能10次才出现正面。不论抛了多少次只要出现一次正面就记为一次完整的实验。这个实验就是伯努利实验。 那么对于n次伯努利实验。意味着出现了**n**次正面。每一次的结果都有可能不同。假设第一次伯努利实验抛掷次数为**k1**以此类推第**n**此为**kn**。 其中在n次实验中必然会存在一次是抛掷次数最大的。假设有一次伯努利实验抛掷了12次才出现正面是最多的一次我们将这个数记为**k_max**。 在伯努利实验中很容易得出以下结论 1、n次伯努利实验中的抛掷次数都不大于k_max。 2、n次伯努利实验过程中最少有一次抛掷次数等于k_max。
其中n和k_max有一个估算关联关系**n2^k_max**(我也不知道怎么推导的)。
假如有一轮伯努利实验的例子如下 **第一次试验: 抛了3次才出现正面此时 k3n1 ** **第二次试验: 抛了2次才出现正面此时 k2n2 ** **第三次试验: 抛了6次才出现正面此时 k6n3 ** 第n 次试验抛了12次才出现正面此时我们估算 n 2^12 假设在上面的例子中我们总共实验了3组那么最大实验次数k_max就是6那么由公式**n2^k_max**可得n2^6!3。由此可知在实验次数很少时这种估算结果误差很大。
4.2、估算的优化
在上面的3组例子中我们称为一轮实验。如果只进行一轮的话当n足够大时误差也会变小但不是足够小。 因此是否可以进行多轮实验然后取每轮实验的**k_max**平均值。例如进行100轮实验然后再取平均数k_max/100。最终在估算出n。下面是**LogLog**的估算公式 其中DVLL 对应的就是nm对应实验的轮次头上有一横的R就是平均数(k_max1k_max2…k_maxm)/mconstant是修正因子可以通过修改这个数值还改变误差率。
通过这种增加实验轮次然后取平均数是LogLog的做法。而HyperLogLog采用的不是平均数而是调和平均数。调和平均数和算术平均数的最大的区别在于调和平均数不容易受大的值影响。 求平均工资: A的是1000/月B的30000/月。采用平均数的方式就是 (1000 30000) / 2 15500 采用调和平均数的方式就是 2/(1/1000 1/30000) ≈ 1935.484 **调和平均数公式为**∑ 是累加符号 HypeLogLog结合调和平均数的计算公式为
4.3、HyperLogLog的做法
4.3.1、bit串
在Redis的HyperLogLog中其首先将要保存的元素通过hash函数计算得到其64位的hash值。并将这个hash值转换成bit串。例如hash值是5那么bit串就是“101”。 那么为什么要转换成bit串呢是为了和伯努利实验的正反面对应上。bit串中的0和1就对应了伯努利实验的正面和反面。假如一个数据的hash值的bit串是“100010000”那么从低往高从右往左数第一个1的位置就是出现正面的次数。 那么基于上面的估算结论我们就可以根据最大的抛掷次数来估算出大概进行了多少次实现。同样的也就可以根据存入的数据转化后出现1的位置k_max来估算出大致存了多少数据。
4.3.2、分桶
HyperLogLog中的分桶其实就是应伯努利实现估算优化中的多轮。每一个桶对应一轮的伯努利实验。转换成计算机存储就是存储的是一个单位是bit长度为L的大数组S将S分为m组其中m就是多轮实验。每组占用的bit个数是平均记为P那么存在以下关系 1、LS.length 2、Lm*P 3、以K为单位数组S占用大小为L/8/1024
在Redis中HyperLogLog中设置m为16834(16384个桶)P为6(每个桶占6位只占用6位原因bit串是64位的其中低14位用来计算桶的位置也就是说还有50位用来得到第一个1出现的问题如果1在最左边那么1的位置最大也就是502^6 64,是第一个大于50的数因此6位就可以完全存下1的位置)那么L168346(bit)。占用内存为168346/8/102412K。 ** 第0组 第1组 … 第16833组 ** [000 000] [000 000] [000 000] [000 000] … [000 000] 4.3.3、做法
在Redis中HyperLogLog首先将保存的元素转换成对应的hash值bit串(64位)。然后根据bit串来计算应该落在桶的位置。按照从右往左的顺序取14位(因为Redis只是将桶分为16384个2^14 ,14位正好可以将桶完全使用上)。根据低14位计算到桶的位置之后然后再根据剩下的50位从右往左找到第一个1的位置。如果1出现的位置indexoldIndex那么index会替换掉oldIndex。否则是跳过。
参考文章 HyperLogLog在线观察** **
