Redis 支持基于 HyperLogLog 的基数计数统计，其算法思想和前两篇提到的 Linear Counting 和 LogLog Counting 的算法类似，本篇主要分析其源码——github:antirez/redis/src/hyperloglog.c 中的代码 Header Header 总共有 16 个字节，分别为 HYLL E N/U Cardin 如下图所示： HYLL 是 4 个魔法字节，为”HYLL” E 为 1 个字节表示Dense/Sparse N/U 为未来留下的空字节，共 3 个字节 Cardin 为缓存区，8 个字节 代码实现如下： struct hllhdr { char magic[4]; /* “HYLL” */ uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */ uint8_t notused[3]; /* … Continue reading “HyperLogLog 算法（三）—— Redis 中的 HyperLogLog”
LogLog 算法 在上一篇 HyperLogLog 算法（一）——Bitmap 与 LinearCounting中介绍了 Linear Counting 的算法，缺点在于从渐进复杂性的角度看，空间复杂度仍为 O(Nmax)，其空间利用效率依旧不高。基于 Linear Counting 算法，LogLog Counting 算法的空间复杂度仅有 O(log2(log2(Nmax)))，使得通过KB级内存估计数亿级别的基数成为可能。 考虑如下伯努利过程 A ：不停抛掷一枚均匀硬币，出现反面则继续抛掷，出现正面则停止抛掷，抛掷出的反面次数为 \( k\) ，那么可以容易得出： \[ P_A(x=k)=(\frac{1}{2})^k \quad k=0,1,2,3,4,5,…\] 考虑如下问题 1： 进行 \( n\) 次 A 过程，每一次过程的总抛掷次数都不大于某常数 \( k_{max}\) 的概率是多少？容易得出： \[ P_1(x\leq k_{max}) = [1-(\frac{1}{2})^{k_{max}}]^n\] 进行 \( n\) 次 A 过程，至少有一次过程，其抛掷次数等于常数 \( k_{max}\) 的概率是多少？容易得出： \[ P_2(x = … Continue reading “HyperLogLog 算法（二）——LogLog 与 HpyerLogLog”