在大数据环境下,我们常常需要处理数量极其庞大的数据集,但由于内存大小的限制,无法直接加载到内存中进行操作。这时就需要设计适合内存受限环境的算法,来解决问题。本文将以在内存不足的情况下,找出亿级规模整数集合中的不重复元素为例,探讨一种基于Bloom Filter的数据结构的解决方案。
问题分析
假设有一个包含2.5亿个整数的集合,需要找出其中不重复的整数。但内存无法容纳全部的2.5亿个元素。如果直接对集合进行遍历,内存会溢出。
一个直观的想法是分批读取数据,每次处理一小部分,并用一个 HashSet 来计数。但随着处理的数据越来越多,HashSet 的大小也会越来越大,还是存在内存溢出的风险。
Bloom Filter解法
针对上述问题,我们可以考虑使用Bloom Filter这种空间效率极高的概率数据结构。
Bloom Filter本质是一个很长的二进制向量和一系列随机映射函数。对每个元素,通过映射函数将其映射到二进制向量的不同位,并将其置为1。查询时也通过相同的映射函数,查看相应位是否都是1。
利点是只需要一个二进制向量即可表示一个集合,不需要存储元素本身。并可以实现间隔查询,不需要对集合进行遍历。理论上,2.5亿个元素只需要225MB的Bloom Filter,远小于元素本身的内存占用。
具体地,思路是:
初始化一个225MB大小的Bloom Filter
分批读取整数数据,每次处理1万个
对每批数据,将元素存入Bloom Filter
再次遍历数据,检查每个元素是否在Bloom Filter中命中
未命中的元素即为不重复元素代码实现Java代码示例如下:
java
public static void findUniqueIntegers(String inputPath, String outputPath) throws IOException {
BloomFilter bloomFilter = new BloomFilter(225 1024 1024);
BufferedReader reader = new BufferedReader(new FileReader(inputPath));
BufferedWriter writer = new BufferedWriter(new FileWriter(outputPath));
String line;
final int BATCH_SIZE = 10000;
while ((line = reader.readLine()) != null) {
int num = Integer.parseInt(line);
// 分批将数据存入Bloom Filter
bloomFilter.add(num);
if (bloomFilter.size() % BATCH_SIZE == 0) {
bloomFilter.flush(); // 持久化到磁盘
}
}
reader.close();
reader = new BufferedReader(new FileReader(inputPath));
// 再次遍历,检查哪些元素未命中
while ((line = reader.readLine()) != null) {
int num = Integer.parseInt(line);
if (!bloomFilter.check(num)) {
writer.write(line + "\n");
}
}
writer.close();
reader.close();
}
这里为了避免Bloom Filter过大,使用了分批持久化的策略,避免内存溢出。二次遍历时只检查元素是否在Bloom Filter中,而不需要加载集合本身。
总结
对于内存无法容纳的超大数据集,使用Bloom Filter可以实现高效地去重和查询。相比传统方法,具有以下优势:
内存占用小,只需要225MB内存即可处理25亿数据;
只需要两轮遍历即可完成,效率较高;
通过间隔查询代替遍历集合,降低内存压力。
当然Bloom Filter也存在一定误判率,需要权衡参数 另外,如果对容错要求较高,可以考虑使用HyperLogLog这种固定内存的数据结构。它可以精确计算巨大数据流distinct值,标准误差是0.8%。实现方法是维护每个元素的估计基数。
对于更复杂的业务场景,例如需要统计不同数字的频数,可以考虑使用Count-Min Sketch这种数据流统计算法。它使用多个哈希函数在多行计数器上统计频数,可以容忍一定程度的 hash 冲突。
无论使用何种算法,SPACE-TIME TRADEOFF是必须权衡的。内存受限情况下处理大数据问题,需要深入理解数据结构与算法的特性,权衡时间空间效率的平衡,设计出针对特定问题的优化方案。
本文给出了一种基于Bloom Filter解决大整数去重问题的设计思路。虽然无法覆盖所有场景,但希望可以作为算法设计的一个模板
