python BitMap實作

假設有20億個int類型不重複非負數的數字，而我們隻有4G的記憶體空間，如何将其排序？

一個int類型資料占據4個Byte，而1個Byte占據8個bit位。20億個int大概需要7.45GB的記憶體。那麼4G的空間是決計不夠的

我們可以用1bit來存儲一個int的目的，隻要周遊一下這個bitmap，就可以自然地得到數字序列的排序。并且理論上它所占用的空間隻有原來的1/32，20億個數字，現在隻需要230MB左右即可實作。

python 中的int 是有符号的，是以隻支援31 個數

class BitMap():
    def __init__(self, maxValue):
        self._size = int((maxValue + 31 - 1) / 31)  # 向上取正  确定數組大小
        self.array = [0 for i in range(self._size)]  # 初始化為0

    def getElemIndex(self, num):  # 擷取該數的數組下标
        return num // 31

    def getBitIndex(self, num):  # 擷取該數所在數組的位下标
        return num % 31

    def set(self, num):  # 将該數所在的位置1
        elemIndex = self.getElemIndex(num)
        bitIndex = self.getBitIndex(num)
        self.array[elemIndex] = self.array[elemIndex] | (1 << bitIndex)

    def find(self, num):  # 查找該數是否存在
        elemIndex = self.getElemIndex(num)
        bitIndex = self.getBitIndex(num)
        if self.array[elemIndex] & (1 << bitIndex):
            return True
        return False


if __name__ == '__main__':

    array_list = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
    results = []
    bitmap = BitMap(maxValue=max(array_list))
    for num in array_list:
        bitmap.set(num)

    for i in range(max(array_list) + 1):
        if bitmap.find(i):
            results.append(i)

    print(array_list)
    print(results)

           

結果：
原始資料 [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
排序後資料 [0, 2, 35, 45, 46, 67, 78, 90, 123, 340, 879]