V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
oldcai
V2EX  ›  Redis

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

  •  
  •   oldcai ·
    oldcai · 2016-09-02 16:32:49 +08:00 · 6019 次点击
    这是一个创建于 3040 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    7 条回复    2020-07-18 13:09:22 +08:00
    mind3x
        1
    mind3x  
       2016-09-02 19:49:55 +08:00
    你用同一套已经加进去的数据怎么测 false negative...
    oldcai
        2
    oldcai  
    OP
       2016-09-02 21:48:04 +08:00
    @mind3x 测的就是再加已经加进去的数据是否可能判断为未加过。
    kaolalotree
        3
    kaolalotree  
       2016-09-02 22:15:59 +08:00
    HLL 算法的目的是基数统计,针对的是统计不同的数的个数,
    Mirana
        4
    Mirana  
       2016-09-02 22:20:35 +08:00
    同一个数重复加对于结果集没有影响
    mind3x
        5
    mind3x  
       2016-09-02 22:26:34 +08:00 via Android
    @oldcai 你可以简单的推理一下,如果存在这样的数据,整个 HyperLogLog 还有什么意义。你把这个数据 pfadd 个几十万次, count 还是零。
    oldcai
        6
    oldcai  
    OP
       2016-09-02 22:57:47 +08:00
    @kaolalotree 对,我是为了统计已加进去的数据是否存在被判断为未加进去的可能。

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

    我看看具体的算法实现吧,先前看的都只是别人讲述的这个算法的原理。
    maguowei
        7
    maguowei  
       2020-07-18 13:09:22 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2640 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 09:56 · PVG 17:56 · LAX 01:56 · JFK 04:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.