如何找到 100 亿个 URL 中重复的 URL,及词汇的 Top 100 问题

题目描述

在一个包含 100 亿个 URL 的大文件中,找到其中所有重复的 URL,假设每个 URL 占用 64 B。

思路分析

假设用 HashSet 来保存 URL,那么极端的情况下如果 100 亿个数都不同,则 HashSet 会产生 100 亿条记录。

HashSet一条记录的大小是 4 个字节,那一共需要 6400 亿个字节,大约是 640 GB 的内存,显然这种方式不合适。

既然直接将所有 URL 都加载到内存中统计的方式不行,结合我们在前几篇文章学习到的思路,依然可以采用 哈希分流 的方式来处理。

在本场景中,我们可以将所有的 URL 通过哈希存到 1000 个文件中。

注意:具体要划分多少个文件,需要在面试的过程中跟面试官进行沟通,了解机器的内存大小等信息。重点是掌握思路和方法。

同一个 URL 经过哈希之后得到的结果一定是一样的,因为哈希函数的性质——相同的输入会产生相同的输出。

之后只需要对每个文件单独使用 HashSet 进行统计即可。

进阶问题

百亿搜索词汇,如何找到最热 TOP100 词汇?

进阶问题分析

像这种数据量这么大的问题,我们最开始还是用哈希分流来处理。

把包含百亿数据量的词汇通过哈希函数分流到不同的机器上。

具体需要多少台机器,我们可以在面试的时候与面试官进一步的交流数据量的大小,机器的限制,或者有其他的限制来决定。

对每一台机器来说,如果分到的数据量依然很大,比如,内存不够或其他问题,可以再用哈希函数把每台机器分到的词汇,进一步拆成多个小文件处理。

处理每一个小文件的时候,利用哈希表来进行统计。key 记录词汇,value 统计词频。

哈希表记录建立完成后,再遍历哈希表。

因为哈希表本身是无序。像这种 topk 问题,我们可以利用 小根堆 来帮我们进行统计。

遍历哈希表的过程中使用大小为 100 的小根堆来选出每一个小文件的 top100。

对同一机器上的所有小文件进行处理之后,每个小文件都有了自己词频的 top100。

接下来有两种方式处理:

  • 将每个小文件自己的 top100 进行排序之后,再对每个小文件进行外排序,得到每台机器上的 top 100。
  • 或者利用小根堆,来选出每台机器上的 top100。

最后,类似于处理同一机器上多个文件的方式,我们可以对不同机器之间的 top100,再进行外排序或者继续利用小根堆,最终求出整个百亿数据量中的 top100。

对于 top K 的问题,除哈希函数分流和用哈希表做词频统计之外,还经常用堆结构和外排序的手段进行处理。

总结

今天所讲解的两个问题主要是可以强化我们在解决大数据量的算法题中常用的哈希分流的思路,同时了解堆结构以及外排序的使用场景。

发表回复

后才能评论