Skip to content

Latest commit

 

History

History
13 lines (13 loc) · 1.61 KB

MergeBigFile.md

File metadata and controls

13 lines (13 loc) · 1.61 KB

两个 10G 大小包含 URL 数据的文件,最多使用 1G 内存,将这两个文件合并,并找到相同的 URL

这两个文件分别为A和B文件,因为内存无法将所有的URL都载入,所以可以考虑如下两种方法:

1. 分而治之

  • 遍历文件A,对每个url求取hash(url)%100,然后根据所取得的值将url分别存储到100个小文件(记为a0,a1,...,a99)中。这样每个小文件的大约为10G/100 = 100M。
  • 遍历文件B,采取和A相同的方式将url分别存储到100小文件(记为b0,b1,...,b99)。这样处理后,所有可能相同的url都在对应的小文件(a0vsb0,a1vsb1,...,a99vsb99)中,不对应的小文件不可能有相同的url。然后要求出100对小文件中url的并集和相同的url。
    • 可以把其中一个小文件a(i)的url存储到hashSet中。然后遍历另一个小文件b(i)的每个url,看其是否在刚才构建的hashSet中
    • 求相同URL:如果b(i)中的url在a(i)中,那么就是共同的url,存到文件里面就可以了。
    • 合并URL:把hashSet中的url都存到文件中,如果b(i)中的url不在hashSet中,那么就存到文件里面就可以了。

2. Bloom filter - 近似算法

  • 如果允许有一定的错误率,可以使用Bloom filter
  • 1G内存大概可以表示80亿bit。将其中一个文件中的url使用Bloom filter映射为这80亿bit,然后挨个读取另外一个文件的url
  • 求相同URL:检查是否存在Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。
  • 合并文件:将第二个文件中的并集都插入到文件中