求救！限时 12 小时！ mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办

[0x0208v0]

如题：
马上下班了，突然来了一个需求，

mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办，

我想破脑子都没想明白应该怎么做，感觉这个除了遍历没有其他方法了，

如果遍历的话，是 O(mn)，也就是 100 百万 * 5 亿次匹配，这也太慢了，12 个小时也搞不完，求大佬帮忙想想办法。

[atwoodSoInterest]

其实只能匹配，楼上说的二分法，其实没有作用，因为人名是可以包含在中间的。

我觉得思路应该放在优化上，适当的剪枝或许能有大作用，比如在写匹配算法的时候，遇到 @就停止匹配，一下就减少了差不多一半的匹配次数。你多看看数据，应该是有一些数据是可以很轻易就去掉的，比如 qq 邮箱全数字这种就直接去掉，一下子也能剪去不少。

[atwoodSoInterest]

人名可以做成字典树，在匹配上也能快不少

[qq316107934]

@atwoodSoInterest #21 12h，感觉代码写不完啊，有限时间内最快捷的方案是洗数据+ 堆机器查，公司要是有 HDFS 的话放里面用 Hive 查。

[0x0208v0]

@atwoodSoInterest 谢谢大佬！我准备用字典树+减树法试试

[iseki]

建 AC 自动机然后遍历全部数据是唯一方案吧…优化也只能从其他角度上走比如加机器什么的…

[murmur]

ac 自动机这数据量也有点巨大
什么需求能有五亿邮件

[iseki]

啊…人名是有点多，内存可能装不下…那…加机器？

[iseki]

我觉得人名库编译成自动机装得下没问题

[laminux29]

估算了一下，一台 16 核 140GB 服务器，120GB * 250MB，C++纯内存跑大概需要 27-40 个小时。

这种服务器如果来一打，抛开数据交换时间，算一次的时间估计能压缩在 3 个小时内。

但问题是：

1.你们需要足够的服务器资源，以及足够强劲的内网带宽。服务器不够，或者内网带宽只有百兆，那就 GG 了。

2.你们需要经验丰富的分布式 C++数据处理经验。不然跑一次 3 小时，发现有问题，改下程序重新跑一次，3 小时又过去了。

3.从 MongoDB 的数据导出，再到 C++的分布式数据导入，需要全程不能踩坑。

比如，MongoDB 导出时，导出工具有 bug，导致处理了半个小时突然卡死；

或者 MongoDB 是分布式架构且数据导出对于磁盘甚至网络是随机 IO 操作；

或者 C++导入数据时忘了用 cache 提速导致导入时瓶颈在机械硬盘的随机 IO 上；

甚至，MongoDB 导出时，发现早期数据录入阶段，因为写策略没使用安全策略且踩了 MongoDB 的性能 bug 导致丢数据；

就算前面都顺利，在最后把这 120GB 均分到不同服务器时，发现交换机的带宽居然不够。或者早期图便宜只用了超 5 类线，等等，这些都是坑。

我咋感觉，这需求，有点像是公司恶意辞退？

[iseki]

额，难道是 12 小时内让你搞定？我还以为是单次任务最多跑 12 小时 emmm 十二小时内写代码测试跑完基本不太可能吧 emmm

[my1103]

下班没（手动狗头）

[lizytalk]

首先扫描一遍所有邮件建立一个 k-tuple （例如序列 abcd，它的所有 2-tuple 就是 ab,bc,cd ）的索引。然后对于每一个人名，只需要在有共同的 k-tuple 的那些邮件里用字符串匹配算法就行了（因为如果名字在邮件里出现了，必然会有共同的 k-tuple ），这样可以过滤掉很多邮件。
k 的选择，可以多选择几个，对不同长度的名字应用不同的 k 。

[fushall]

这需求，字典树都够呛能在一台有限内存的机器上跑出来。就算能，也得代码也得非常好，要是用 Python 那种语言，估计内存就爆炸了。12 小时之内没希望能完成，看得出来，这种提问，应该是你自己一个人在硬着头皮搞。明天直接说一下吧，这东西搞不来，楼上 有位大神都帮你分析了，你品你细品

[oneisall8955]

额，想起这个月初那天通宵搞对接第三方接口+上线，楼主看着办吧🐶

[0bit]

如果允许损失一定精度，可以考虑使用 Bloom Filter （布隆过滤器）

1. 先把名字规整化，全部小写，去除多余字符，每个名字一个字符串
2. 创建一个 BloomFilter，写入全部的名字规则
3. 遍历 MongoDB 的记录，判断是否在 BloomFilter 中，找出符合条件的

PS：如果公司故意恶心你，还不如直接走了算了。

[iseki]

啊，我傻了，我算错了，要是字典树写得不够好 100G 内存真是够呛塞得下

[nuk]

hyperscan ？

[HunterPan]

5 亿数据按前缀打到数据库的分片上，10 个分片就够了，然后 100w 查询 就这样

[heiheidewo]

@iseki 想啥呢，100w 个英文名建 AC 自动机，怎么要 100G 内存，英文名全部转成小写，撑死 1G 内存

[imdong]

非专科，算法渣，我想的办法是：

把邮件名中按字母建立索引，然后用人名去对应的索引中查找（假设名字中没有数字和符号）。

比如：
[e-mail] 同时进入：a t h o m 6 这几个的索引。

如果想加速，就每两两三三再建一层索引：

ha ah at to om 这样。

最后查询的话，拿 tom 去命中 t o m 或者 to om 中的数据。

然后再去检查，对比匹配的数量应该会少很多。