Python: 实现bitmap数据结构

发布时间：2019-08-28 09:16:08编辑：auto阅读（2280）


    http://my.oschina.net/goal/blog/200347 

    bitmap是很常用的数据结构，比如用于Bloom Filter中、用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。对于Python来说，整数类型默认是有符号类型，所以一个整数的可用位数为31位。

    bitmap实现思路

    bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。

    上图所示为一个32位整型，在Python中默认是有符号类型，最高位为符号位，bitmap不能使用它。左边是高位，右边是低位，最低位为第0位。

    初始化bitmap

    首先需要初始化bitmap。拿90这个整数来说，因为单个整型只能使用31位，所以90除以31并向上取整则可得知需要几个数组元素。代码如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size = int((max + 31 - 1) / 31) #向上取整
     
    if __name__ == '__main__':
        bitmap = Bitmap(90)
        print '需要 %d 个元素。' % bitmap.size

    ?
    1
    2
    $ python bitmap.py
    需要 3 个元素。

    计算索引

    确定了数组大小后，也就可以创建这个数组了。如果要将一个整数保存进这个数组，首先需要知道保存在这个数组的第几个元素之上，然后要知道是在这个元素的第几位上。因此计算索引分为：

    1. 计算在数组中的索引

    2. 计算在数组元素中的位索引

    计算在数组中的索引

    计算在数组中的索引其实是跟之前计算数组大小是一样的。只不过之前是对最大数计算，现在换成任一需要存储的整数。但是有一点不同，计算在数组中的索引是向下取整，所以需要修改calcElemIndex方法的实现。代码改为如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size  = self.calcElemIndex(max, True)
            self.array = [0 for i in range(self.size)]
     
        def calcElemIndex(self, num, up=False):
            '''up为True则为向上取整, 否则为向下取整'''
            if up:
                return int((num + 31 - 1) / 31) #向上取整
            return num / 31
     
    if __name__ == '__main__':
        bitmap = Bitmap(90)
        print '数组需要 %d 个元素。' % bitmap.size
        print '47 应存储在第 %d 个数组元素上。' % bitmap.calcElemIndex(47)

    ?
    1
    2
    3
    $ python bitmap.py
    数组需要 3 个元素。
    47 应存储在第 1 个数组元素上。

    所以获取最大整数很重要，否则有可能创建的数组容纳不下某些数据。

    计算在数组元素中的位索引

    数组元素中的位索引可以通过取模运算来得到。令需存储的整数跟31取模即可得到位索引。代码改为如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size  = self.calcElemIndex(max, True)
            self.array = [0 for i in range(self.size)]
     
        def calcElemIndex(self, num, up=False):
            '''up为True则为向上取整, 否则为向下取整'''
            if up:
                return int((num + 31 - 1) / 31) #向上取整
            return num / 31
     
        def calcBitIndex(self, num):
            return num % 31
     
    if __name__ == '__main__':
        bitmap = Bitmap(90)
        print '数组需要 %d 个元素。' % bitmap.size
        print '47 应存储在第 %d 个数组元素上。' % bitmap.calcElemIndex(47)
        print '47 应存储在第 %d 个数组元素的第 %d 位上。' % (bitmap.calcElemIndex(47), bitmap.calcBitIndex(47),)

    ?
    1
    2
    3
    4
    $ python bitmap.py
    数组需要 3 个元素。
    47 应存储在第 1 个数组元素上。
    47 应存储在第 1 个数组元素的第 16 位上。

    别忘了是从第0位算起哦。

    置1操作

    二进制位默认是0，将某位置1则表示在此位存储了数据。代码改为如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size  = self.calcElemIndex(max, True)
            self.array = [0 for i in range(self.size)]
     
        def calcElemIndex(self, num, up=False):
            '''up为True则为向上取整, 否则为向下取整'''
            if up:
                return int((num + 31 - 1) / 31) #向上取整
            return num / 31
     
        def calcBitIndex(self, num):
            return num % 31
     
        def set(self, num):
            elemIndex = self.calcElemIndex(num)
            byteIndex = self.calcBitIndex(num)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem | (1 << byteIndex)
     
    if __name__ == '__main__':
        bitmap = Bitmap(90)
        bitmap.set(0)
        print bitmap.array

    ?
    1
    2
    $ python bitmap.py
    [1, 0, 0]

    因为从第0位算起，所以如需要存储0，则需要把第0位置1。

    清0操作

    将某位置0，也即丢弃已存储的数据。代码如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size  = self.calcElemIndex(max, True)
            self.array = [0 for i in range(self.size)]
     
        def calcElemIndex(self, num, up=False):
            '''up为True则为向上取整, 否则为向下取整'''
            if up:
                return int((num + 31 - 1) / 31) #向上取整
            return num / 31
     
        def calcBitIndex(self, num):
            return num % 31
     
        def set(self, num):
            elemIndex = self.calcElemIndex(num)
            byteIndex = self.calcBitIndex(num)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem | (1 << byteIndex)
     
        def clean(self, i):
            elemIndex = self.calcElemIndex(i)
            byteIndex = self.calcBitIndex(i)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem & (~(1 << byteIndex))
     
    if __name__ == '__main__':
        bitmap = Bitmap(87)
        bitmap.set(0)
        bitmap.set(34)
        print bitmap.array
        bitmap.clean(0)
        print bitmap.array
        bitmap.clean(34)
        print bitmap.array

    ?
    1
    2
    3
    4
    $ python bitmap.py
    [1, 8, 0]
    [0, 8, 0]
    [0, 0, 0]

    清0和置1是互反操作。

    测试某位是否为1

    判断某位是否为1是为了取出之前所存储的数据。代码如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size  = self.calcElemIndex(max, True)
            self.array = [0 for i in range(self.size)]
     
        def calcElemIndex(self, num, up=False):
            '''up为True则为向上取整, 否则为向下取整'''
            if up:
                return int((num + 31 - 1) / 31) #向上取整
            return num / 31
     
        def calcBitIndex(self, num):
            return num % 31
     
        def set(self, num):
            elemIndex = self.calcElemIndex(num)
            byteIndex = self.calcBitIndex(num)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem | (1 << byteIndex)
     
        def clean(self, i):
            elemIndex = self.calcElemIndex(i)
            byteIndex = self.calcBitIndex(i)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem & (~(1 << byteIndex))
     
        def test(self, i):
            elemIndex = self.calcElemIndex(i)
            byteIndex = self.calcBitIndex(i)
            if self.array[elemIndex] & (1 << byteIndex):
                return True
            return False
     
    if __name__ == '__main__':
        bitmap = Bitmap(90)
        bitmap.set(0)
        print bitmap.array
        print bitmap.test(0)
        bitmap.set(1)
        print bitmap.test(1)
        print bitmap.test(2)
        bitmap.clean(1)
        print bitmap.test(1)

    ?
    1
    2
    3
    4
    5
    6
    $ python bitmap.py
    [1, 0, 0]
    True
    True
    False
    False

    接下来实现一个不重复数组的排序。已知一个无序非负整数数组的最大元素为879，请对其自然排序。代码如下：

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #!/usr/bin/env python
    #coding: utf8
     
    class Bitmap(object):
        def __init__(self, max):
            self.size  = self.calcElemIndex(max, True)
            self.array = [0 for i in range(self.size)]
     
        def calcElemIndex(self, num, up=False):
            '''up为True则为向上取整, 否则为向下取整'''
            if up:
                return int((num + 31 - 1) / 31) #向上取整
            return num / 31
     
        def calcBitIndex(self, num):
            return num % 31
     
        def set(self, num):
            elemIndex = self.calcElemIndex(num)
            byteIndex = self.calcBitIndex(num)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem | (1 << byteIndex)
     
        def clean(self, i):
            elemIndex = self.calcElemIndex(i)
            byteIndex = self.calcBitIndex(i)
            elem      = self.array[elemIndex]
            self.array[elemIndex] = elem & (~(1 << byteIndex))
     
        def test(self, i):
            elemIndex = self.calcElemIndex(i)
            byteIndex = self.calcBitIndex(i)
            if self.array[elemIndex] & (1 << byteIndex):
                return True
            return False
     
    if __name__ == '__main__':
        MAX = 879
        suffle_array = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
        result       = []
        bitmap = Bitmap(MAX)
        for num in suffle_array:
            bitmap.set(num)
         
        for i in range(MAX + 1):
            if bitmap.test(i):
                result.append(i)
     
        print '原始数组为:    %s' % suffle_array
        print '排序后的数组为: %s' % result

    ?
    1
    2
    3
    $ python bitmap.py
    原始数组为：   [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
    排序后的数组为：[0, 2, 35, 45, 46, 67, 78, 90, 123, 340, 879]

    结束语

    bitmap实现了，则利用其进行排序就非常简单了。其它语言也同样可以实现bitmap，但对于静态类型语言来说，比如C/Golang这样的语言，因为可以直接声明无符号整型，所以可用位就变成32位，只需将上述代码中的31改成32即可，这点请大家注意。


关键字：

上一篇： 在Python中定义和使用 抽象类及抽象

下一篇： LibSVM for Python 使用