微信号:AlgorithmFans

介绍:算法是程序员的内功!伯乐在线旗下账号「算法爱好者」专注分享算法相关文章、工具资源和算法题,帮程序员修炼内功.

BitMap 算法介绍

2018-12-25 20:00 帅地

(给算法爱好者加星标,修炼编程内功


作者:苦逼的码农 - 帅地 (本文来自作者投稿)


我们先来看个简单的问题。

假如给你20亿个非负数的int型整数,然后再给你一个非负数的int型整数 t ,让你判断t是否存在于这20亿数中,你会怎么做呢?

有人可能会用一个int数组,然后把20亿个数给存进去,然后再循环遍历一下就可以了。

想一下,这样的话,时间复杂度是O(n),所需要的内存空间

4byte * 20亿,一共需要80亿个字节,

大概需要8GB的内存空间,显然有些计算机的内存一次是加载不了这么这么多的数据的。

初步优化


按照上面的做法,时间复杂度是O(n),内存是8GB,实际上我们是可以把时间复杂度降低到O(1)的。

例如我们可以这样来存数据,把一个int非负整数n作为数组下标,如果n存在,则对应的值为1,如果不存在,对应的值为0。例如数组arr[n] = 1,表示n存在,arr[n] = 0表示n不存在。

那么,我们就可以把20亿个数作为下标来存,之后直接判断arr[t]的值,如果arr[t] = 1,则代表存在,如果arr[t] = 0,则代表不存在。这样,我们就可以把时间复杂度降低到O(1)。不过空间复杂度我们并没有降低。还稍微大了点。

由于int非负整数一共有 2^31 个,所以数组的大小需要 2^31 这么大。

这里可能有人说也可以用HashSet来存啊,时间复杂度也是近似O(1)。不过这里需要说明的是,HashSet里面存的必须是对象,也就是说需要把int包装成Integer,显然一个对象的话是更花销内存的,需要对象头啊什么的…..

再次优化


大家想一个问题,对于一个数,实际上我们只需要两种状态,就是这个数存在不存在这两种可能。上面我们用1代表存在,用0代表不存在。

也就是说,我们是可以不用int型的数组来存储的,一个int型占用4个字节,即32个二进制位,一共可以表示40亿多个状态。用int型的来存两个状态,多浪费。

所以我们可以考虑用boolean型的来存的,boolean貌似就占用一个字节(java中的boolena貌似是占用一个字节)。而一个boolean有true和false两种状态,所以也是成立的。这样子的话占用的内存就是2GB的内存了。

这样,就可以降低到之前的四分之1内存了。

最终优化:bitmap


大家再想一个问题,虽然boolean是表示两种状态,但是boolean实际上占用了8bit啊,按道理8bit是可以表示128种状态的。而被我们拿来表示两个状态,是否也有点浪费了呢?

我们都知道,一个二进制位,有0和1两种状态,所以说,其实我们是可以用一个二进制位来代表一个int型的数是否存在的。例如对于1,3,5,7这四个数,如果存在的话,则可以这样表示:

1代表这个数存在,0代表不存在。例如表中01010101代表1,3,5,7存在,0,2,4,6不存在。

那如果8,10,14也存在怎么存呢?如图,8,10,14我们可以存在第二个字节里

以此类推。这样子,我们又可以把内存降低到之前的8分之一了。

这种采用一个二进制位来存储数据的方法,我们也叫做bitmap算法

可能有人会问,假如我要添加一个数n,我知道它要存在第n个位那里,把第n个二进制改为1,可是我要怎么操作呢?

这个对于bitmap算法是如何存储的,如何进行增删操作的,我会在之后的文章里讲,这篇就大概介绍下bitmap算法。

Java中有自带的bitmap实现,今天我们就用Java中自带的bitmap来做道题练练手。我们换道类似题目吧,不知道你一眼是否就能想到用bitmap算法来做。

题目描述:

现在有五十亿个int类型的正整数,要从中找出重复的数并返回。

判断50亿个数有哪些是重复和刚才上面那个判断是否存在,其实是一样的。我们采用bitmap算法来做。不过这里50亿个数,别人肯定是以文件流的形式给你的。这样我们为了方便,我们就假设这些数是以存在int型数组的形式给我们的

代码如下:

public class Test {
   //为了方便,假设数据是以数组的形式给我们的
   public static Set<Integer> test(int[] arr{
       int j = 0;
       //用来把重复的数返回,存在Set里,这样避免返回重复的数。
       Set<Integer> output = new HashSet<>();
       BitSet bitSet = new BitSet(Integer.MAX_VALUE);
       int i = 0;
       while (i < arr.length) {
           int value = arr[i];
           //判断该数是否存在bitSet里
           if (bitSet.get(value)) {
               output.add(value);
           } else {
               bitSet.set(valuetrue);
           }
           i++;
       }
       return output;
   }
   //测试
   public static void main(String[] args{
       int[] t = {1,2,3,4,5,6,7,8,3,4};
       Set<Integer> t2 = test(t);
       System.out.println(t2);
   }
}

代码可以左右滑动

打印结果:

[34]


当然,bitmap算法的应用不仅仅是节省内存,它还有很多其他的优点。之后有机会就拿一些其他的应用来写篇文章。

本次讲解到此结束。如果喜欢,可以分享给更多的小伙伴哦。

【本文作者】


帅地:一名热爱编程的在校生,目前维护订阅号「苦逼的码农」,专注于写于编程相关的文章



推荐阅读

(点击标题可跳转阅读)

算法有偏见么?

小鹿讲算法之三大排序算法:冒泡、插入、选择



觉得本文有帮助?请分享给更多人

关注「算法爱好者」加星标,修炼编程内功

喜欢就点一下「好看」呗~

 
算法爱好者 更多文章 82 个 Python 机器学习代码和实践案例让你受益终生! 冰与火之歌:「时间」与「空间」复杂度 好不容易写的爬虫,没爬几个就被封了,为什么? 法国数学长盛不衰的历史渊源 软件工程师转行人工智能必知必会 5 项技能,你了解么?
猜您喜欢 如何成为一个糟糕的程序员 【腾云计划】网络时代,谁来给你“安全感” API 调用次数限制实现 其实还是喜欢做那个专心敲码的程序员 Linux安全审计机制模块实现分析(5)