海量数据中查找出重复出现的元素(位图法)
数据 出现 元素 查找 重复 海量
2023-09-14 09:07:35 时间
位图可以用来排序,去重等。
但下面的位图法一般用来做正整数的排序,去重;若有负整数,可以再新建一个队列专门存负整数,先转成正整数去比较,存在这个负整数队列。
理解:
8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位,那么存储8位整数大约需要99MB。因为1B=8bit,所以99Mbit折合成内存为99/8=12.375MB的内存,即可以只用12.375MB的内存表示所有的8位数电话号码的内容。
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import com.google.common.collect.Lists; /** * 位图 */ public class Weitu { private static final int BITSPERWORD = 32;// 整数位数 private static final int SHIFT = 5; private static final byte MASK = 0x1F;//5位遮蔽 0B11111 private static final int N = 1000; private static int[] a = new int[1 + N / BITSPERWORD]; private static List<String> list = new ArrayList<String>(1 + N / BITSPERWORD); public static void main(String[] args) throws Exception { Weitu tu = new Weitu(); // tu.readFile("/Users/zj/aa1.txt"); tu.readFile("C:/Users/zj/Desktop/aa1.txt"); for (int i = 0; i < list.size(); i++) { tu.set(Integer.parseInt(list.get(i))); } List<Integer> resultList = Lists.newArrayList(); for (int i = 0, length = a.length; i < length; i++) { if (a[i] != 0) { for (int j = 0; j < (1 << SHIFT); j++) { if (((1 << j) & a[i]) != 0) { resultList.add(i * (1 << SHIFT) + j); } } } } for (Integer xx : resultList) { System.out.println(xx); } System.out.println((1 << 31) - 1); System.out.println(Integer.MAX_VALUE); } // 置a[i>>SHIFT]的第(i & MASK)位为1,也就是位数组的第i位为1 public void set(int i) { if (test(i)) { System.err.println(i); } a[i >> SHIFT] |= (1 << (i & MASK)); } // 置a[i>>SHIFT]的第(i & MASK)位为0,也就是位数组的第i位为0 public void clr(int i) { a[i >> SHIFT] &= ~(1 << (i & MASK)); } public int test11(int i) { return a[i >> SHIFT] & (1 << (i & MASK)); } // 测试位数组的第i位是否为1 (可以用作重复问题) public static boolean test(int i) { return (a[i >> SHIFT] & (1 << (i & MASK))) == (1 << (i & MASK)); } public void readFile(String filePath) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(filePath))); String len; while ((len = br.readLine()) != null) { list.add(len); } br.close(); } }
相关文章
- 数据透视表上线!如何在纯前端实现这个强大的数据分析功能?
- 零零信安-D&D数据泄露报警日报【第47期】
- 使用google earth engine(GEE)提取2000年到2019年长江下游水体(河流、湖泊)数据[通俗易懂]
- 解决spark sql读取hudi表出现偶然读不出来数据问题
- pascal voc数据集下载_目标检测分类
- 使用Excel公式求出一组数据中指定文本连续出现的最大次数
- 数据治理专业认证CDMP学习笔记(思维导图与知识点)- 第八章数据集成和互操作篇
- 30个MySQL千万级大数据SQL查询优化技巧详解数据库
- java连接zookeeper服务器出现“KeeperErrorCode = ConnectionLoss for …”详解大数据
- Java数据持久层框架 MyBatis之API学习六(Mapper XML 文件详解)编程语言
- 简单操作,Oracle数据分组(oracle数据分组)
- MySQL插入数据时出现乱码问题怎么办?(mysql插库乱码)
- 使用MySQL查询语句进行模糊搜索:了解如何使用LIKE操作符快速检索数据库中的数据。(mysql查询like)
- 无法删除MySQL数据库中的数据?可能出现的几个问题及解决方法(mysql不能删数据)
- Oracle查询数据出现乱码问题的解决方法(oracle查询数据乱码)
- CSV格式数据导入MySQL出现错误(csv导入mysql出错)
- Redis 加速数据更新周期(数据更新频繁用redis)
- 谨防Redis存储数据出现乱码问题(存到redis 值乱码)
- 确保数据准确性Mysql禁止负数输入(mysql 不能出现负数)
- MySQL数据无法修改出现问题的原因和解决方案(mysql 不能修改数据)
- 数据Oracle中去除冗余数据的策略(oracle中去掉重复的)
- asp.netdatalist绑定数据后可以上移下移实现示例