前言

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

什么是BitMap

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

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

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

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

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

BitMap儲(chǔ)存方式

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

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

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

在BitMap思想中使用bit來(lái)儲(chǔ)存每一個(gè)值。如果要儲(chǔ)存相同的數(shù)字，那么在BitMap中這些數(shù)字會(huì)被儲(chǔ)存在同一個(gè)位置，這樣就會(huì)導(dǎo)致數(shù)據(jù)重復(fù)，無(wú)法達(dá)到去重的目的。因此，BitMap不能儲(chǔ)存相同的數(shù)字，利用這個(gè)特性，BitMap可以對(duì)大數(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

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

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

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

最新評(píng)論