Redis源码中hyperloglog结构的实现原理是啥( 五 )
表示二进制中的最低位，
表示次低位。
然后可以通过
来计算放在第
个桶，这里
同时将
的高位拿出来，也就是
计算这批序列的
函数的最大值，然后记为
这一步也可以称为 merge 模块，也就是进行更新合并。compute Z := (\\sum_{j=1}^{m}2^{-M})^{-1};上一步就是 HyperLogLog 的另外一步，count 模块，于是，进一步估算出
HyperLogLog 的空间复杂度特别低，大约是
这个量级的，其中
是桶的个数，
是基数。HyperLogLog 的时间复杂度则是
只需要遍历一遍所有元素即可得到最终结果。
假设基数为
二进制就是
位，
最晚就会出现在第
个位置上；而
只需要
个 bit 就能够存储；假设基数为
二进制就是
位，
最晚会出现在第
个位置上；而
需要
个 bit 就可以存储。
算法对比在论文中，论文 "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm" 的作者们针对各种算法进行了对比，其实 HyperLogLog 的空间复杂度是非常小的，并且误差也在可控的范围内。
HyperLogLog 的定理证明在论文 "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm" 作者们得到上述定理，精准的给出了 HyperLogLog 算法的误差估计。因此，HyperLogLog 算法其实是有数学定理证明的。
以上只是获得了理论上的 HyperLogLog 算法，但是在实战中，其实是需要进行微调的。主要的微调部分是根据理论中的
推荐阅读
- microsoft redistributable为啥不做成一个带可选项的程序
- 网站完整源码能有途径获取吗
- cygwin下源码编译openssl出错
- redis中的hset怎样快速地找到最大key或最大value，有办法快速地知道一个hset中key的个数 或 value的个数吗
- 怎样借助 redis 进行内容的排序，并将关注的 feed 流推送进来，聚合在一起，显示出来
- 有关JDK源码中一些元素类型在方法实现方面的效率问题请大牛们指点迷津一下，谢谢！?
- wordpress首页文章摘要字数设置具体源码在文中！求大神！
- 开发一个网站的价格，做一个网站要多少钱，需要源码的呢
- 写一个类，让toString()输出这个类的源码
- 如果让一个程序随机的修改自己源码无限制的编译且复制自身，是否有一日会出现一个完善的人工智能