求救！限时 12 小时！ mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办
0x0208v0 · 2020-08-27 18:51:28 +08:00 · 12371 次点击这是一个创建于 1348 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题：
马上下班了，突然来了一个需求，
mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办，
我想破脑子都没想明白应该怎么做，感觉这个除了遍历没有其他方法了，
如果遍历的话，是 O(mn)，也就是 100 百万 * 5 亿次匹配，这也太慢了，12 个小时也搞不完，求大佬帮忙想想办法。
第 1 条附言 · 2020-08-27 20:10:15 +08:00
多谢各位回答，补充一下问题，如果人名是 tom，email 是 [email protected] ，我想在数据库匹配出 该条 email 的数据
第 2 条附言 · 2020-10-06 13:29:12 +08:00
终于，跟老板说了一下自己做不了以后，就放弃做这个了。估计也会在老板脑海中留下能力不行的标签
 |
101
glfpes 2020-08-28 15:39:58 +08:00
spark join 一下就好，处理大数据就用最专业的大数据处理工具嘛。
|
 |
102
kethylar 2020-08-28 16:48:05 +08:00
有个想法
5 亿 email 先导出到 email.txt 每行一个 取 100w 行人名第一个 name grep name email.txt >包含 name.txt grep -V name email.txt > 不包含 name.txt 取第二个 name2 grep name2 不包含 name.txt > 不包含 name 但包含 name2.txt grep -V name2 不包含 name.txt > 不包含 name 也不包含 name2.txt 感觉这样下去每次 grep 的时间会越来越短 数据量越来越少 这样先筛出不包含 100w 名字的 email 有哪些 |
 |
103
goodboy95 2020-08-28 16:56:55 +08:00  1
@xupefei 字典树是常规 O(L^2)，AC 是个常数略大的 O(L)，（ L 一般是 10-20 之间）。性能上 AC 确实占些优势，不过两种方法都能胜任。
只不过嘛，对于之前没打过竞赛的人，AC 写起来应该挺麻烦吧，字典树写起来简单一些，调 bug 好调。这个 12 小时是包含写代码和调试的时间的…… |
 |
104
dingyaguang117 2020-08-28 17:53:14 +08:00
|
 |
105
MoYi123 2020-08-28 18:00:57 +08:00 1
除了 ac 自动机外再提供一个写起来简单的方法
假设英文名长度在 3-10 之间，把英文名按长度存到 8 个哈希表中（其实存到一个里也没关系），用长度是 3-10 的滑动窗口遍历邮件地址，窗口每动一下去查一下对应长度的哈希表，时间复杂度也是 O(N)。 应该用几个小时就能跑完。 |
 |
106
pixstone 2020-08-28 18:14:46 +08:00
|
 |
107
xxxy 2020-08-28 18:35:14 +08:00
来个大佬总结下啊，上面的方案究竟行不行
|
 |
108
winglight2016 2020-08-28 18:59:59 +08:00
用 mongodb 自带的 mapreduce 就可以了，首先确保建立索引，然后把一百万名字分组，循环用$in 过滤就可以了。连多线程都没必要用，我试过在上亿条记录里做 group/sum 这种操作，都是 100 毫秒以内。惟一可能产生瓶颈的就是写入操作，这个也问题不大，写入同一个 mongodb 应该是够快了。
|
|
109
winglight2016 2020-08-28 19:01:32 +08:00
刚才忘记说了，凡是 hash 操作都不如直接在 mongo 中建立索引，所以不管是 email 还是人名，都丢到 mongo 中处理是最快的。
|
 |
110
xupefei 2020-08-28 19:25:09 +08:00 via iPhone
@MoYi123 你仔细想想看时间复杂度是多少😂？先查长度 10 还是长度 3 ？长度 10 的结果和长度 3 的结果怎么合并？
|
 |
112
levelworm 2020-08-28 20:04:34 +08:00 via Android
我个人觉得自己写程序可能都不如现成的工具，数据库操作应该就蛮快的。不过我还是不清楚具体的判断规则。。。
|
|
113
MoYi123 2020-08-28 22:11:56 +08:00
@xupefei
emails = ['[email protected]'] names = {'alice', 'bob'} min_name_length = 3 max_name_length = 10 for email in emails: ____for window_size in range(min_name_length, max_name_length): ________left, right = 0, window_size ________while right <= len(email): ____________if email[left:right] in names: ________________print(email) ____________left += 1 ____________right += 1 因为 email 地址和 name 肯定都是很小的值，所以下面 2 个循环是 O(1),整体是 O(n)没有问题吧。 |
|
114
xupefei 2020-08-28 22:50:59 +08:00
@MoYi123
for email in emails: ----- 邮箱数 N ____for window_size in range(min_name_length, max_name_length): ----- r = len - window_size + 1 ________left, right = 0, window_size ________while right <= len(email): ------- email 平均长度 len ____________if email[left:right] in names: -------- 1 ________________print(email) ____________left += 1 ____________right += 1 我会说你算法的复杂度是 O(N*len*r) = O(N*len^2)。 |
 |
115
MrKou47 2020-08-29 02:33:31 +08:00 via iPhone
楼主人呢？
|
 |
116
daimiaopeng 2020-08-29 07:37:12 +08:00 1
年轻的码农还在想方案，年迈的码农已经开始面试了。
|
 |
117
zengming00 2020-08-29 09:43:22 +08:00
楼主已经成功入职下一家
|
 |
118
GtDzx 2020-08-29 12:59:28 +08:00
@atwoodSoInterest 明白了，有道理。email 不会太长。
|
 |
119
q9OxQg 2020-08-29 19:06:27 +08:00 via Android
这帖子，我一个文科生，即使大部分回复都看不懂，依然收藏了这个帖子。
|
 |
120
aec4d 2020-08-30 23:18:53 +08:00 1
处理五亿条 email， 匹配 400 万个名字
咋一看 5 * 10^8 * 4 * 10^6 次匹配，但是这个地方 email 和 name 都很短 400 万名字，大概就 30M, 把它存成 set 把每一个 email，拆分，比如 abcd 拆分成 a,b,c,d,ab,bc,cd,abc,bcd,abcd, 去在 set 里面匹配，存在则表示 email 有效 set.contains 查询效率是 O(1) , 并发查询，记每次 contains 消耗 10ns 假设平均一个 email 拆分成 20 个，计算一下，处理五亿记录只需要 100s 写了一个试了一下，耗时 11 分钟，还有很大优化空间 https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7939811c4c2d417496593d760fbdb996 |
Select Language