Redis 的 PFADD，用的是 HyperLogLog 算法，按理说是有 False Negative 的吧，实测了 100W 数据却没有

[oldcai]

正在跑 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 差不多？

可能是我对算法理解有问题，请指点一下。

[mind3x]

你用同一套已经加进去的数据怎么测 false negative...

[oldcai]

@mind3x 测的就是再加已经加进去的数据是否可能判断为未加过。

[kaolalotree]

HLL 算法的目的是基数统计，针对的是统计不同的数的个数，

[Mirana]

同一个数重复加对于结果集没有影响

[mind3x]

@oldcai 你可以简单的推理一下，如果存在这样的数据，整个 HyperLogLog 还有什么意义。你把这个数据 pfadd 个几十万次， count 还是零。

[oldcai]

@kaolalotree 对，我是为了统计已加进去的数据是否存在被判断为未加进去的可能。

@mind3x 因为是计数算法，所以存在 False Negative 是可以接受的，但是如果是排重算法，就是未必可接受的了。

我看看具体的算法实现吧，先前看的都只是别人讲述的这个算法的原理。

[maguowei]

不应该用 pfadd 的返回值做统计
https://stackoverflow.com/questions/24391756/return-value-of-pfadd-in-redis