精华内容
参与话题
问答
  • java基础--BitMap

    2019-10-15 21:54:00
    BitMap 在一些数据量比较大的场景中,做一些查重、排序,一般的方法难以实现。数据量过大,会占用较大的内存,常用的处理方式有两种:BitMap(位图法)和布隆过滤。 概述 一种大数据外部排序(内存无法加载所有...

                                                  BitMap

    在一些数据量比较大的场景中,做一些查重、排序,一般的方法难以实现。数据量过大,会占用较大的内存,常用的处理方式有两种:BitMap(位图法)和布隆过滤。

    概述

           一种大数据外部排序(内存无法加载所有排序元素)、去除重复元素、快速找到随机被删除元素的BitMap小算法,核心思想即通过将一个数作为下标(index)来索引一个bit表示一个数是否存在,排序时的时间复杂度为O(N),需要的额外空间的复杂度O(N/8),

    上面的算法都是用一个bit来表示一个数,即只有2种可能,要么有,要么无,可以扩展到一个字节表示一个数,这样就可以统计出现255次范围内的重复元素,原理以此类推。

    另外用bit来表示一个int数,节约了31倍的内存空间,即int(4*8),bit(8/1),所以数据量越来使用这种方式的优势越明显,前提是场景适用这种方式。

    可以使用bitmap算法,这个很有意思。特别是在数据量大的时候,非常高效
    所谓bitmap就是用一个bit位来标记某个元素对应的value,而key即是这个元素。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间。

    原理

    在java中,一个int类型占32个字节,我们用一个int数组来表示时未new int[32],总计占用内存32*32bit,现假如我们用int字节码的每一位表示一个数字的话,那么32个数字只需要一个int类型所占内存空间大小就够了,这样在大数据量的情况下会节省很多内存。

    具体思路:

    1个int占4字节即4*8=32位,那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据,其中N代表要进行查找的总数,tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

    tmp[0]:可表示0~31

    tmp[1]:可表示32~63

    tmp[2]可表示64~95

    .......

    那么接下来就看看十进制数如何转换为对应的bit位:

    假设这40亿int数据为:6,3,8,32,36,......,那么具体的BitMap表示为:

    如何判断int数字在tmp数组的哪个下标,这个其实可以通过直接除以32取整数部分,例如:整数8除以32取整等于0,那么8就在tmp[0]上。另外,我们如何知道了8tmp[0]中的32个位中的哪个位,这种情况直接mod32ok,又如整数8,在tmp[0]中的第8 mod32等于8,那么整数8就在tmp[0]中的第八个bit位(从右边数起)。

    //BitMap源码

    public class BitMap2 {
        //BitMap源码
        private long length;
        private static int[] bitsMap;
        private static final int[] BIT_VALUE = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
                0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
                0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
                0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000};
    
        public BitMap2(long length) {
            this.length = length;
            /**
             * 根据长度算出,所需数组大小
             * 当 length%32=0 时大小等于
             * = length/32
             * 当 length%32>0 时大小等于
             * = length/32+l
             */
            bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
        }
    
        /**
         * @param n 要被设置的值为n
         */
        public void setN(long n) {
            if (n < 0 || n > length) {
                throw new IllegalArgumentException("length value "+n+" is  illegal!");
            }
            // 求出该n所在bitMap的下标,等价于"n/5"
            int index = (int) n>>5;
            // 求出该值的偏移量(求余),等价于"n%31"
            int offset = (int) n & 31;
            /**
             * 等价于
             * int bits = bitsMap[index];
             * bitsMap[index]=bits| BIT_VALUE[offset];
             * 例如,n=3时,设置byte第4个位置为1 (从0开始计数,bitsMap[0]可代表的数为:0~31,从左到右每一个bit位表示一位数)
             * bitsMap[0]=00000000 00000000 00000000 00000000  |  00000000 00000000 00000000 00001000=00000000 00000000 00000000 00000000 00001000
             * 即: bitsMap[0]= 0 | 0x00000008 = 3
             *
             * 例如,n=4时,设置byte第5个位置为1
             * bitsMap[0]=00000000 00000000 00000000 00001000  |  00000000 00000000 00000000 00010000=00000000 00000000 00000000 00000000 00011000
             * 即: bitsMap[0]=3 | 0x00000010 = 12
             */
            bitsMap[index] |= BIT_VALUE[offset];
    
        }
        /**
         * 获取值N是否存在
         * @return 1:存在,0:不存在
         */
        public int isExist(long n) {
            if (n < 0 || n > length) {
                throw new IllegalArgumentException("length value illegal!");
            }
            int index = (int) n>>5;
            int offset = (int) n & 31;
            int bits = (int) bitsMap[index];
            // System.out.println("n="+n+",index="+index+",offset="+offset+",bits="+Integer.toBinaryString(bitsMap[index]));
            return ((bits & BIT_VALUE[offset])) >>> offset;
        }
    
    }
    

    BitMap应用

    1. BitMap小小变种:2-BitMap

    看个小场景:在3亿个整数中找出不重复的整数,限制内存不足以容纳3亿个整数。

    对于这种场景我可以采用2-BitMap来解决,即为每个整数分配2bit,用不同的01组合来标识特殊意思,如00表示此整数没有出现过,01表示出现一次,11表示出现过多次,就可以找出重复的整数了,其需要的内存空间是正常BitMap2倍,为:3亿*2/8/1024/1024=71.5MB

    具体的过程如下:

    扫描着3亿个整数,组BitMap,先查看BitMap中的对应位置,如果00则变成01,是01则变成11,是11则保持不变,当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。

     

       2.已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

    8位最多99 999 999,大概需要99mbit,大概10m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99MBit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)

    BitMap问题

    BitMap 的思想在面试的时候还是可以用来解决不少问题的,然后在很多系统中也都会用到,算是一种不错的解决问题的思路。

    但是 BitMap 也有一些局限,因此会有其它一些基于 BitMap 的算法出现来解决这些问题。

    • 数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题,那就可以考虑用 Bloom Filter 来解决,Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
    • 数据稀疏。又比如要存入(10,8887983,93452134)这三个数据,我们需要建立一个 99999999 长度的 BitMap ,但是实际上只存了3个数据,这时候就有很大的空间浪费,碰到这种问题的话,可以通过引入 Roaring BitMap 来解决。

    实例1

    int中32位只能表示一个数,而用BitMap可以表示32一个数:

    int[] bitMap:

    bitMap[0]:可以表示数字0~31 比如表示0:00000000 00000000 00000000 00000000

    比如表示1 : 00000000 00000000 00000000 00000001

    bitMap[1]:可以表示数字32~63

    bitMap[2]:可以表示数字64~95

    ……

    因此要将一个数插入到bitMap中要进过三个步骤:

    1)找到所在bitMap中的index也就是bitMap数组下标

    比如我们要在第64一个位置上插入一个数据(也就是插入63)

    index = 63 >> 5 = 1,也就是说63应该插入到bitMap[1]中

    2)找到63在bitMap[1]中的偏移位置

    offset = 63 & 31 = 31说明63在bitMap[1]中32位的最高位

    3)将最高位设为1

    public class BitMap {
        /** 插入数的最大长度,比如100,那么允许插入bitsMap中的最大数为99 */
        private long length;
        private static int[] bitsMap;
        private static final int[] BIT_VALUE = { 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
                0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
                0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
                0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000 };
    
        public BitMap(long length) {
            this.length = length;
            // 根据长度算出,所需数组大小
            bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
        }
        /**
         * 根据长度获取数据 比如输入63,那么实际上是确定数62是否在bitsMap中
         * @return index 数的长度
         * @return 1:代表数在其中 0:代表
         */
        public int getBit(long index) {
            if (index < 0 || index > length) {
                throw new IllegalArgumentException("length value illegal!");
            }
            int intData = (int) bitsMap[(int) ((index - 1) >> 5)];
            return ((intData & BIT_VALUE[(int) ((index - 1) & 31)])) >>> ((index - 1) & 31);
        }
        /**
         * @param index
         * 要被设置的值为index - 1
         */
        public void setBit(long index) {
            if (index < 0 || index > length) {
                throw new IllegalArgumentException("length value illegal!");
            }
            // 求出该index - 1所在bitMap的下标
            int belowIndex = (int) ((index - 1) >> 5);
            // 求出该值的偏移量(求余)
            int offset = (int) ((index - 1) & 31);
            int inData = bitsMap[belowIndex];
            bitsMap[belowIndex] = inData | BIT_VALUE[offset];
        }
    }
    
    public static void main(String[] args) {
            BitMap bitMap = new BitMap(63);
            bitMap.setBit(63);
            System.out.println(bitMap.getBit(63));
            System.out.println(bitMap.getBit(62));
        }
    

    实例 2

    BitMap 优缺点

    优点:实现简单。适合数据量比较大的场景。
    缺点:占用内存。申请的数组长度不好控制和最大的数值有关。当某个值特别大的情况下,映射的数组超过申请的数组容量,会出现下标越界。这也是上面提到的10亿个元素占用120M是最小内存的原因,实际可能会大于这个内存。

     

    10亿个正整数,给定一个数值,如何快速排定该数值是否在10亿个正整数当中?

    位图法的思想类似于hash寻址,首先初始化一个int数组,每个元素对应32位比特,将10亿个元素分别读入内存,对int数组中的元素比特位进行标记,如果存在,标记为1即可。标记完之后,即可快速判定某个元素是否在10亿个正整数当中,时间复杂度为O(1)。

     

    10亿个元素需要10亿个比特位,10亿/8/1024/1024 = 120 M,相比原来节省了 32 倍内存。

    需要申请多大的数组?

    array[0]:可表示0~31

    array[1]:可表示32~63

    array[2]可表示64~95

    数组长度为10亿/32 +1即可。

    1寻址

    比如元素 119,如何确定其对应的数组比特位 index ?
    1)确定数组 index:119/32 = 3.7,也就是第 4 个数组元素,a[3] 的位置。
    2)确定比特位 index:119%32 = 23,第23个比特位。
    3)将比特位设置为1。

    2设置比特位

    1)将比特位设置为1

    将第28个比特位设置为1:
    只需将 1 左移(31-28)位数,然后与原来的值进行或运算。

    2)将比特位设置为0

    将第28个比特位设置为0:
    只需将 1 左移(31-28)位数,并进行非运算,然后与原来的值进行与运算。

    3)判断某一元素是否存在

    判断 28 位比特位是否有元素存在:
    只需将 1 左移(31-28)位数,然后与原来的值进行与运算。只要与运算结果中有1,即表示元素存在。所以可以用运行结果是不为0作为元素是否存在依据。

    public class BigMapTest {
    
        private int[] bigArray;
    
        public BigMapTest(long  size){
            bigArray = new int[(int) (size/ 32 + 1)];
        }
    
        public void set1(int  num){
            //确定数组 index
            int arrayIndex = num >> 5;
            //确定bit index
            int bitIndex = num & 31;
            //设置0
            bigArray[arrayIndex] |= 1 << bitIndex;
        }
    
        public void set0(int  num){
            //确定数组 index
            int arrayIndex = num >> 5;
            //确定bit index
            int bitIndex = num & 31;
            //设置0
            bigArray[arrayIndex] &= ~(1 << bitIndex);
            System.out.println(get32BitBinString(bigArray[arrayIndex]));
        }
    
        public boolean isExist(int  num){
            //确定数组 index
            int arrayIndex = num >> 5;
            //确定bit index
            int bitIndex = num & 31;
    
            //判断是否存在
            return (bigArray[arrayIndex] & ((1 << bitIndex)))!=0 ? true : false;
        }
    
        /**
         * 将整型数字转换为二进制字符串,一共32位,不舍弃前面的0
         * @param number 整型数字
         * @return 二进制字符串
         */
        private static String get32BitBinString(int number) {
            StringBuilder sBuilder = new StringBuilder();
            for (int i = 0; i < 32; i++){
                sBuilder.append(number & 1);
                number = number >>> 1;
            }
            return sBuilder.reverse().toString();
        }
        
        public static void main(String[] args) {
    
            int[] arrays = new int[]{1, 2, 35, 22, 56, 334, 245, 2234, 54};
    
            BigMapTest bigMapTest = new BigMapTest(2234-1);
    
            for (int i : arrays) {
                bigMapTest.set1(i);
            }
            System.out.println(bigMapTest.isExist(35));
        }
    }
    

    其它

    十进制表示方法,不止一种

    ASCII

    BCD

    压缩BCD

    这些都是十进制编码,其中压缩BCD可以多存储一倍的数据

    其他,

    16Bits 可以表示万进制

    32Bits 可以表示亿进制,10   亿进制

    这些和十进制优势关系密切的表示方法,转换简单

    另外一种 多 字节(字,双字,四字)串 表示方法,

    是 二进制表示法,

    和十进制转换不太方便,不过+,-,*,/ 等数学运算,实现方便.

    展开全文
  • 深入理解Android Bitmap的各种操作

    万次阅读 多人点赞 2018-12-15 16:10:27
    在 Android 开发中,经常和 Bitmap 打交道,不知道你是否真正理解 Bitmap?接下来让我们一起走进 Bitmap 的世界。 一、Bitmap 1.1 Bitmap的创建 在 Bitmap 类中, Bitmap 构造方法默认权限,而且这个类也是 final...


    Android 开发中,经常和 Bitmap 打交道,不知道你是否真正理解 Bitmap?接下来让我们一起走进 Bitmap 的世界。

    一、Bitmap

      Bitmap 代表一个位图,BitmapDrawable 里封装的图片就是一个 Bitmap 对象。开发者为了把一个 Bitmap 对象包装成 BitmapDrawable 对象,可以调用 BitmapDrawable 的构造器:

    BitmapDrawable bitmapDrawable = new BitmapDrawable(bitmap);
    

    如果需要获取 BitmapDrawable 所包装的 Bitmap 对象,则可以用 BitmapDrawablegetBitmap() 的方法:

    Bitmap bitmap = bitmapDrawable.getBitmap();
    

    1.1 Bitmap的创建

      在 Bitmap 类中, Bitmap 构造方法默认权限,而且这个类也是 final 的,所以我们无法 new 一个 Bitmap 对象。可以根据静态方法 createBitmap 来创建 Bitmap 类。这些重载的方法有13个,他们分别是:
    在这里插入图片描述
    这些方法大致可以分为三类(本文所用的源码是 android - 26):

    1.1.1 根据已有的Bitmap来创建新Bitmap

    /**
    * 通过矩阵的方式,返回原始 Bitmap 中的一个不可变子集。新 Bitmap 可能返回的就是原始的 Bitmap,也可能还是复制出来的。
    * 新 Bitmap 与原始 Bitmap 具有相同的密度(density)和颜色空间;
    *
    * @param source   原始 Bitmap
    * @param x        在原始 Bitmap 中 x方向的其起始坐标(你可能只需要原始 Bitmap x方向上的一部分)
    * @param y        在原始 Bitmap 中 y方向的其起始坐标(你可能只需要原始 Bitmap y方向上的一部分)
    * @param width    需要返回 Bitmap 的宽度(px)(如果超过原始Bitmap宽度会报错)
    * @param height   需要返回 Bitmap 的高度(px)(如果超过原始Bitmap高度会报错)
    * @param m        Matrix类型,表示需要做的变换操作
    * @param filter   是否需要过滤,只有 matrix 变换不只有平移操作才有效
    */
    public static Bitmap createBitmap(@NonNull Bitmap source, int x, int y, int width, int height,
                @Nullable Matrix m, boolean filter) 
    

    1.1.2 通过像素点数组创建空的Bitmap

    /**
         * 
         * 返回具有指定宽度和高度的不可变位图,每个像素值设置为colors数组中的对应值。
         * 其初始密度由给定的确定DisplayMetrics。新创建的位图位于sRGB 颜色空间中。
         * @param display  显示将显示此位图的显示的度量标准
         * @param colors   用于初始化像素的sRGB数组
         * @param offset   颜色数组中第一个颜色之前要跳过的值的数量
         * @param stride   行之间数组中的颜色数(必须> = width或<= -width)
         * @param width    位图的宽度
         * @param height   位图的高度
         * @param config   要创建的位图配置。如果配置不支持每像素alpha(例如RGB_565),
         * 那么colors []中的alpha字节将被忽略(假设为FF)
         */
        public static Bitmap createBitmap(@NonNull DisplayMetrics display,
                @NonNull @ColorInt int[] colors, int offset, int stride,
                int width, int height, @NonNull Config config) 
    

    1.1.3 创建缩放的Bitmap

    /**
    * 对Bitmap进行缩放,缩放成宽 dstWidth、高 dstHeight 的新Bitmap
    */
    public static Bitmap createScaledBitmap(@NonNull Bitmap src, int dstWidth, int dstHeight,boolean filter)
    

    二、BitmapFactory

      BitmapFactory 是一个工具类,它提供了大量的方法,这个方法可用于不同的数据源来解析、创建 Bitmap 对象。大概有如下方法:
    在这里插入图片描述

    2.1 创建Bitmap的方法

    • decodeByteArray(byte[] data, int offset, int length, Options opts):从指定字节数组的 offset 位置开始,将长度 length 的字节数据解析成 Bitmap 对象。
    • decodeFile(String pathName, Options opts):从 pathName 指定的文件中解析、创建 Bitmap 对象。
    • decodeFileDescriptor(FileDescriptor fd, Rect outPadding, Options opts):用于从 FileDescriptor 对应的文件中解析、创建 Bitmap 对象。
    • decodeResource(Resources res, int id, Options opts):用于给定的资源 ID 从指定资源中解析、创建 Bitmap 对象。
    • decodeStream(InputStream is, Rect outPadding, Options opts):用于从指定输入流中解析、创建 Bitmap 对象。

    decodeFiledecodeResource 其实最终都会调用 decodeStream 方法来解析 Bitmap 。有一个特别有意思的事情是,在 decodeResource 调用 decodeStream 之前还会调用 decodeResourceStream 这个方法,接下来让我们看看 decodeResourceStream 方法的源码:

    public static Bitmap decodeResourceStream(Resources res, TypedValue value,
                InputStream is, Rect pad, Options opts) {
            validate(opts);
            if (opts == null) {
                opts = new Options();
            }
    
            if (opts.inDensity == 0 && value != null) {
                final int density = value.density;
                if (density == TypedValue.DENSITY_DEFAULT) {
                    opts.inDensity = DisplayMetrics.DENSITY_DEFAULT;
                } else if (density != TypedValue.DENSITY_NONE) {
                	  //这里 density 的值如果对应资源目录为 hdpi 的话,就是 240;如果是 xhdpi 则是 320;如果是 xxdpi 则是 480
                    opts.inDensity = density;
                }
            }
            
            if (opts.inTargetDensity == 0 && res != null) {
                opts.inTargetDensity = res.getDisplayMetrics().densityDpi;
            }
            
            return decodeStream(is, pad, opts);
        }
    

      这个方法主要对 Options (详解的属性值在下面)进行处理,在得到 opts.inDensity 的属性前提下,如果没有对该属性的设定值,那么 opts.inDensity = DisplayMetrics.DENSITY_DEFAULT; 这个值默认为标准dpi的基值:160。如果没有设定 opts.inTargetDensity 的值时,opts.inTargetDensity = res.getDisplayMetrics().densityDpi; 该值为当前设备的 densityDpi,这个值是根据你放置在 drawable 下的文件不同而不同的(具体参考 Android 屏幕各种参数的介绍和学习)。
      所以说 decodeResourceStream 这个方法主要对 opts.inDensityopts.inTargetDensity进行赋值。那什么时候使用这个 opts 属性呢?在将参数传入 decodeStream方法,该方法在调用 native 方法进行解析 Bitmap 后会调用 setDensityFromOptions 这个方法:

    /**
         * Set the newly decoded bitmap's density based on the Options.
         */
        private static void setDensityFromOptions(Bitmap outputBitmap, Options opts) {
            if (outputBitmap == null || opts == null) return;
    		 //opts.inDensity 这个值会因为你放置在 drawable 下不同分辨率的文件夹下而不同
            final int density = opts.inDensity;
            if (density != 0) {
                outputBitmap.setDensity(density);
                final int targetDensity = opts.inTargetDensity;
                if (targetDensity == 0 || density == targetDensity || density == opts.inScreenDensity) {
                    return;
                }
    
                byte[] np = outputBitmap.getNinePatchChunk();
                final boolean isNinePatch = np != null && NinePatch.isNinePatchChunk(np);
                if (opts.inScaled || isNinePatch) {
                    outputBitmap.setDensity(targetDensity);
                }
            } else if (opts.inBitmap != null) {
                // bitmap was reused, ensure density is reset
                outputBitmap.setDensity(Bitmap.getDefaultDensity());
            }
        }
    

    这个方法就是把刚刚赋值过的两个属性 inDensityinTargetDensityBitmap 进行赋值,不过并不是直接赋值给 Bitmap 而是判断 inDensity 的值与 inTargetDensity 或 该设备屏幕 Density 不相等 ,而且 opts.inScaled = true 时,条件才成立。具体的计算见:

    从上面的源码可以得出一个重要的结论:

    • decodeResource 在解析时会对 Bitmap 根据当前设备屏幕密度 densityDpi 的值进行缩放适配操作,使得解析出来的 Bitmap 与当前设备分辨率匹配,并且一般来说,这时 Bitmap 的大小将比原始的 Bitmap 大。
    • decodeFiledecodeStream 在解析时不会对 Bitmap 进行一系列的屏幕适配,解析出来的将是原始大小的图。

    2.2 BitmapFactory.Options的属性解析

    在使用 BitmapFactoryOptions 这个静态内部类经常用到,里面有很多经常使用的属性,让我们来看一些比较重要的:

    • inJustDecodeBounds:如果这个值为 true ,那么在解码的时候将不会返回 Bitmap ,只会返回这个 Bitmap 的尺寸。这个属性的目的是,如果你只想知道一个 Bitmap 的尺寸,但又不想将其加载到内存中时,是一个非常好用的属性。
    • outWidth和outHeight:表示这个 Bitmap 的宽和高,一般和 inJustDecodeBounds 一起使用来获得 Bitmap的宽高,但是不加载到内存。
    • inSampleSize:压缩图片时采样率的值,如果这个值大于1,那么就会按照比例(1 / inSampleSize)来缩小 Bitmap 的宽和高。如果这个值为 2,那么 Bitmap 的宽为原来的1/2,高为原来的1/2,那么这个 Bitmap 是所占内存像素值会缩小为原来的 1/4。
    • inDensity:表示这个 Bitmap 的像素密度,对应的是 DisplayMetrics 中的 densityDpi,不是 density。(如果不明白它俩之间的异同,可以看我的 Android 屏幕各种参数的介绍和学习
    • inTargetDensity:表示要被新 Bitmap 的目标像素密度,对应的是 DisplayMetrics 中的 densityDpi
    • inScreenDensity:表示实际设备的像素密度,对应的是 DisplayMetrics 中的 densityDpi
    • inPreferredConfig:这个值是设置色彩模式,默认值是 ARGB_8888,这个模式下,一个像素点占用 4ByteRGB_565 占用 2ByteARGB_4444 占用 4Byte(以废弃)。
    • inPremultiplied:这个值和透明度通道有关,默认值是 true,如果设置为 true,则返回的 Bitmap 的颜色通道上会预先附加上透明度通道。
    • inDither:这个值和抖动解码有关,默认值为 false,表示不采用抖动解码。
    • inScaled:设置这个Bitmap 是否可以被缩放,默认值是 true,表示可以被缩放。
    • inPreferQualityOverSpeed:这个值表示是否在解码时图片有更高的品质,仅用于 JPEG 格式。如果设置为 true,则图片会有更高的品质,但是会解码速度会很慢。
    • inBitmap:这个参数用来实现 Bitmap 内存的复用,但复用存在一些限制,具体体现在:在 Android 4.4 之前只能重用相同大小的 Bitmap 的内存,而 Android 4.4 及以后版本则只要后来的 Bitmap 比之前的小即可。使用 inBitmap 参数前,每创建一个 Bitmap 对象都会分配一块内存供其使用,而使用了 inBitmap 参数后,多个 Bitmap 可以复用一块内存,这样可以提高性能。

    三、计算Bitmap的大小

    3.1 Android API 的方法

    在使用 Bitmap 时经常会出现 OOM 的现象(这是多么让人心痛的错误啊),那么一张图片究竟是有多大呢?在 Bitmap 中提供了一个供我们查看 Bitmap 大小的 getByteCount() 方法:

    public final int getByteCount() {
            if (mRecycled) {
                Log.w(TAG, "Called getByteCount() on a recycle()'d bitmap! "
                        + "This is undefined behavior!");
                return 0;
            }
            // int result permits bitmaps up to 46,340 x 46,340
            return getRowBytes() * getHeight();
        }
    

    这个是 Android API所给的方法,当我们想进一步看看它是怎么实现的时候却发现 getRowBytes 调用的是 native 方法。那么我们能不能给一张在某个手机上的图片,你就知道 Bitmap 所在内存的大小呢?为了探究 Bitmap 的奥秘,我们去手动计算一张 Bitmap 的大小。

    3.2 手动计算

    下载了 Android framework 源码,Bitmap 相关的源码在文件下:frameworks\base\core\jni\android\graphics,找到 Bitmap.cpp, getRowBytes() 对应的函数为:

    static jint Bitmap_rowBytes(JNIEnv* env, jobject, jlong bitmapHandle) {
        LocalScopedBitmap bitmap(bitmapHandle);
        return static_cast<jint>(bitmap->rowBytes());
    }
    

    SkBitmap.cpp

    size_t SkBitmap::ComputeRowBytes(Config c, int width) {
        return SkColorTypeMinRowBytes(SkBitmapConfigToColorType(c), width);
    }
    

    SkImageInfo.h

    static int  SkColorTypeBytesPerPixel(SkColorType ct) {
       static const  uint8_t gSize[] = {
        0,  // Unknown
    
        1,  // Alpha_8
    
        2,  // RGB_565
    
        2,  // ARGB_4444
    
        4,  // RGBA_8888
    
        4,  // BGRA_8888
    
        1,  // kIndex_8
    
      };
      SK_COMPILE_ASSERT(SK_ARRAY_COUNT(gSize) == (size_t)(kLastEnum_SkColorType + 1),
                    size_mismatch_with_SkColorType_enum);
       SkASSERT((size_t)ct < SK_ARRAY_COUNT(gSize));
       return gSize[ct];
    }
    static inline size_t SkColorTypeMinRowBytes(SkColorType ct, int width) {
        return width * SkColorTypeBytesPerPixel(ct);
    
    }
    

    顺便提一下,Bitmap 本质上是一个 SKBitmap ,而这个 SKBitmap 也是大有来头,它来自 Skia 。这个是 Android 2D 图像引擎,而且也是 flutter 的图像引擎。我们发现 ARGB_8888(也就是我们最常用的 Bitmap 的格式)的一个像素占用 4byte,那么 rowBytes 实际上就是 4*width bytes。那么一行图片所占的内存计算公式:

    图片的占用内存 = 图片的长度(像素单位) * 图片的宽度(像素单位) * 单位像素所占字节数

    但需要注意的是, 在使用decodeResource 获得的 Bitmap 的时候,上面的计算公式并不准确。让我们来看看原因。decodeStream 会调用 native 方法 nativeDecodeStream 最终会调用BitmapFactory.cppdoDecode函数:

    static jobject doDecode(JNIEnv* env, SkStreamRewindable* stream, jobject padding, jobject options) {
        	// .....省略
            if (env->GetBooleanField(options, gOptions_scaledFieldID)) {
            	  //对应不同 dpi 的值不同,这个值跟这张图片的放置的目录有关,如 hdpi 是240;xdpi 是320;xxdpi 是480。
                const int density = env->GetIntField(options, gOptions_densityFieldID);
                //特定手机的屏幕像素密度不同,如华为p20 pro targetDensity是480
                const int targetDensity = env->GetIntField(options, gOptions_targetDensityFieldID);
                const int screenDensity = env->GetIntField(options, gOptions_screenDensityFieldID);
                if (density != 0 && targetDensity != 0 && density != screenDensity) {
                	  //缩放比例(这个是重点)
                    scale = (float) targetDensity / density;
                }
            }
        }
    	//这里这个deodingBitmap就是解码出来的bitmap,大小是图片原始的大小
    	int scaledWidth = size.width();
        int scaledHeight = size.height();
        bool willScale = false;
    
        // Apply a fine scaling step if necessary.
        if (needsFineScale(codec->getInfo().dimensions(), size, sampleSize)) {
            willScale = true;
            scaledWidth = codec->getInfo().width() / sampleSize;
            scaledHeight = codec->getInfo().height() / sampleSize;
        }
        // Scale is necessary due to density differences.
        //进行缩放后的高度和宽度
        if (scale != 1.0f) {
            willScale = true;
            scaledWidth = static_cast<int>(scaledWidth * scale + 0.5f);//①
            scaledHeight = static_cast<int>(scaledHeight * scale + 0.5f);
        }
        //.......省略
        if (willScale) {
            // This is weird so let me explain: we could use the scale parameter
            // directly, but for historical reasons this is how the corresponding
            // Dalvik code has always behaved. We simply recreate the behavior here.
            // The result is slightly different from simply using scale because of
            // the 0.5f rounding bias applied when computing the target image size
            //sx 和 sy 实际上约等于 scale ,因为在①出可以看出scaledWidth 和 scaledHeight 是由 width 和 height 乘以 scale 得到的。
            const float sx = scaledWidth / float(decodingBitmap.width());
            const float sy = scaledHeight / float(decodingBitmap.height());
    
            // Set the allocator for the outputBitmap.
            SkBitmap::Allocator* outputAllocator;
            if (javaBitmap != nullptr) {
                outputAllocator = &recyclingAllocator;
            } else {
                outputAllocator = &defaultAllocator;
            }
    
            SkColorType scaledColorType = colorTypeForScaledOutput(decodingBitmap.colorType());
            // FIXME: If the alphaType is kUnpremul and the image has alpha, the
            // colors may not be correct, since Skia does not yet support drawing
            // to/from unpremultiplied bitmaps.
            outputBitmap.setInfo(
                    bitmapInfo.makeWH(scaledWidth, scaledHeight).makeColorType(scaledColorType));
            if (!outputBitmap.tryAllocPixels(outputAllocator, NULL)) {
                // This should only fail on OOM.  The recyclingAllocator should have
                // enough memory since we check this before decoding using the
                // scaleCheckingAllocator.
                return nullObjectReturn("allocation failed for scaled bitmap");
            }
    
            SkPaint paint;
            // kSrc_Mode instructs us to overwrite the uninitialized pixels in
            // outputBitmap.  Otherwise we would blend by default, which is not
            // what we want.
            paint.setBlendMode(SkBlendMode::kSrc);
            paint.setFilterQuality(kLow_SkFilterQuality); // bilinear filtering
    
            SkCanvas canvas(outputBitmap, SkCanvas::ColorBehavior::kLegacy);
            canvas.scale(sx, sy);//canvas进行缩放
            canvas.drawBitmap(decodingBitmap, 0.0f, 0.0f, &paint);
        } else {
            outputBitmap.swap(decodingBitmap);
        }
        //.......省略
    }
    

    所以,sxsy 约等于 scale 的值,而 scale = (float) targetDensity / density;,那么我们来计算,在一张4000 * 3000 的jpg 图片,我们把它放在 drawable - xhdpi 目录下,在华为 P20 Pro 上加载,这个手机上densityDpi为 480,用 getByteCount 算出占用内存为 108000000。
    我们来手动计算:
    sx = 480/320,
    sy = 480/320,
    4000 * sx *3000 * sy * 4 = 108000000

    如果你自己算你手机上的可能和 getByteCount 不一致,那是因为精度不一样,大家可以看到上面源码 ①处,scaledWidth = static_cast(scaledWidth * scale + 0.5f); 它是这样算的,所以我们可以用:
    scaledWidth = int (480/320 *4000 + 0.5)
    scaledHeight = int (480/320 *3000 + 0.5)
    Bitmap所占内存空间为:scaledWidth * scaledHeight * 4
    所以这时Bitmap所占内存空间的方式为:

    图片的占用内存 = 缩放后图片的长度(像素单位) * 缩放后图片的宽度(像素单位) * 单位像素所占字节数

    总结:这个方法主要是让我们知道为什么同一张图片放在不同分辨率的文件下,Bitmap 所占内存空间的不同。而且这个计算方式是用 decodeResource 来得到Bitmap 的大小时,才有效。而用 decodeFiledecodeStream直接计算就行,没有缩放宽和高的整个过程。

    四、Bitmap的缩放

    4.1 质量压缩

      质量压缩不会改变图片的像素点,即我们使用完质量压缩后,在转换 Bitmap 时占用内存依旧不会减小。但是可以减少我们存储在本地文件的大小,即放到 disk上的大小。如果减少 Bitmap 加载到内存的大小,可以用采样压缩。下面是质量压缩的代码:

     /**
         * 质量压缩方法,并不能减小加载到内存时所占用内存的空间,应该是减小的所占用磁盘的空间
         * @param image
         * @param compressFormat
         * @return
         */
        public static Bitmap compressbyQuality(Bitmap image, Bitmap.CompressFormat compressFormat) {
    
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            image.compress(compressFormat, 100, baos);//质量压缩方法,这里100表示不压缩,把压缩后的数据存放到baos中
            int quality = 100;
    
            while ( baos.toByteArray().length / 1024 > 100) { //循环判断如果压缩后图片是否大于100kb,大于继续压缩
                baos.reset();//重置baos即清空baos
                if(quality > 10){
                    quality -= 20;//每次都减少20
                }else {
                    break;
                }
                image.compress(Bitmap.CompressFormat.JPEG, quality, baos);//这里压缩options%,把压缩后的数据存放到baos中
    
            }
            ByteArrayInputStream isBm = new ByteArrayInputStream(baos.toByteArray());//把压缩后的数据baos存放到ByteArrayInputStream中
    
            BitmapFactory.Options options = new BitmapFactory.Options();
            options.inPreferredConfig = Bitmap.Config.RGB_565;
            Bitmap bmp = BitmapFactory.decodeStream(isBm, null, options);//把ByteArrayInputStream数据生成图片
    
            return bmp;
        }
    

    4.2 采样压缩

    这个方法主要用在图片资源本身较大,或者适当地采样并不会影响视觉效果的条件下,这时候我们输出的目标可能相对的较小,对图片的大小和分辨率都减小。采样压缩最典型的代码如下:

    BitmapFactory.Options options = new Options();
    options.inSampleSize = 2;
    Bitmap bitmap = BitmapFactory.decodeResource(getResources(), resId, options);
    

    4.3 使用矩阵

    前面我们采用了采样压缩,Bitmap 所占用的内存是小了,可是图的尺寸也小了。当我们需要尺寸较大时该怎么办?我们要用用 Canvas 绘制怎么办?当然可以用矩阵(Matrix):

    /**
         * 矩阵缩放图片
         * @param sourceBitmap
         * @param width 要缩放到的宽度
         * @param height 要缩放到的长度
         * @return
         */
        private Bitmap getScaleBitmap(Bitmap sourceBitmap,float width,float height){
            Bitmap scaleBitmap;
            //定义矩阵对象
            Matrix matrix = new Matrix();
            float scale_x = width/sourceBitmap.getWidth();
            float scale_y = height/sourceBitmap.getHeight();
            matrix.postScale(scale_x,scale_y);
    
            try {
                scaleBitmap = Bitmap.createBitmap(sourceBitmap,0,0,sourceBitmap.getWidth(),sourceBitmap.getHeight(),matrix,true);
            }catch (OutOfMemoryError e){
                scaleBitmap = null;
                System.gc();
            }
            return scaleBitmap;
        }
    

    4.4 合理选择Bitmap的像素格式

    ARG_B8888 格式的图片,每像素占用 4 Byte,而 RGB_565 则是 2 Byte。显而易见,不同的像素格式其Bitmap 的大小也就不同。

    格式 单位像素所占字节数 描述
    ALPHA_8 1 只有一个alpha通道
    ARGB_4444 2 这个从API 13开始不建议使用,因为质量太差
    ARGB_8888 4 ARGB四个通道,每个通道8bit
    RGB_565 2 每个像素占2Byte,其中红色占5bit,绿色占6bit,蓝色占5bit

    4.5 综合优化

    下面的例子主要用到了 Bitmap 的采样压缩(这个采样率是根据需求来进行生成的),使用到了inBitmap内存复用和 inJustDecodeBounds (这两个字段上面都有介绍)
    下面介绍获取采样的流程:

    1. BitmapFactory.OptionsinJustDecodeBounds 参数设置为 true 并加装图片。
    2. BitmapFactory.Options 中取出图片的原始宽和高,它们对应于 outWidthoutHeight 参数。
    3. 根据采样率的规则并结合目标 View 的所需要大小计算出采样率 inSampleSize
    4. BitmapFactory.OptionsinJustDecodeBounds 参数设为 false ,然后重新加装图片。
    /**
         * 采样率压缩,这个和矩阵来实现缩放有点类似,但是有一个原则是“大图小用用采样,小图大用用矩阵”。
         * 也可以先用采样来压缩图片,这样内存小了,可是图的尺寸也小。如果要是用 Canvas 来绘制这张图时,再用矩阵放大
         * @param image
         * @param compressFormat
         * @param requestWidth 要求的宽度
         * @param requestHeight 要求的长度
         * @return
         */
        public static Bitmap compressbySample(Bitmap image, Bitmap.CompressFormat compressFormat, int requestWidth, int requestHeight){
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            image.compress(compressFormat, 100, baos);//质量压缩方法,这里100表示不压缩,把压缩后的数据存放到baos中
            ByteArrayInputStream isBm = new ByteArrayInputStream(baos.toByteArray());//把压缩后的数据baos存放到ByteArrayInputStream中
    
            BitmapFactory.Options options = new BitmapFactory.Options();
            options.inPreferredConfig = Bitmap.Config.RGB_565;
            options.inPurgeable = true;
            options.inJustDecodeBounds = true;//只读取图片的头信息,不去解析真是的位图
            BitmapFactory.decodeStream(isBm,null,options);
            options.inSampleSize = calculateInSampleSize(options,requestWidth,requestHeight);
            //-------------inBitmap------------------
            options.inMutable = true;
            try{
                Bitmap inBitmap = Bitmap.createBitmap(options.outWidth, options.outHeight, Bitmap.Config.RGB_565);
                if (inBitmap != null && canUseForInBitmap(inBitmap, options)) {
                    options.inBitmap = inBitmap;
                }
            }catch (OutOfMemoryError e){
                options.inBitmap = null;
                System.gc();
            }
    
            //---------------------------------------
    
            options.inJustDecodeBounds = false;//真正的解析位图
            isBm.reset();
            Bitmap compressBitmap;
            try{
                compressBitmap =  BitmapFactory.decodeStream(isBm, null, options);//把ByteArrayInputStream数据生成图片
            }catch (OutOfMemoryError e){
                compressBitmap = null;
                System.gc();
            }
    
            return compressBitmap;
        }
    
        /**
         * 采样压缩比例
         * @param options
         * @param reqWidth 要求的宽度
         * @param reqHeight 要求的长度
         * @return
         */
        private static int calculateInSampleSize(BitmapFactory.Options options, int reqWidth, int reqHeight) {
    
            int originalWidth = options.outWidth;
            int originalHeight = options.outHeight;
            
            int inSampleSize = 1;
    
            if (originalHeight > reqHeight || originalWidth > reqHeight){
                // 计算出实际宽高和目标宽高的比率
                final int heightRatio = Math.round((float) originalHeight / (float) reqHeight);
                final int widthRatio = Math.round((float) originalWidth / (float) reqWidth);
                // 选择宽和高中最小的比率作为inSampleSize的值,这样可以保证最终图片的宽和高
                // 一定都会大于等于目标的宽和高。
                inSampleSize = heightRatio < widthRatio ? heightRatio : widthRatio;
    
            }
            return inSampleSize;
        }
    

    勤能补拙是良训,一分辛苦一分才。

    站在巨人的肩膀上:
    计算bitmap占用内存大小
    BitmapFactory解析与Bitmap的内存优化
    图片基础知识梳理(3) - Bitmap&BitmapFactory 解析
    Android中BitmapFactory.Options详解

    展开全文
  • BitMap算法

    万次阅读 2017-03-19 22:05:50
    http://blog.csdn.net/pipisorry/article/details/62443757BitMapBitMap从字面的意思,很多人认为是位图,其实准确的来说,翻译成基于位的映射。在所有具有性能优化的数据结构中,大家使用最多的就是hash表,是的,...

    http://blog.csdn.net/pipisorry/article/details/62443757

    BitMap

    BitMap从字面的意思,很多人认为是位图,其实准确的来说,翻译成基于位的映射。

    在所有具有性能优化的数据结构中,大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美。但是数据量大了,内存就不够了。

    当然也可以使用类似外排序来解决问题的,由于要走IO所以时间上又不行。

    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

    其实如果你知道计数排序的话(算法导论中有一节讲过),你就会发现这个和计数排序很像。

    bitmap应用

           1)可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下。
           2)去重数据而达到压缩数据

    还可以用于爬虫系统中url去重、解决全组合问题。

    BitMap应用:排序示例

    假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)


    然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending。不过计算机一般是小端存储的,如intel。小端的话就是将倒数第5位置1),因为是从零开始的,所以要把第五位置为一(如下图):


    然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:


    然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

    bitmap排序复杂度分析

    Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。

    bitmap排序的时间复杂度不是O(N)的,而是取决于待排序数组中的最大值MAX,在实际应用上关系也不大,比如我开10个线程去读byte数组,那么复杂度为:O(Max/10)。也就是要是读取的,可以用多线程的方式去读取。时间复杂度方面也是O(Max/n),其中Max为byte[]数组的大小,n为线程大小。

    空间复杂度应该就是O(Max/8)bytes吧

    BitMap算法流程

    假设需要排序或者查找的最大数MAX=10000000(lz:这里MAX应该是最大的数而不是int数据的总数!),那么我们需要申请内存空间的大小为int a[1 + MAX/32]。

    其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推: 
    bitmap表为: 
    a[0]--------->0-31 
    a[1]--------->32-63 
    a[2]--------->64-95 
    a[3]--------->96-127 
    ..........

    我们要把一个整数N映射到Bit-Map中去,首先要确定把这个N Mapping到哪一个数组元素中去,即确定映射元素的index。我们用int类型的数组作为map的元素,这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

    1.求十进制数对应在数组a中的下标:
    先由十进制数n转换为与32的余可转化为对应在数组a中的下标。

    如十进制数0-31,都应该对应在a[0]中,比如n=24,那么 n/32=0,则24对应在数组a中的下标为0。又比如n=60,那么n/32=1,则60对应在数组a中的下标为1,同理可以计算0-N在数组a中的下标。

    i = N>>K    % 结果就是N/(2^K)

    Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。

    2.求十进制数对应数组元素a[i]在0-31中的位m:
    十进制数0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得对应0-31中的数。

    m = n & ((1 << K) - 1)      %结果就是n%(2^K)

    3.利用移位0-31使得对应第m个bit位为1

    如a[i]的第m位置1:a[i] = a[i] | (1<<m)

    如:将当前4对应的bit位置1的话,只需要1左移4位与B[0] | 即可。

    Note:  1  p+(i/8)|(0×01<<(i%8))这样也可以?

    2 同理将int型变量a的第k位清0,即a=a&~(1<<k)

    [编程珠玑]

    BitMap算法评价

    优点:
        1. 运算效率高,不进行比较和移位;
        2. 占用内存少,比如最大的数MAX=10000000;只需占用内存为MAX/8=1250000Byte=1.25M。
    缺点:
        1. 所有的数据不能重复,即不可对重复的数据进行排序。(少量重复数据查找还是可以的,用2-bitmap)。

        2. 当数据类似(1,1000,10万)只有3个数据的时候,用bitmap时间复杂度和空间复杂度相当大,只有当数据比较密集时才有优势

    BitMap算法的拓展

    Bloom filter可以看做是对bit-map的扩展。更大数据量的有一定误差的用来判断映射是否重复的算法。[Bloom Filter布隆过滤器]

    皮皮blog



    问题及应用实例

    1 使用位图法判断整形数组是否存在重复
    判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。
    位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到 5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

    2 在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数

    解法一:将bit-map扩展一下,采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

    [c++直接实现代码大数据:查找不重复的整数 ]

    或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map,都是一样的道理。

    解法二:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

    解法三:(lz)类似解法2,只是划分时按照快排partition一样划分,直到划分到每个块都可以放入内存中。

    [c实现]

    2.1 一个序列里除了一个元素,其他元素都会重复出现3次,设计一个时间复杂度与空间复杂度最低的算法,找出这个不重复的元素。


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

    8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)

    lz觉得这个是应该用计数排序类似的算法吧,而不是bitmap?

    4 给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

     解析:bitmap算法就好办多了。申请512M的内存,一个bit位代表一个unsigned int值,读入40亿个数,设置相应的bit位;读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

    Note: unsigned int最大数为2^32 - 1,所以需要2^32 - 1个位,也就是(2^32 - 1) / 8 /10 ^ 9G = 0.5G内存。

        逆向思维优化:usinged int只有接近43亿(unsigned int最大值为232-1=4294967295,最大不超过43亿),所以可以用某种方式存没有出现过的3亿个数(使用数组{大小为3亿中最大的数/8 bytes}存储),如果出现在3亿个数里面,说明不在40亿里面。3亿个数存储空间一般小于40亿个。(xx存储4294967296需要512MB, 存储294967296只需要35.16MBxx)

    5 给定一个数组a,求所有和为SUM的两个数。

    如果数组都是整数(负数也可以,将所有数据加上最小的负数x,SUM += 2x就可以了)。如a = [1,2,3,4,7,8],先求a的补数组[8,7,6,5,2,1],开辟两个数组b1,b2(最大数组长度为SUM/8/2{因为两数满足和为SUM,一个数<SUM/2,另一个数也就知道了},这样每个b数组最大内存为SUM/(8*2*1024*1024) = 128M),使用bitmap算法和数组a分别设置b1b2对应的位为1,b1b2相与就可以得到和为SUM的两个数其中一个数了。


    皮皮blog



    BitMap的实现

    Python

    lz写的一个比较好的实现

    import os, sys, array
    
    CWD = os.path.split(os.path.realpath(__file__))[0]
    sys.path.append(os.path.join(CWD, '../..'))
    
    
    def power2n(x):
        '''
        求比x大且是2n次方的数
        '''
        for i in (1, 2, 4, 8, 16, 32):  # 支持到64int型,加上64则可以支持到128等等
            x |= x >> i
        # print(x + 1)
        return x + 1
    
    
    class BitMap():
        def __init__(self):
            self.K = 5
            self.BIT_NUM = 1 << self.K
            self.BIT_TYPE = 'I'  # 32unsighed int存储位。note:可能8char存储对小数据更好一丢丢
            self.shift = 0  # 如果数组中有<0的数,则所有数都要减去最小的那个负数
    
        def fit(self, x):
            '''
            将数据读入bitmap中存储
            '''
            MIN_NUM = min(x)
            if MIN_NUM < 0:
                self.shift = -MIN_NUM  # 如果数组中有<0的数,则所有数都要减去最小的那个负数
                x = [i + self.shift for i in x]
            else:
                self.shift = 0
            MAX_NUM = max(x)
    
            num_int = power2n(MAX_NUM) >> self.K
            num_int = num_int if num_int > 0 else 1  # 至少应该有一个数组
            # print(num_int)
            self.a = array.array(self.BIT_TYPE, [0] * num_int)
            for xi in x:
                self.set(xi)
    
        def set(self, xi, value=1):
            '''
            设置数xi在数组a中对应元素对应的位为1
            '''
            array_ix = xi >> self.K  # 数组的元素位置(0开始)
            bit_ix = xi & ((1 << self.K) - 1)  # 数组元素中的bit位置(0开始),取模
            if value == 1:
                self.a[array_ix] |= 1 << bit_ix  # 对应的第bit_ix位置的2**bit_ix1
            else:
                self.a[array_ix] &= ~((1 << bit_ix))  # 对应的第bit_ix位置的2**bit_ix0
    
        def show_array(self):
            for ai in self.a:
                print('{:032b}'.format(ai))  # bin(ai)
    
        def search(self, xi):
            '''
            bitmap查找
            '''
            if self.shift != 0:
                xi += self.shift
    
            array_ix = xi >> self.K
            bit_ix = xi & ((1 << self.K) - 1)
            if (self.a[array_ix] & (1 << bit_ix)):
                flag = True
            else:
                flag = False
            return flag
    
        def sort(self):
            '''
            bitmap排序
            '''
            sorted_x = []
            for array_ix, ai in enumerate(self.a):
                for bit_ix in range(self.BIT_NUM):
                    # 首先得到该第j位的掩码(0x01<<j),将内存区中的,位和此掩码作与操作。最后判断掩码是否和处理后的结果相同
                    if (ai & (1 << bit_ix)) == (1 << bit_ix):
                        sorted_x.append(self.BIT_NUM * array_ix + bit_ix)
            # print(sorted_x)
            if self.shift != 0:
                sorted_x = [i - self.shift for i in sorted_x]
            return sorted_x
    
    
    def test():
        bm = BitMap()
        bm.fit([-3, -44, 7, 2, 5, 3, 32])
        bm.show_array()
        print(bm.search(7))
        print(bm.search(6))
        print(bm.sort())
    
    
    test()

    00000000000000000000000000000001
    00000000000010101100001000000000
    00000000000000000001000000000000
    00000000000000000000000000000000
    True
    False

    [-44, -3, 2, 3, 5, 7, 32]

    Python package[bitsets 0.7.9]

    Python 实现类似C++的bitset类:[Python 实现类似C++的bitset类 ]

    C/C++

    c++有bitset模块

    也可以自己实现:[海量数据处理算法—Bit-Map ]

    Java

    其实某些语言是对BitMap算法进行了封装的,比如java中对应BitMap的数据结构就有BitSet类。其使用方法相当简单,看看API就ok,还是给个例子吧:
    import java.util.BitSet;
    public class Test{
        public static void main(String[] args) {
            int [] array = new int [] {1,2,3,22,0,3};
            BitSet bitSet  = new BitSet(6);
            //将数组内容组bitmap
            for(int i=0;i<array.length;i++)
            {
                bitSet.set(array[i], true);
            }
           System.out.println(bitSet.size());
            System.out.println(bitSet.get(3));
        }
    }
    对应的bit位如果有对应整数那么通过bitSet.get(x)会返回true,反之false。其中x为BitMap位置下标。

    [java.util.BitSet代码实现]

    from: http://blog.csdn.net/pipisorry/article/details/62443757

    ref:  [经典算法题每日演练——第十一题 Bitmap算法]

    [经典算法系列之(一) - BitMap]


    展开全文
  • Bitmap算法简介

    千次阅读 2018-09-01 23:23:16
    Bitmap算法中文又叫做位图算法。那么什么是Bitmap算法呢? 位图算法中的位图是内存中连续的二进制位(bit),用于对大量整形数据做去重和查询。 举个例子,给定一块长度是10bit的内存空间,想要依次插入整形数据4,2...

    Bitmap算法中文又叫做位图算法。那么什么是Bitmap算法呢?

    位图算法中的位图是内存中连续的二进制位(bit),用于对大量整形数据做去重和查询。

    举个例子,给定一块长度是10bit的内存空间,想要依次插入整形数据4,2,1,3。我们需要怎么做呢?

    1. 给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。

    2. 把整型数4存入bitmap,对应存储的位置就是下标为4的位置,将此bit置为1。

    3. 把整型数2存入bitmap,对应存储的位置就是下标为2的位置,将此bit置为1。

    4. 把整型数1存入bitmap,对应存储的位置就是下标为1的位置,将此bit置为1。

    5. 把整型数3存入bitmap,对应存储的位置就是下标为3的位置,将此bit置为1。

    要问此时bitmap里存储了哪些元素?显然是4、3、2、1,一目了然。

    Bitmap不仅方便查询,还可以去除掉重复的整型数。

    虽然HashSet和HashMap也同样能实现用户的去重和统计,但是如果使用HashSet和HashMap存储的话,每一个数据比如用户ID都要存成int,占4字节即32bit。而一个用户ID在Bitmap中只占一个bit,内存节省了32倍。

    不仅如此,Bitmap在做交集和并集运算的时候也有极大的便利。我们来看看下面的例子:

    1. 如何查找使用苹果手机的程序员用户?

     2. 如何查找所有男性或者00后的用户?

    这就是Bitmap算法的另一个优势:位运算的高性能。

    那么Bitmap这种解决方案这么方便,它有什么缺点没?

    缺点也是存在的,Bitmap不支持[非运算]。比如想要查找不使用苹果手机的用户,Bitmap就无能为力了。

    现在也有一些开源的Bitmap的实现:

    Bitmap和BitSet的关系:JDK中的BitSet集合是对Bitmap相对简单的实现。

    而谷歌开发的EWAHCompressedBitmap则是一种更为优化的实现。

    EWAH的意思是Enhanced Word-Aligned Hybrid,在WAH基础上优化而来。

    Bitmap的一个缺点无法进行[非运算],为什么不能进行非运算呢?

    在统计用户标签这样的特定场景下,Bitmap无法[直接]做非运算。为什么呢?看看下面的例子:

    我们以下面的用户数据为例,用户基本信息如下。按照年龄标签,可以划分成90后、00后两个Bitmap:

    用更加形象的表示,90后用户的Bitmap如下:

    这时候可以直接求得90后的用户吗?直接进行非运算? 

    显然,非90后用户实际上只有1个,而不是图中得到的8个结果,所以不能直接进行非运算。

    那如果我们一定要求出不属于某个标签的用户数量,该怎么做呢?

    这个时候就需要借助一个全量的Bitmap。

    同样是刚才的例子,我们给定90后用户的Bitmap,再给定一个全量用户的Bitmap。最终要求出的是存在于全量用户,但又不存在于90后用户的部分。


    如何求出呢?我们可以使用异或操作,即相同位为0,不同位为1。

    Bitmap虽然使用方便,但是如果在一个很长的Bitmap里只存有一两个用户,就会很浪费空间。

    针对这个问题,在谷歌所实现的EWAHCompressedBitmap中,对Bitmap存储空间做了一定的优化。

    EWAH把Bitmap存储于long数组当中。long数组的每一个元素都可以当做是64位的二进制数,也是整个Bitmap的子集。谷歌把这些子集叫做[Word]。

    当创建一个空的Bitmap时,初始只有4个Word,也即long数组的长度是4。随着数据的不断插入,Word数量会随之扩充。

    初始情况由于还未插入任何数据,此时所有的Word值都是0。

    EWAH有些Word存储实际数据,有些Word存储数据和数据之间的间隔个数,当节点之间跨度很大时,Bitmap不会傻傻把长度扩充到Bitmap的最高位那么多,他会由一个节点专门存储两个节点之间的跨度信息,以此达到节省空间的目的。在插入新的数据的时候,如果数据不存放在已有的Word当中,EWAH还会进行动态扩充或对存储跨度的节点进行分裂。

    关于EWAH实现原理的更多信息,可以参考EWAH的算法论文:《Sorting improves word-aligned bitmap indexes》。

    EWAHCompressedBitmap对应的maven依赖如下:

    <dependency>
      <groupId>com.googlecode.javaewah</groupId>
      <artifactId>JavaEWAH</artifactId>
      <version>1.1.0</version>
    </dependency>

    关于Bitmap的基础知识就简单介绍到这里啦。

    参考:程序员小灰—《Bitmap算法 整合版》

    展开全文
  • bitMap浅析

    千次阅读 2019-03-30 13:18:38
    所谓的BitMap就是用一个bit位来标记某个元素所对应的value,而key即是该元素,由于BitMap使用了bit位来存储数据,因此可以大大节省存储空间。 举例:  这此我用一个简单的例子来详细介绍BitMap算法的原理。假设...
  • Bitmap的深入理解

    千次阅读 2016-08-22 16:50:47
    Android内存分配 Java Head(Dalvik Head),这部分的内存是由Dalvik虚拟机管理,可以通过java的new方法来分配内存;而内存的回收是符合GC Root回收规则。内存的大小受到系统限制,如果使用内存超过App最大可用内存...
  • 深入了解Bitmap源码解析及经验总结

    千次阅读 2017-03-21 21:57:10
    Bitmap的分析与使用在Android应用里,最耗费内存的就是图片资源。而且在Android系统中,读取位图Bitmap时,分给虚拟机中的图片的堆栈大小只有8M,如果超出了,就会出现OutOfMemory异常。所以,对于图片的内存优化,...
  • Bitmap 格式

    千次阅读 2014-09-02 14:14:23
    Bitmap是Windows操作系统中的标准图像文件格式,可以分成两类:设备相关位图(DDB)和设备无关位图(DIB),DDB已经就
  • bitmap算法

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

    千次阅读 2018-07-19 14:31:53
     本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性。 二、Bit-Map算法 先看看...
  • BitMap算法原理及实现实现

    千次阅读 2017-09-04 15:35:22
    bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
  • 算法系列-bitmap算法详解和实现

    千次阅读 2017-08-29 14:40:19
    1.什么是bitmap? 我们可以将bitmap看成是一种数据结构,所谓的Bit-map就是用一个(或几个)bit位来标记某个元素对应的state(value)。最基本的情况,使用1bit标示一个关键字的状态(可标示两种状态),但根据需要...
  • 大数据处理算法一:BitMap算法

    万次阅读 2015-04-29 09:57:23
     解析:bitmap算法就好办多了  所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。  例如,要判断一千万个人的状态,每个人只有两种...
  • bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 如果说了这么多还没...
  • BitMap算法和C++ STL里面的bitset

    千次阅读 2018-08-27 22:31:49
    今天看到大数据处理的BitMap算法,可以有效地对空间进行压缩。 一、BitMap基本思想 在32位的机器上,一个int需要占据32位,而有时候这就是很大的空间浪费。比如没有重复数字的计数排序的时候,假设数据范围[0,1e8]...
  • Bitmap算法

    千次阅读 2017-08-23 10:39:12
    中文:位图算法参考博客: 漫画:什么是Bitmap算法
  • bitmap算法和布隆过滤器

    千次阅读 2018-03-01 14:06:33
    bitmap算法和布隆过滤器都是用来当数据量很大时用于信息的记录和去重的,但它们有相同的地方也有不同的地方,下面就先来介绍下bitmap算法bitmap算法的思路是利用一个bit位图去记录信息是否存在,举个例子,假设你...
  • bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。  适用范围: 可进行数据的快速查找...
  • bitmap 位图算法

    千次阅读 2017-08-30 10:25:55
    bitmap 位图算法
  • Bitmap算法浅谈篇】Mysql应用Bitmap

    千次阅读 2017-09-08 18:05:07
    首先Bitmap算法并不是一种数学公式,而是一种方法! 下面通过一个列子来使你明白何为Bitmap算法!以下数据库以mysql为列! 给出一个表结构,每一行都表示一条记录! 1、要想统计所有...
  • 漫画:Bitmap算法 整合版

    千次阅读 2018-04-13 13:48:08
    转载自 玻璃猫 程序员小灰两个月之前——为满足用户标签的统计需求,小灰利用Mysql设计了如下的表结构,每一个维度的标签都对应着Mysql表的一列:要想统计所有90后的程序员该怎么做呢?用一条求交集的SQL语句即可:...
  • 1、关于bitmap   bitmap是使用bit位来存储数据的一种结构,当数据有明确的上下界时,我们可以转换到bitmap去存储,比如0~8区间的数,如果使用int来存,则需要耗费32字节大小,如果使用位来存,只需要花费1个字节...
  • 在近期的 Apache Kylin Meetup 北京站上,我们邀请到 Kyligence 大数据研发工程师陶加涛为大家揭开了大数据分析常用去重算法的神秘面纱。 △ 陶加涛 Apache Kylin 作为目前唯一一个同时支持精确与非精确...
  • BitMap的C++实现

    千次阅读 2017-02-21 20:38:28
    BitMap算法的实现 所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 我们知道,一般可以直接操控的最小的单位是...
  • BitMap从字面的意思,很多人认为是位图,其实准确的来说,翻译成基于位的映射,怎么理解呢? 举一个例子,有一个无序有界int数组{1,2,5,7},初步估计占用内存44=16字节,这倒是没什么奇怪的,但是假如有10亿个这样...
  • 上篇介绍了TopK的四种解法,其中随机选择(randomized select)最为经典,用减治法...空间换时间,是算法优化中最常见的手段,如果有相对充裕的内存,可以有更快的算法。 画外音:即使内存不够,也可以水平切分,使...
  • 算法:BitMap算法实现

    2019-08-20 16:54:57
    算法介绍: Bit-Map算法具有效率高,节省空间的特点,适用于对大量数据进行去重,查询等。 花了一个小时实现了一下 只要定义一下bitmap_type和BitMap_User的结构体就可以使用了 bitmap功能的实现如下: #...
  • FastBit是位图索引技术的集大成者,是一系列高级位图索引技术的集合。
  • 大量数据去重:Bitmap和布隆过滤器(Bloom Filter)

    万次阅读 多人点赞 2017-02-27 17:46:27
    5TB的硬盘上放满了数据,请写一个算法将这些数据进行排重。如果这些数据是一些32bit大小的数据该如何解决?...介绍两个算法,对于空间的利用到达了一种极致,那就是Bitmap和布隆过滤器(Bloom Filter)。
  • 漫画BitMap在用户画像的应用

    千次阅读 2017-08-29 23:30:55
    两个月之前—— ...为满足用户标签的统计需求,小灰利用Mysql设计了如下的表结构,每一个维度的标签都对应着Mysql表的一列: ...要想统计所有90后的程序员该怎

空空如也

1 2 3 4 5 ... 20
收藏数 290,699
精华内容 116,279
关键字:

bitmap