前言

對于大量的隨機(jī)整數(shù)，如何做到去重？BitMap是個很不錯的選擇，本篇文章就帶大家認(rèn)識BitMap的奇妙之處

什么是BitMap

BitMap的基本原理是用一個 bit 來標(biāo)記某個元素對應(yīng)的 Value，而 Key 即是該元素。由于采用一 個bit 來存儲一個數(shù)據(jù)，因此可以大大的節(jié)省空間。

普通數(shù)據(jù)儲存

我們知道，當(dāng)我們隨意向計(jì)算機(jī)輸入一個數(shù)字，這個數(shù)字絕對不是以其本身的數(shù)值形式儲存在計(jì)算機(jī)內(nèi)存中的，而儲存形式就是二進(jìn)制。

比如我們輸入8，那么計(jì)算機(jī)中會儲存為1000。每種計(jì)算機(jī)中的字符的最小儲存單位就是字節(jié)，一個字節(jié)有8位，所以至少也是00001000。也正因此一個字節(jié)最大能儲存11111111這個二進(jìn)制數(shù)值（代表255）。這樣看一個字節(jié)絕對不夠用啊，所以一般還需要更多的字節(jié)來儲存大一點(diǎn)的數(shù)字。

在每種編程語言中所用于儲存數(shù)字的字節(jié)數(shù)可能不同，在Python3版本中int類型是動態(tài)長度的，因此理論可以存非常大的數(shù)字了。

BitMap儲存方式

BitMap的作用是為了達(dá)到數(shù)據(jù)去重或者儲存，那么肯定是將要存儲的東西變得越少越好，在BitMap思想中使用bit來儲存每一個值。一起來看下面這張圖：

上圖只畫了四個位，可以看到框內(nèi)的是分別的四個位，四個位上有的地方為1，有的地方為0，之后這幾個位綜合起來形成一個我們熟知的十進(jìn)制數(shù)值。這個十進(jìn)制數(shù)值就儲存著BitMap儲存的數(shù)值。比如上面的5可以存儲1,3兩個數(shù)，15可以存儲1,2,3,4這幾個數(shù)。這下懂了吧，實(shí)際上就是在哪個位上有一個1就是代表這里存儲了一個數(shù)字，這就是BitMap儲存數(shù)據(jù)的原理

為什么BitMap可以對大數(shù)據(jù)進(jìn)行去重

在BitMap思想中使用bit來儲存每一個值。如果要儲存相同的數(shù)字，那么在BitMap中這些數(shù)字會被儲存在同一個位置，這樣就會導(dǎo)致數(shù)據(jù)重復(fù)，無法達(dá)到去重的目的。因此，BitMap不能儲存相同的數(shù)字，利用這個特性，BitMap可以對大數(shù)據(jù)進(jìn)行去重。

下面是使用Python實(shí)現(xiàn)最基礎(chǔ)的BitMap算法的代碼：

import array
class BitMap:
    def __init__(self, max_num):
        self.max_num = max_num
        self.arr = array.array('B', [0] * (max_num // 8 + 1))
    def set(self, num):
        index = num // 8
        bit = num % 8
        self.arr[index] |= 1 << bit
    def get(self, num):
        index = num // 8
        bit = num % 8
        return self.arr[index] & (1 << bit) != 0
    def remove_duplicates(self, nums):
        for num in nums:
            if self.get(num):
                continue
            self.set(num)
            yield num

這個類中，我們定義了三個方法：__init__、set和get。__init__方法初始化了一個數(shù)組，用于存儲BitMap的數(shù)據(jù)。set方法用于設(shè)置某個數(shù)字的狀態(tài)，get方法用于獲取某個數(shù)字的狀態(tài)。remove_duplicates方法用于對數(shù)據(jù)進(jìn)行去重。這里我們使用了Python中的array庫來直接操作bit數(shù)組。

這是一個最基礎(chǔ)的BitMap算法的實(shí)現(xiàn)，如果您想要更深入地了解BitMap算法，可以參考其他更高級的實(shí)現(xiàn)方式。

更多關(guān)于python BitMap算法去重的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論