如题:
马上下班了,突然来了一个需求,
mongodb 存了 5 亿条 email,现有 100 万英文人名,想把包含人名的所有 email 找到,怎么办,
我想破脑子都没想明白应该怎么做,感觉这个除了遍历没有其他方法了,
如果遍历的话,是 O(mn),也就是 100 百万 * 5 亿次匹配,这也太慢了,12 个小时也搞不完,求大佬帮忙想想办法。
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 |