【算法-位图法】在海量数据中查找重复元素

2023-10-13 19:30

本文主要是介绍【算法-位图法】在海量数据中查找重复元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是位图法?

举个简单例子,在java中一个int类型的数有32位,而这32只表示一个数太过浪费,于是就考虑让这32位可以表示32个数,每一位表示该数是否存在,例如:

这里用16位的二进制就能表示十六个数字,1表示存在,0表示不存在,上图就表示存在(16,12,6,4,1)这五个数。

在海量数据中查找重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题,一般可以通过位图法实现,例如,已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

本题最好的解决办法就是通过位图法来实现。

解题思路:

8位整数可以表示的最大十进制数值为99999999,如果每个数字对应于位图中的一个bit位,那么存储八位整数需要99999999bit大约99Mbit,因为1Byte=8bit,所以99Mbit折合成内存为99/8=12.375MB的内存,及可以只用12.375MB的内存表示所有的8位数电话号码的内容。

程序代码如下:

import java.util.Random;
public class DuplicateTelephone{int randNum=100;int min=10000000;int max=99999999;int len=(max-min+1);int bit_per_word=32;int  word_offset(int b){return b/bit_per_word;}int bit_offset(int b){return b%bit_per_word;}void setBit(int[] words,int n){int temp=n;temp-=min;words[word_offset(temp)]|=(1<<bit_offset(temp));}void clearBit(int[] words,int n){words[word_offset(n)]&=~(1<<bit_offset(n));}boolean getBit(int[] words,int n){int result=words[word_offset(n)]&(1<<bit_offset(n));return result!=0;}public void sort(){int arr[]=new int[randNum];System.out.println("数组大小:"+randNum);int[] words=new int[len/bit_per_word+1];int count=0;Random r=new Random();for(int j=0;j<randNum;j++){arr[j]=r.nextInt(len);arr[j]+=min;System.out.print(arr[j]+" ");}System.out.println();for(int j=0;j<randNum;j++){setBit(words,arr[j]);}System.out.println("排序后a为:");for(int i=0;i<len;i++){if(getBit(words,i)){System.out.print(i+min+" ");count++;}}System.out.println();System.out.println("总个数为:"+count);}public static void main(String[] args){new DuplicateTelephone().sort();}}

运行的结果为:

数组大小:100
46875852 63059260 46888254 54260213 84901496 58876931 28753082 72176161 30014077 84850078 31950213 14204495 26230245 27850510 32455193 68366470 52371514 87138574 94489525 45678876 90450237 42341450 24655913 43282877 49446847 42320941 84516417 35313419 59903775 35761368 11337291 46450272 93115232 55490862 11998766 73065445 47942924 18581547 58818184 77268172 99380374 80558928 16202169 95248485 20644397 34063612 20913170 94324174 67502076 80090509 45820098 81312556 32858162 16476350 15080157 45289864 99027018 87240729 89981567 52198533 39085177 76494986 65134775 93827194 13834939 71752586 32473580 67759555 29073921 72452538 98008564 58115033 64844962 59371680 86529508 69079674 61521841 96326355 25073903 19962950 33966761 83534685 38855968 14084970 85023410 78286139 81124660 48083315 57208466 72108161 26193937 67771844 22611251 51376666 43171943 82768547 47796300 19563949 91347170 47639405
排序后a为:
11337291 11998766 13834939 14084970 14204495 15080157 16202169 16476350 18581547 19563949 19962950 20644397 20913170 22611251 24655913 25073903 26193937 26230245 27850510 28753082 29073921 30014077 31950213 32455193 32473580 32858162 33966761 34063612 35313419 35761368 38855968 39085177 42320941 42341450 43171943 43282877 45289864 45678876 45820098 46450272 46875852 46888254 47639405 47796300 47942924 48083315 49446847 51376666 52198533 52371514 54260213 55490862 57208466 58115033 58818184 58876931 59371680 59903775 61521841 63059260 64844962 65134775 67502076 67759555 67771844 68366470 69079674 71752586 72108161 72176161 72452538 73065445 76494986 77268172 78286139 80090509 80558928 81124660 81312556 82768547 83534685 84516417 84850078 84901496 85023410 86529508 87138574 87240729 89981567 90450237 91347170 93115232 93827194 94324174 94489525 95248485 96326355 98008564 99027018 99380374
总个数为:100

这篇关于【算法-位图法】在海量数据中查找重复元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分,使用python生成公钥与私钥,然后保存在两个文

mysql中的数据目录用法及说明

《mysql中的数据目录用法及说明》:本文主要介绍mysql中的数据目录用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、版本3、数据目录4、总结1、背景安装mysql之后,在安装目录下会有一个data目录,我们创建的数据库、创建的表、插入的

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复