Home Page
Search
\begin{md} ## 题目 给定两个集合,每个集合集合里面有 20 亿不重复数据(可以认为是数字),设计一个算法求出两个集合的交集,内存使用量最大 4 G,可以使用磁盘空间。 ## 解法 **采用分治的思想** 1. 考虑到数据量太大,所以直接建立 hash 表是不显示的,肯定会超过 4 G 内存。所以我们可以首先遍历集合 A, 然后计算每个元素的 hash 值 h, 再将 h % 1000, 根据值将元数据分别存储到 1000 个小文件 $a_0, a_1, ..., a_{999}$ 中。 分成 1000 份是考虑到内存,内存更多的话可以文件数可以设置得更小。 2. 遍历集合 B,采用和 A 相同的方式将文件映射到 1000 个文件 $b_0, b_1, ..., b_{999}$ 中。 3. 假设交集储存在文件 result 中,依次遍历文件 $a_i$, 建立 hash 表,然后遍历文件 $b_i$, 检查相应数据是否在 hash 表中,如果在的话保存到 result 中。 \end{md}
Home Page