精华内容
下载资源
问答
  • BItmap算法

    2020-03-13 12:29:00
    Bitmap 算法 目录 Bitmap 算法 1、什么是Bitmap算法 2、基本思想 3、如何如何确定10进制数到二进制的转换 ...1、什么是Bitmap算法 ...所谓的BitMap就是用一个bit位来...首先用一个简单的例子来详细介绍BitMap算法的原...

    Bitmap 算法

    目录

    Bitmap 算法

    1、什么是Bitmap算法

    2、基本思想

    3、如何如何确定10进制数到二进制的转换

    4、代码实现

     


    1、什么是Bitmap算法

    所谓的BitMap就是用一个bit位来标记某个元素所对应的value,而key即是该元素,由于BitMap使用了bit位来存储数据,因此可以大大节省存储空间


    2、基本思想

    首先用一个简单的例子来详细介绍BitMap算法的原理。假设我们要对1-8内的5个元素(5,6,8,1)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数,我们需要8个byte。

    1. 首先我们开辟一个字节(8byte)的空间,将这些空间的所有的byte位都设置为0

    2. 然后便利这5个元素,第一个元素是4,因为下边从0开始,因此我们把第五个字节的值设置为1

    3. 然后再处理剩下的四个元素,最终8个字节的状态如下图

    1 0 0 0 1 1 0 1

    要达到排序的目的:接下来我们只需要从左到右遍历一次数组,便可得到排序序列(1,5,6,8)。


    3、如何如何确定10进制数到二进制的转换

    (1)MAP映射:

    假设需要排序或则查找的数的总数N=100000000,BitMap中1bit代表一个数字,1个int = 4Bytes = 4*8bit = 32 bit,那么N个数需要N/32 int空间。所以我们需要申请内存空间的大小为int a[1 + N/32],其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推:

    a[0]  对应  0-31

    a[1]  对应  32-63

    a[2]  对应  64-95

    a[3]  对应  96-127

    以此类推

    (2)用位移将十进制数转换为对应的bit位

    1、求十进制数在对应数组a中的下标

    十进制数0-31,对应在数组a[0]中,32-63对应在数组a[1]中,64-95对应在数组a[2]中………,使用数学归纳分析得出结论:对于一个十进制数n,其在数组a中的下标为:a[n/32]

    2、求出十进制数在对应数a[i]中的下标

    例如十进制数1在a[0]的下标为1,十进制数31在a[0]中下标为31,十进制数32在a[1]中下标为0。 在十进制0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得在对应数组a[i]中的下标。

    3、位移

    对于一个十进制数n,对应在数组a[n/32][n%32]中,但数组a毕竟不是一个二维数组,我们通过移位操作实现置1

    a[n/32] |= 1 << n % 32

    ​ 移位操作:
      a[n>>5] |= 1 << (n & 0x1F)

    n & 0x1F 保留n的后五位 相当于 n % 32 求十进制数在数组a[i]中的下标


    4、代码实现

    public class BitMap {
    
        private static final int N = 10000000;
    
        private int[] a = new int[N/32 + 1];
    
        /**
         * 设置所在的bit位为1
         * @param n
         */
        public void addValue(int n){
            //row = n / 32 求十进制数在数组a中的下标
            int row = n >> 5;
            //相当于 n % 32 求十进制数在数组a[i]中的下标
            a[row] |= 1 << (n & 0x1F);
        }
    
        // 判断所在的bit为是否为0 
        public boolean exits(int n){
            int row = n >> 5;
            return (a[row] & ( 1 << (n & 0x1F))) != 0;
        }
    
        public void display(int row){
            System.out.println("BitMap位图展示");
            for(int i=0;i<row;i++){
                List<Integer> list = new ArrayList<Integer>();
                int temp = a[i];
                for(int j=0;j<32;j++){
                    list.add(temp & 1);
                    temp >>= 1;
                }
                System.out.println("a["+i+"]" + list);
            }
        }
    
        public static void main(String[] args){
            //int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
            int num[] = {4,7}
            BitMap map = new BitMap();
            for(int i=0;i<num.length;i++){
                map.addValue(num[i]);
            }
    
            int temp = 4;
            if(map.exits(temp)){
                System.out.println("value:[" + temp + "] has already exists");
            }
            map.display(3);
        }
    }

    运行结果:

    value:[4] has already exists
    BitMap位图展示
    a[0][0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    a[1][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    a[2][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

     

    展开全文
  • BitMap算法

    2020-05-29 15:49:28
    首先用一个简单的例子来详细介绍BitMap算法的原理。假设我们要对0-7内的5个元素(4,7,2,5,3)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数,我们需要8个byt.

    所谓的BitMap就是用一个bit位来标记某个元素所对应的value,而key即是该元素,由于BitMap使用了bit位来存储数据,因此可以大大节省存储空间。
     

    1. 基本思想

    假设我们要对0-7内的5个元素(4,7,2,5,3)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。

    7<2^3所以我们需要8个byte(这里我们使用int(32 bit)。

    1. 首先我们初始化一个int

    2. 然后便利这5个元素,第一个元素是4,因为下边从0开始,因此我们把第五个字节的值设置为1

    3. 然后再处理剩下的四个元素,最终前8个字节的状态如下图

    这样便达到了排序的目的

    从上面的例子可以看出,BitMap算法的思想还是比较简单的,关键的问题是如何确定10进制数到二进制的转换

    MAP映射:

    我们接着用int数组为例

      a[0]-----------------------------> 0-31 bit

      a[1]------------------------------> 32-63 bit

      a[2]-------------------------------> 64-95 bit

      a[3]--------------------------------> 96-127 bit

      ......................................................

    那么十进制数如何转换为对应的bit位,下面介绍用位移将十进制数转换为对应的bit位:

      1.求十进制数在对应数组a中的下标

    因为每个int对应32个bit,所以可得下标为n/32 =》a[n/32]

      2.求出十进制数在对应数a[i]中的下标

      通过模32求得在对应数组a[i]中的下标,即n%32。

      3.位移

      对于一个十进制数n,对应在数组a[n/32][n%32]中,但数组a毕竟不是一个二维数组,我们通过移位操作实现置1

      a[n/32] |= 1 << n % 32
      

    ​ 移位操作:
      a[n>>5] |= 1 << (n & 0x1F)

      n & 0x1F 保留n的后五位 相当于 n % 32 求十进制数在数组a[i]中的下标

    应用范围: 可以运用在快速查找、去重、排序、压缩数据等。

    例题: 力扣41. 缺失的第一个正数

    给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

     

    示例 1:

    输入: [1,2,0]
    输出: 3
    示例 2:

    输入: [3,4,-1,1]
    输出: 2
    示例 3:

    输入: [7,8,9,11,12]
    输出: 1
     

    提示:

    你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间。

    普通解法

    class Solution {
        public int firstMissingPositive(int[] nums) {
            int len = nums.length;
            int[] vis = new int[len+2];
            for( int i = 0; i < len ; i++){
                if(nums[i]>=1 & len>=nums[i])
                    vis[nums[i]] = 1;
            }
            for( int i = 1; i <= len+1; i++)
                if(vis[i] == 0)
                    return i;
            return 1;
        }
    }

    Bitmap解法

    官方题解
     

     

    展开全文
  • bitmap算法

    2019-05-19 16:15:30
    本文参考:Bitmap 算法解释与应用 概念 BitMap 就是用一个 bit 位来标记某个key对应的 value。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间。 使用场景 bitmap排序 假设我们要对5个不重复的数(4,7...

    本文参考:Bitmap 算法解释与应用

    概念

    BitMap 就是用一个 bit 位来标记某个key对应的 value。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间。

    使用场景

    bitmap排序

    假设我们要对5个不重复的数(4,7,2,5,3)排序。
    确定最大值是7,数值范围是0~7,共8个数,需要8bit,即1字节。

    此时8个字节与集合中的数的对应关系为:

    • 00010000 : 4
    • 10000000 : 7
    • 00000100 : 2
    • 00100000 : 5
    • 00001000 : 3

    所以最终8个bit的结果为10111100,遍历这8bit,所以排序结果为(7,5,4,3,2)。

    bitmap排序只有在数据比较密集的时候才会有有其优势,很多情况下并不适用。比如对(1,1000,10万)这种数据集排序就很不合适。

    bitmap查找

    找出10亿个数字中是否存在某个值

    使用bitmap+布隆过滤器,布隆过滤器可以看笔者另一篇文章 布隆过滤器简介

    bitmap去重

    已知某个文件内包含很多电话号码,每个号码为8个数字,统计不同号码的个数。

    8位最多99999999,占用100,000,000个bit,大小为12MB,这样用12M内存就表示来所有8位数的电话。

    bitmap查重

    10亿个整数中找出不重复的整数的个数,内存空间不足以同时容纳这10亿个整数。

    将bitmap扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。
    在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。

    展开全文
  • Bitmap算法

    千次阅读 2017-08-23 10:39:12
    中文:位图算法参考博客: 漫画:什么是Bitmap算法

    中文:位图算法

    参考博客:
    漫画:什么是Bitmap算法?

    展开全文
  • Bitmap 算法

    2017-12-11 15:34:14
    今天我们来聊聊 Bitmap 算法 为满足用户标签的统计需求,小灰利用Mysql设计了如下的表结构,每一个维度的标签都对应着Mysql表的一列: 要想统计所有90后的程序员该怎么做呢? 用一条求交集的SQL语句...
  • BitMap 算法

    2016-03-17 16:12:00
    什么是 BigMap 算法 所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value,而 ... 在内存中占32bit,可以用对应的32个bit位来表示十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,414
精华内容 565
关键字:

bitmap算法