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

百万字符串检查是否重复有啥好办法不

  •  
  •   git00ll · 124 天前 · 1111 次点击
    这是一个创建于 124 天前的主题,其中的信息可能已经有所发展或是发生改变。

    目前是利用 redis set 实现判断,但这么大的数据量与 redis 交互还是有点慢。

    要求精准,不误判,不漏判

    第 1 条附言  ·  122 天前

    使用场景如下:

    用户上传excel文件,需要解析文件并且禁止某一列的值存在相同的。还要查找出哪一行是重复的。

    因为解析excel是个更加消耗资源的过程,且为了减少内存占用使用流式解析,即每次只能读取到一行记录。

    并且文件可能很大,用java的set可能导致oom,现采用redis set,在内存中累计1000条,批量插入redis set中。 这是我能想到一定内存下的最好方式了。

    布隆过滤器应该是不满足条件的,这里需要精准判断是否重复,不误判,漏判。

    9 条回复    2021-08-02 10:06:52 +08:00
    ClarkAbe
        1
    ClarkAbe  
       124 天前
    AC 自动机试试?不过感觉会更....
    lerry
        2
    lerry  
       124 天前
    如果字符串比较长,可以先 hash 一下
    bagheer
        3
    bagheer  
       123 天前
    按行存为 txt, 然后 sort -u
    Mohanson
        4
    Mohanson  
       123 天前
    前缀树
    wellsc
        5
    wellsc  
       123 天前 via iPhone
    又到了布隆过滤器时刻了
    blackshadow
        6
    blackshadow  
       123 天前 via iPhone
    布隆,或者布谷鸟?
    Samuelcc
        7
    Samuelcc  
       123 天前 via Android
    可以描述一下使用场景。
    例如是已经有一个词库,不断有新的输入和词库查重,还是就是固定的百万字符串里找重复的?
    如果是前者,这个词库会有变化吗?
    sadfQED2
        8
    sadfQED2  
       122 天前 via Android
    要求精确的话布隆过滤器就别瞎掺和了吧。
    建议
    1.redis set,redis 根本不是你的瓶颈,读文件才是瓶颈
    2.楼上的前缀树也可以,但是实现比 redis set 方案复杂太多了
    sadfQED2
        9
    sadfQED2  
       122 天前 via Android
    另外提醒一下,excel 我记得最多就 5 万多行吧,jvm 堆内存搞大点,set 也不会 oom 吧
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2919 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:57 · PVG 18:57 · LAX 02:57 · JFK 05:57
    ♥ Do have faith in what you're doing.