您好,匿名用户
随意问技术百科期待您的加入

如何从大数据中找出两条相同的信息

0 投票

有50亿条商品名称信息,每条信息最长是50个字符,给定限制内存是4G,如何从这50亿条商品信息中查找出任意两条相同商品名称信息。给出思路以及算法思路。

用户头像 提问 2012年 12月1日 @ Annie 上等兵 (299 威望)
分享到:

1个回答

0 投票

算法2粗糙版:基于布隆过滤器,扫一遍,找出那些可能是重复的。看完这个数据结构你就懂了。

算法2精确版:使用布隆过滤器,扫一遍,找出那些可能是重复的。再扫一遍,计算它们的出现次数,超过1的就是精确的答案。

---

算法1:基本思路是对n个信息进行相对比较平均的分组(使用 hash(info) % m 分成m组),使得每组构成的哈希表可以放在内存中,且保证相同的两个信息进入同一组,然后再对每一组中的数据建立哈希表进行匹配即可。

4GB内存大约可以存下8000w+个50Bytes,考虑到hash表的空间利用率,假设以5000w为一组,则需要1000组(这个数字可以适当增加,并且使用质数的话通常效果更好)。

时间复杂度和空间复杂度都是O(n)。

p.s. 由于涉及到了外存,所以时间和空间复杂度其实就是扯淡。这个算法需要将所有数据先扫描一次(读取),分组(写入硬盘),再对每组进行查找(再读取),也就是要读2次写1次。

用户头像 回复 2012年 12月1日 @ Capricorn 上等兵 (188 威望)
提一个问题:

相关问题

0 投票
0 回复 20 阅读
0 投票
1 回复 27 阅读
用户头像 提问 2013年 11月28日 @ Tryndamere 上等兵 (325 威望)
0 投票
1 回复 34 阅读

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...