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

2021-07-31 18:03:14 +08:00
 git00ll

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

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

1968 次点击
所在节点    编程
9 条回复
ClarkAbe
2021-07-31 18:14:34 +08:00
AC 自动机试试？不过感觉会更....
lerry
2021-07-31 18:27:14 +08:00
如果字符串比较长，可以先 hash 一下
bagheer
2021-07-31 21:24:13 +08:00
按行存为 txt, 然后 sort -u
Mohanson
2021-08-01 00:00:36 +08:00
前缀树
wellsc
2021-08-01 00:01:45 +08:00
又到了布隆过滤器时刻了
blackshadow
2021-08-01 00:25:39 +08:00
布隆，或者布谷鸟？
Samuelcc
2021-08-01 14:41:17 +08:00
可以描述一下使用场景。
例如是已经有一个词库，不断有新的输入和词库查重，还是就是固定的百万字符串里找重复的？
如果是前者，这个词库会有变化吗？
sadfQED2
2021-08-02 10:04:51 +08:00
要求精确的话布隆过滤器就别瞎掺和了吧。
建议
1.redis set，redis 根本不是你的瓶颈，读文件才是瓶颈
2.楼上的前缀树也可以，但是实现比 redis set 方案复杂太多了
sadfQED2
2021-08-02 10:06:52 +08:00
另外提醒一下，excel 我记得最多就 5 万多行吧，jvm 堆内存搞大点，set 也不会 oom 吧

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/792891

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX