谧怏弦 发表于 2025-6-9 15:16:25

Hyper loglog 简单理解

最近在学习redis, 看到hyper loglog 有这么近乎作弊的空间复杂度
着实好奇
其核心使用了概率统计 通过局部判断总体

[*]loglog
我们的任务是基数统计 判断不重复子串数量
字串由0/1排列而成
这就是典型的二项分布, 分布概率均为1/2
那不就是正态分布

当0与1数量相差小时集中在 x = μ上    当0与1数量相差大时集中在两端
可见当字串0/1分布越极端概率越小
假设 μ左侧为1多情况, μ右侧为0多情况
我们仅取一端 0多情况   简单用局部(50%)估计总体(100%)
而hyper loglog采用的就是 从右向左数没遇到1时数的0的个数m 保存这段数据中Max(m1, m2, …)
Max(m1, m2, …)中0的个数越多概率越小 反应基数数据量越大

[*]hyper 部分
针对了极端情况进行了优化
当基数极小却意外取到了大量的0 ,那基本就gg了
此时我们将数据分片, 每个片再依次求基数量, 取平均数 * 片数量
调和平均数 和 一般平均数
倘若 A工资为 1000 B工资为 30000
一般平均数下工资为 ( 30000+1000 ) / 2 = 15500
而调和平均数   2/( 1/1000 + 1/30000 ) ≈ 1935.484
显然在调和平均数的计算下 更不容易受到大值的影响

调和平均数
即有公式


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

艾晓梅 发表于 2025-12-10 07:02:39

谢谢分享，试用一下

奄幂牛 发表于 2025-12-12 03:04:05

感谢分享，下载保存了，貌似很强大

酝垓 发表于 2025-12-21 18:25:04

谢谢分享，试用一下

柩通奉 发表于 2025-12-24 20:43:10

感谢发布原创作品，程序园因你更精彩

纣捎牟 发表于 2026-1-5 22:51:20

感谢分享，学习下。

崔瑜然 发表于 2026-1-8 05:31:51

收藏一下   不知道什么时候能用到

倡遍竽 发表于 2026-1-10 07:17:50

感谢分享，学习下。

撙仿 发表于 2026-1-19 04:44:42

不错，里面软件多更新就更好了

党新苗 发表于 2026-1-26 09:00:19

懂技术并乐意极积无私分享的人越来越少。珍惜

靳夏萱 发表于 2026-1-26 09:01:18

感谢，下载保存了

吕梓美 发表于 2026-1-28 04:15:04

这个好，看起来很实用

麓吆 发表于 2026-1-29 07:16:11

过来提前占个楼

赴忽 发表于 2026-2-4 03:31:37

分享、互助 让互联网精神温暖你我

粹脍誊 发表于 2026-2-4 08:32:29

新版吗？好像是停更了吧。

咚獭 发表于 2026-2-5 09:33:24

分享、互助 让互联网精神温暖你我

明思义 发表于 2026-2-6 15:02:19

感谢发布原创作品，程序园因你更精彩

梅克 发表于 2026-2-8 05:45:47

谢谢楼主提供！

郜庄静 发表于 2026-2-10 17:47:59

谢谢分享，辛苦了

百里宵月 发表于 2026-2-10 21:09:42

东西不错很实用谢谢分享
页: [1] 2
查看完整版本: Hyper loglog 简单理解