page contents

如何从大量的url中找出相同的url?

轩辕小不懂 发布于 2021-10-08 11:11
阅读 640
收藏 0
分类:Golang
  • url
  • 给定a、b两个文件,各存放50亿个url,每个url各占64个字节,内存限制是4G,请找出a、b两个文件中共同的url。

    2105
    Nen
    Nen
    - 程序员

    分析解答:由于每个url需要占64个字节,所以50亿个url占用空间的大小为50亿×64=5G×64=320G字节。由于内存大小只有4G,因此不可能一次性把所有的url都加载到内存中处理。对于这个类型的题目,一般都需要使用分治法,即把一个文件中的url按照某一特征分成多个文件,使得每个文件的内容都小于4G,这样就可以把这个文件一次性读到内存中进行处理了。对于本题而言,主要的实现思路为:

    (1)遍历文件a,对遍历到的url求hash(url)%500,根据计算结果把遍历到的url分别存储到a0,a1,a2,…,a499(计算结果为i的url存储到文件ai中),这样每个文件的大小大约为600M。当某一个文件中url的大小超过2G的时候,可以按照类似的思路把这个文件继续分为更小的子文件(例如:如果a1大小超过2G,那么可以把文件继续分成a11,a12…)。

    (2)使用同样的方法遍历文件b,把文件b中的url分别存储到文件b0,b1,…,b499中。

    (3)通过上面的划分,与ai中url相同的的url一定在bi中。由于ai与bi中所有的url的大小不会超过4G,因此可以把它们同时读入到内存中进行处理。具体思路为:遍历文件ai,把遍历到的url存入到hash_set中,接着遍历文件bi中的url,如果这个url在hash_set中存在,那么说明这个url是这两个文件共同的url,可以把这个url保存到另外一个单独的文件中。当把文件a0~a499都遍历完成后,就找到了两个文件中共同的url。

    请先 登录 后评论