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

2024-01-10 23:44
文章标签 内存 qq 1g 百亿

本文主要是介绍在1G的内存中,对百亿个QQ号去重?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、公共方法
    • 1、生成模拟QQ号
    • 2、读取数据文件
    • 3、测试方法
  • 二、HashSet
  • 三、Java8的Stream
  • 四、Segment
  • 五、BloomFilter
  • 六、BitMap
  • 七、总结

假设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_SIZList<File> segmentFiles = new ArrayList<>();for (int i = 0; i < segmentCount; i++) {List<String> segment = list.subList(0, Math.min(MAX_SEGMENT_SIZE, lisSet<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 segmentFileFile file = null;try {file = File.createTempFile("qq_new_egment", ".txt");} catch (IOException e) {e.printStackTrace();}try (BufferedReader reader1 = new BufferedReader(new FileReader(segmentFiBufferedReader reader2 = new BufferedReader(new FileReader(segmentFiBufferedWriter 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关键字查询),但这种需要额外存储开销…

这篇关于在1G的内存中,对百亿个QQ号去重?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/592469

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

使用Java发送邮件到QQ邮箱的完整指南

《使用Java发送邮件到QQ邮箱的完整指南》在现代软件开发中,邮件发送功能是一个常见的需求,无论是用户注册验证、密码重置,还是系统通知,邮件都是一种重要的通信方式,本文将详细介绍如何使用Java编写程... 目录引言1. 准备工作1.1 获取QQ邮箱的SMTP授权码1.2 添加JavaMail依赖2. 实现

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C

golang内存对齐的项目实践

《golang内存对齐的项目实践》本文主要介绍了golang内存对齐的项目实践,内存对齐不仅有助于提高内存访问效率,还确保了与硬件接口的兼容性,是Go语言编程中不可忽视的重要优化手段,下面就来介绍一下... 目录一、结构体中的字段顺序与内存对齐二、内存对齐的原理与规则三、调整结构体字段顺序优化内存对齐四、内

Linux内存泄露的原因排查和解决方案(内存管理方法)

《Linux内存泄露的原因排查和解决方案(内存管理方法)》文章主要介绍了运维团队在Linux处理LB服务内存暴涨、内存报警问题的过程,从发现问题、排查原因到制定解决方案,并从中学习了Linux内存管理... 目录一、问题二、排查过程三、解决方案四、内存管理方法1)linux内存寻址2)Linux分页机制3)

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Redis多种内存淘汰策略及配置技巧分享

《Redis多种内存淘汰策略及配置技巧分享》本文介绍了Redis内存满时的淘汰机制,包括内存淘汰机制的概念,Redis提供的8种淘汰策略(如noeviction、volatile-lru等)及其适用场... 目录前言一、什么是 Redis 的内存淘汰机制?二、Redis 内存淘汰策略1. pythonnoe