当前位置:首页 > 单片机 > 架构师社区
[导读]作者 l 会点代码的大叔(CodeDaShu)    有一道流传广泛的面试题: 给你一台 4G 内存的机器,一组 20 亿个无序正整数,如何快速地判断一个正整数 N 是否在这组数字中?或者如何快速地对这组数据排重后排序? 让我们先算算 20 亿个整数会占用多大的内存空间,J

20 亿个数字在 4G 内存中如何去重排序:快来试一试 BitMap

作者 l 会点代码的大叔(CodeDaShu)


有一道流传广泛的面试题:


给你一台 4G 内存的机器,一组 20 亿个无序正整数,如何快速地判断一个正整数 N 是否在这组数字中?或者如何快速地对这组数据排重后排序?


让我们先算算 20 亿个整数会占用多大的内存空间,Java 的 int 类型占用 4 个字节,那么 20 亿 * 4 再换算成 G 大约是 7.5G,大于题目中 4G 内存的限制,无法一次性地放到内存中;


这时候有些伙伴会说:“把数据放到磁盘上,然后分批将数据读取到内存中就行查询”,但是这种方法会导致多次磁盘 IO,而且只能解决第一个查找的问题,排序就没有办法做到了。



01

BitMap 的概念



BitMap 能够很好地解决这个问题;它是用一个 Bit 位来标记某个元素对应的 Value, 而 Key 即是该元素,比如我们初始化一个类型为 bit、长度为 8 的数组,数组下标 0-7,数组中的内容 1 表示存在,0 表示不存在,那么:


00000001 下标为 0 的位置,对应值是1,那么表示 0;同理:

00000010 表示 1;

00000100 表示 2;

00001000 表示 3;

...

10000000 表示 7;


如果一组数据 {2,3,4,7} 放到同一个数组中的话,就是 10011100:


如果按照 int 数组存储,{2,3,4,7} 需要 4 * 4 * 8 个 bit 才能存储的数据,但是现在 BitMap 只需要 8 个 bit 就可以存储,很大地节省了存储空间,并且排重后的排序也变的非常简单了;如果用 byte 实现的话,只需要 1 个 byte 就可以(1 byte = 8 bits)。


如果增加了一个数字 10 呢,那么 1 个 byte 就不够了:



02

数据结构及初始化



我们可以得知,BitMap 的容量大小取决于最大的那个数值,比如要存储 {2,3,4,7,10}:


  • 如果用 bit 数组实现(假如有的话),那么需要 10 + 1 个长度;

  • 如果是用 byte 数组实现,那么需要 10/8 + 1 个长度;

  • 如果是用 int 数组实现,那么就需要 10/32 + 1 个长度(1 个 int 等于 4 个 bytes,等于 32 个 bits);


明白了这点之后,一个简单的 BitMap 数据结构也就可以确定了:


public class BitMap { //数据 private byte[] bits;  //最大值 private int max_value; //容量 private int capacity;  /** * 初始化 * @param capacity */ public BitMap(int max_value){ this.max_value = max_value; //1bit存储8个数据,存储最大值为 max_value 的数组需要 max_value/8+1 个 byte,除以8就是右移3位 this.capacity = (max_value >> 3 ) + 1; bits = new byte[capacity]; }}



03

添加数据



添加数据,需要快速地定位到这个元素要存到整个数组中的哪个位置,这里有两个概念:


索引号 index:数据保存在整个数组的哪个下标中;


位置号 position:数据在这个下标元素的哪个位置;


比如 10 保存在 index = 1,position = 2(从 0 开始) 这个位置中,经推算可得:


index = N / 8position = N % 8


知道了 10 保存的位置之后,怎么把对应位置的数据更改成 1 呢?可以用“位或”运算。将 10 添加到 BitMap 中的完整步骤如下:


  • 计算 index = 10/8 = 1 ;

  • 计算 position = 10%8 = 2 ;

