Redis 的 PFADD，用的是 HyperLogLog 算法，按理说是有 False Negative 的吧，实测了 100W 数据却没有
oldcai · oldcai · 2016-09-02 16:32:49 +08:00 · 5809 次点击这是一个创建于 2785 天前的主题，其中的信息可能已经有所发展或是发生改变。
正在跑 1000W 数据，但是感觉意义不大，应该还是没有吧。。
是不是有什么地方经过了特殊处理？
代码如下，如果缩进不被吃掉就能拿来测测
#!/usr/bin/env python3
import redis
redis_cli = redis.from_url('redis://localhost:6379/0')
count = 0
for i in range(0, 1000000):
if not redis_cli.pfadd('test', 'aaa%dbbb' % i):
count += 1
print(count)
count = 0
for i in range(0, 1000000):
if redis_cli.pfadd('test', 'aaa%dbbb' % i):
count += 1
print(count)
第一个 print 结果 940536 ，大概 94%左右的 True Positive ，也就是 6%左右的 False Positive
第二个显示 0 ，也就是都是 True Negative ，没有 False Negative
按理说 HyperLogLog 的 False Positive 和 False Negative 差不多？
可能是我对算法理解有问题，请指点一下。
 |
1
mind3x 2016-09-02 19:49:55 +08:00
你用同一套已经加进去的数据怎么测 false negative...
|
 |
3
kaolalotree 2016-09-02 22:15:59 +08:00
HLL 算法的目的是基数统计，针对的是统计不同的数的个数，
|
 |
4
Mirana 2016-09-02 22:20:35 +08:00
同一个数重复加对于结果集没有影响
|
|
5
mind3x 2016-09-02 22:26:34 +08:00 via Android
@oldcai 你可以简单的推理一下，如果存在这样的数据，整个 HyperLogLog 还有什么意义。你把这个数据 pfadd 个几十万次， count 还是零。
|
 |
6
oldcai OP @kaolalotree 对，我是为了统计已加进去的数据是否存在被判断为未加进去的可能。
@mind3x 因为是计数算法，所以存在 False Negative 是可以接受的，但是如果是排重算法，就是未必可接受的了。 我看看具体的算法实现吧，先前看的都只是别人讲述的这个算法的原理。 |
 |
7
maguowei 2020-07-18 13:09:22 +08:00
|
Select Language