在1G的内存中,对百亿个QQ号去重?

发布时间:2024年01月10日


假设QQ号是int类型,那么最多可以有4294967295个,就是43亿左右,QQ号无论多少位,每个数字只占用4个字节(32位)。如果要存储43亿个QQ号,需要的内存空间为43亿乘以4Byte=172亿Byte,172亿字节 ÷ (1024 × 1024 × 1024) ≈ 16GB。这只是存储QQ号本身所需的内存空间,不包括其他数据结构和索引所需的额外空间。

一、公共方法

1、生成模拟QQ号

private static void QQGenerator(int qqCount) {
	String[] qqs = new String[qqCount];
	Random random = new Random();
	for (int i = 0; i < qqCount; i++) {
		int randomNumber = random.nextInt(Integer.MAX_VALUE);
		qqs[i] = String.valueOf(randomNumber);
	}
	try (BufferedWriter writer = new BufferedWriter(new FileWriter("G:\\qq.txt"))) {
		for (String qq : qqs) {
			writer.write(qq + System.lineSeparator());
		}
	} catch (IOException e) {
		e.printStackTrace();
	}
}

2、读取数据文件

private static List<String> loadData(String s) {
	List<String> list = new ArrayList<String>();
	try (BufferedReader reader = new BufferedReader(new FileReader("G:\\qq.txt"))) {
		String line;
		while ((line = reader.readLine()) != null) {
			list.add(line);
		}
	} catch (IOException e) {
		e.printStackTrace();
	}
	return list;
}

3、测试方法

// 读取qq.txt里面的内容
List<String> list = loadData("G:\\qq.txt");
long statr = System.currentTimeMillis();
// qqDistinct为实际使用的方式
List<String> distinctQQList = qqDistinct(list);
System.out.println("去重后数量:" + distinctQQList.size());
System.out.println("执行耗时(单位ms):" + (System.currentTimeMillis() - statr));

二、HashSet

假设内存足够的话,可以使用这种方式

HashSet<String> set = new HashSet<>(list);
List<String> distinctQQList = new ArrayList<>(set);

实验情况如下:

实验1:数据量10W
去重后数量:99988
执行耗时(单位ms):28
实验2:数据量100W
去重后数量:999766
执行耗时(单位ms):149

三、Java8的Stream

假设内存足够的话,可以使用这种方式

List<String> distinctQQList = list.stream().distinct().collect(Collectors.toList());

实验情况如下:

实验1:数据量10W
去重后数量:99988
执行耗时(单位ms):63
实验2:数据量100W
去重后数量:999766
执行耗时(单位ms):254

四、Segment

利用归并排序思路,就是先把大文件拆成多个小文件,拆的过程中同时对文件内容去重+排序,再合并文件,合并过程中同时对内容排序。

每批的最大数量计算如下:

1G = 1,073,741,824字节,每个数字占用4个字节,那么1G内存可以存储的数字数量为:1,073,741,824字节 / 4字节 = 268,435,456个数字

代码实现如下:

// 每个分段的最大数量,根据实际情况调整大小即可,这里默认分20批
private static final int MAX_SEGMENT_SIZE = 50000;
private static List<String> distinctBySegment(List<String> list) {
	// 分段处理,文件拆成多个子文件,并排好序
	int segmentCount = (int) Math.ceil((double) list.size() / MAX_SEGMENT_SIZ
	List<File> segmentFiles = new ArrayList<>();
	for (int i = 0; i < segmentCount; i++) {
		List<String> segment = list.subList(0, Math.min(MAX_SEGMENT_SIZE, lis
		Set<String> segmentSet = new HashSet<>(segment);
		// 及时释放内存
		segment.clear();
		segment = new ArrayList<>(segmentSet);
		// 及时释放内存
		segmentSet.clear();
		Collections.sort(segment);
		File segmentFile = writeSegmentToFile(segment);
		// 及时释放内存
		segment.clear();
		segmentFiles.add(segmentFile);
	}
	// 子文件按照顺序,合成一个文件
	while (segmentFiles.size() > 1) {
		List<File> mergedSegmentFiles = new ArrayList<>();
		for (int i = 0; i < segmentFiles.size(); i += 2) {
			File segmentFile1 = segmentFiles.get(i);
			File segmentFile2 = (i + 1 < segmentFiles.size()) ? segmentFiles.
			if (null == segmentFile2) {
				mergedSegmentFiles.add(segmentFile1);
			} else {
				File mergedSegmentFile = mergeTwoSegmentsToNew(segmentFile1, 
				mergedSegmentFiles.add(mergedSegmentFile);
			}
		}
		segmentFiles = mergedSegmentFiles;
	}
	// 最终得到segmentFiles只有一个文件,且是排好序去重的
	File file = segmentFiles.get(0);
	List<String> distinctQQList = new ArrayList<String>();
	try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
		String line;
		while ((line = reader.readLine()) != null) {
			distinctQQList.add(line);
		}
	} catch (IOException e) {
		e.printStackTrace();
	}
	return distinctQQList;
}
private static File writeSegmentToFile(List<String> segmentSet) {
	File file = null;
	try {
		file = File.createTempFile("qq_egment", ".txt");
	} catch (IOException e) {
		e.printStackTrace();
	}
	try (BufferedWriter writer = new BufferedWriter(new FileWriter(file))) {
		for (String qq : segmentSet) {
			writer.write(qq + System.lineSeparator());
		}
	} catch (IOException e) {
		e.printStackTrace();
	}
	return file;
}
private static File mergeTwoSegmentsToNew(File segmentFile1, File segmentFile
	File file = null;
	try {
		file = File.createTempFile("qq_new_egment", ".txt");
	} catch (IOException e) {
		e.printStackTrace();
	}
	try (BufferedReader reader1 = new BufferedReader(new FileReader(segmentFi
		 BufferedReader reader2 = new BufferedReader(new FileReader(segmentFi
		 BufferedWriter writer = new BufferedWriter(new FileWriter(file))) {
		String qq1 = reader1.readLine();
		String qq2 = reader2.readLine();
		while (qq1 != null && qq2 != null) {
			if (qq1.compareTo(qq2) < 0) {
				writer.write(qq1 + System.lineSeparator());
				qq1 = reader1.readLine();
			} else if (qq1.compareTo(qq2) > 0) {
				writer.write(qq2 + System.lineSeparator());
				qq2 = reader2.readLine();
			} else {
				writer.write(qq1 + System.lineSeparator());
				qq1 = reader1.readLine();
				qq2 = reader2.readLine();
			}
		}
		while (qq1 != null) {
			writer.write(qq1 + System.lineSeparator());
			qq1 = reader1.readLine();
		}
		while (qq2 != null) {
			writer.write(qq2 + System.lineSeparator());
			qq2 = reader2.readLine();
		}
	} catch (IOException e) {
		e.printStackTrace();
	}
	return file;
}

实验情况如下:

实验1:数据量10W
去重后数量:99988
执行耗时(单位ms):402
实验2:数据量100W
去重后数量:999766
执行耗时(单位ms):2029

五、BloomFilter

内存估算公式

m = n * ln§ / (ln(2)^2)
m是BloomFilter的位数组大小(以位为单位),n是预期插入的元素数量,p是预期的误判率。

假设预期插入43亿个元素,误判率为0.001(0.1%),根据公式计算,Bloom Filter的位数组大小(m)约为 5,754,602,676 位,即约等于686MB,满足要求,在1G内。

代码实现如下:

// 预期插入的元素数量,这里默认设置为元素的2倍
private static final int EXPECTED_INSERTIONS = 2000000;
// 预期的误判率,must be > 0.0
private static final double FALSE_POSITIVE_RATE = 0.001;
private static List<String> distinctByBloomFilter(List<String> list) {
	List<String> distinctQQList = new ArrayList<>();
	BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), EXPECTED_INSERTIONS, FALSE_POSITIVE_RATE);
	for (String qq : list) {
		if (!bloomFilter.mightContain(qq)) {
			bloomFilter.put(qq);
			distinctQQList.add(qq);
		}
	}
	return distinctQQList;
}

实验情况如下:

实验1:数据量10W
去重后数量:99988
执行耗时(单位ms):163
实验2:数据量100W
去重后数量:999766
执行耗时(单位ms):1033

六、BitMap

Redis的Bitmap数据结构可以存储2^32个位,需要占用多少内存?
1位表示1byte,那么转为mb,就是2^32*8/1024/1024=512mb,满足要求,在1G内。

8 bit(位) = 1byte(字节)
1024 byte = 1kb
1024 kb = 1Mb
512MB:8 * 1024 * 1024 * 512 = 2^32

private static final String BITMAP_KEY = "duplicate_bitmap";
private static List<String> distinctByRedisBitMap(List<String> list) {
	List<String> distinctQQList = new ArrayList<>();
	Jedis jedis = new Jedis("localhost", 6379);
	// 去重计数
	for (String qq : list) {
		long bit = Long.parseLong(qq);
		boolean isDuplicate = jedis.getbit(BITMAP_KEY, bit);
		if (!isDuplicate) {
			// 设置位图中对应位为1,标识已经存在
			jedis.setbit(BITMAP_KEY, bit, true);
			distinctQQList.add(qq);
		}
	}
	// 获取去重后的数量
	long distinctCount = jedis.bitcount(BITMAP_KEY);
	System.out.println("Distinct count: " + distinctCount);
	jedis.close();
	return distinctQQList;
}

实验情况如下:

实验1:数据量10W
去重后数量:99988
执行耗时(单位ms):16331
实验2:数据量100W
去重后数量:999766
执行耗时(单位ms):157840

七、总结

实现方式HashSetStreamSegmentBloomFilterBitmap
10W数据耗时28ms63ms402ms163ms16331ms
100W数据耗时149ms254ms2029ms1033ms157840ms
  • HashSet和Stream性能好,不过内存占用较高,不满足1G内存要求;
  • Segment实现麻烦,需要额外文件,满足1G内存要求;
  • BloomFilter的性能看似还行,满足1G内存要求,但实际上性能和内存占用,取决于预期插入的元素数量和预期的误判率,可能存在一定误差;
  • Bitmap这种数据结构可以存储2^32个位,需要的内存不多,只需要512MB,占用内存最少,满足1G内存要求,但性能不行。

除此之外,还可以使用数据库的去重(唯一索引或DISTINCT关键字查询),但这种需要额外存储开销…

文章来源:https://blog.csdn.net/qq_36433289/article/details/135265308
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。