  • 将 byte[1] 的数据与 0000100 做“位或”运算,其中 0000100 是通过对 1 左移 2 得到。


完整的代码如下:


public void add(int num){ //数据保存在整个数组的哪个下标中 int index = num / 8; //数据在这个下标元素的哪个位置 int position = num % 8;  bits[index] |= 1<}



04

判断数字是否存在



知道了如何判断数字的索引号和位置号之后,判断数字是否存在也就容易了,直接使用“位与”运算,代码如下:


public boolean contains(int num){ if(num > max_value){ return false; } //数据保存在整个数组的哪个下标中 int index = num / 8; //数据在这个下标元素的哪个位置 int position = num % 8; return (bits[index] & 1<0;}


05

测试



让我们做一下测试吧:


public class BitMapTest { public static void main(String[] agrs){ BitMap bm = new BitMap(100);  bm.add(1); bm.add(12); bm.add(14); bm.add(51); bm.add(71); bm.add(100);  System.out.println("12:" + (bm.contains(12)?"存在":"不存在")); System.out.println("13:" + (bm.contains(13)?"存在":"不存在")); System.out.println("51:" + (bm.contains(51)?"存在":"不存在")); System.out.println("66:" + (bm.contains(66)?"存在":"不存在")); System.out.println("100:" + (bm.contains(100)?"存在":"不存在")); }}


运行结果:


12:存在13:不存在51:存在66:不存在100:存在


从结果可以看到,判断的都很准确,当然这只是一个最简单的BitMap实现,它还存在着很多问题,比如我们必须知道数据中最大的那个数字是多少,这个可以采用动态扩容的方式解决;


在 JDK 中,已经有对应实现的数据结构类 java.util.BitSet,我们可以不用强撸 BitMap,直接使用 BitSet 就好了,或者使用谷歌封装的 EWAHCompressedBitmap


06

优缺点



优点:

  • 占用内存空间低,可以极大地节约空间;

  • 运算效率高,查找、去重都不需要遍历全部数据;


缺点:

  • 所有的数据不能重复,相当于直接就是排重过的;

  • 如果数据只有两个:1 和 10000000,使用 BitMap 得不偿失,只有当数据比较密集时才有优势。


本章节介绍了 BitMap 的概念和基本实现,后续会介绍 BitMap 在实际开发中的应用。


特别推荐一个分享架构+算法的优质内容,还没关注的小伙伴,可以长按关注一下:

20 亿个数字在 4G 内存中如何去重排序:快来试一试 BitMap

20 亿个数字在 4G 内存中如何去重排序:快来试一试 BitMap

20 亿个数字在 4G 内存中如何去重排序:快来试一试 BitMap

长按订阅更多精彩▼

20 亿个数字在 4G 内存中如何去重排序:快来试一试 BitMap

如有收获,点个在看,诚挚感谢


免责声明:本文内容由21ic获得授权后发布,版权归原作者所有,本平台仅提供信息存储服务。文章仅代表作者个人观点,不代表本平台立场,如有问题,请联系我们,谢谢!

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

LED驱动电源的输入包括高压工频交流(即市电)、低压直流、高压直流、低压高频交流(如电子变压器的输出)等。

关键字: 驱动电源

在工业自动化蓬勃发展的当下,工业电机作为核心动力设备,其驱动电源的性能直接关系到整个系统的稳定性和可靠性。其中,反电动势抑制与过流保护是驱动电源设计中至关重要的两个环节,集成化方案的设计成为提升电机驱动性能的关键。

关键字: 工业电机 驱动电源

LED 驱动电源作为 LED 照明系统的 “心脏”,其稳定性直接决定了整个照明设备的使用寿命。然而,在实际应用中,LED 驱动电源易损坏的问题却十分常见,不仅增加了维护成本,还影响了用户体验。要解决这一问题,需从设计、生...

关键字: 驱动电源 照明系统 散热

根据LED驱动电源的公式,电感内电流波动大小和电感值成反比,输出纹波和输出电容值成反比。所以加大电感值和输出电容值可以减小纹波。

关键字: LED 设计 驱动电源

电动汽车(EV)作为新能源汽车的重要代表,正逐渐成为全球汽车产业的重要发展方向。电动汽车的核心技术之一是电机驱动控制系统,而绝缘栅双极型晶体管(IGBT)作为电机驱动系统中的关键元件,其性能直接影响到电动汽车的动力性能和...

关键字: 电动汽车 新能源 驱动电源

在现代城市建设中,街道及停车场照明作为基础设施的重要组成部分,其质量和效率直接关系到城市的公共安全、居民生活质量和能源利用效率。随着科技的进步,高亮度白光发光二极管(LED)因其独特的优势逐渐取代传统光源,成为大功率区域...

关键字: 发光二极管 驱动电源 LED

LED通用照明设计工程师会遇到许多挑战,如功率密度、功率因数校正(PFC)、空间受限和可靠性等。

关键字: LED 驱动电源 功率因数校正

在LED照明技术日益普及的今天,LED驱动电源的电磁干扰(EMI)问题成为了一个不可忽视的挑战。电磁干扰不仅会影响LED灯具的正常工作,还可能对周围电子设备造成不利影响,甚至引发系统故障。因此,采取有效的硬件措施来解决L...

关键字: LED照明技术 电磁干扰 驱动电源

开关电源具有效率高的特性,而且开关电源的变压器体积比串联稳压型电源的要小得多,电源电路比较整洁,整机重量也有所下降,所以,现在的LED驱动电源

关键字: LED 驱动电源 开关电源

LED驱动电源是把电源供应转换为特定的电压电流以驱动LED发光的电压转换器,通常情况下:LED驱动电源的输入包括高压工频交流(即市电)、低压直流、高压直流、低压高频交流(如电子变压器的输出)等。

关键字: LED 隧道灯 驱动电源
关闭