Redis源码中hyperloglog结构的实现原理是啥( 三 )
简单来看，其实 HyperLogLog 的基数统计就使用了这样的思想，通过二进制中
出现的第一个位置来估算整体的数量。首先把这批元素通过 hash 函数处理成
序列，然后把这批
序列都放入
个桶，然后通过计算这个桶里面所有
序列的
的最大值，就可以预估出整体的数量。i.e.
整体的数量预估是
个桶：计算出
预估不重复的元素个数是
那么如果只有
个桶，其实是会存在一定的偏差的。为了解决这个问题，一种想法就是重复以上操作，从 hash 函数开始处理成
序列，每次都把这批
序列放入
个桶，每次获得一个
值。总共操作
次，第
次操作得到的值记为
于是就可以对
进行均值处理，可以使用以下方法：
算术平均数：
几何平均数：
调和平均数：
中位数：
从而可以预估整体的数量为
如果按照以上的步骤进行操作，就是需要重复进行多次操作，在足够多的情况下，其实是没有必要那么操作的。HyperLogLog 也是用了多个桶，但是用了一个截断的技巧。对于一个
序列
HyperLogLog 从某个位置
开始，低位
用于决定桶的序号，也就是第几个桶。桶的个数就是
推荐阅读
- microsoft redistributable为啥不做成一个带可选项的程序
- 网站完整源码能有途径获取吗
- cygwin下源码编译openssl出错
- redis中的hset怎样快速地找到最大key或最大value，有办法快速地知道一个hset中key的个数 或 value的个数吗
- 怎样借助 redis 进行内容的排序，并将关注的 feed 流推送进来，聚合在一起，显示出来
- 有关JDK源码中一些元素类型在方法实现方面的效率问题请大牛们指点迷津一下，谢谢！?
- wordpress首页文章摘要字数设置具体源码在文中！求大神！
- 开发一个网站的价格，做一个网站要多少钱，需要源码的呢
- 写一个类，让toString()输出这个类的源码
- 如果让一个程序随机的修改自己源码无限制的编译且复制自身，是否有一日会出现一个完善的人工智能