Python 데이터 구조 구현 Bitmap

Bitmap
bitmap 는 Bloom Filter 에서 자주 사용 되 는 데이터 구조 입 니 다.반복 되 지 않 는 정수 정렬 등에 사용 합 니 다.bitmap 는 보통 배열 을 바탕 으로 이 루어 집 니 다. 배열 의 모든 요 소 는 일련의 바 이 너 리 로 볼 수 있 고 모든 요 소 는 더 큰 바 이 너 리 집합 을 구성 합 니 다.
Bitmap 의 정의
bitmap 는 Bloom Filter 에서 자주 사용 되 는 데이터 구조 입 니 다.반복 되 지 않 는 정수 정렬 등에 사용 합 니 다.bitmap 는 보통 배열 을 바탕 으로 이 루어 집 니 다. 배열 의 모든 요 소 는 일련의 바 이 너 리 로 볼 수 있 고 모든 요 소 는 더 큰 바 이 너 리 집합 을 구성 합 니 다.쉽게 말 하면 이런 데이터 구조 저장 소 는 원래 의 수 를 바 이 너 리 저장 으로 바 꾸 고 모든 사람 이 하나의 저장 부 를 차지 하 며 우 리 는 bimap 중의 데 이 터 를 조작 하면 한 자 리 를 조작 하 는 것 과 같다.Python 에 있어 서 정수 유형 은 기본적으로 기호 유형 이 있 기 때문에 하나의 정수 가 사용 할 수 있 는 자릿수 는 31 비트 입 니 다.
Bitmap 동작
만약 우리 가 특정한 자릿수 를 조작 하려 면 먼저 배열 의 몇 번 째 요 소 를 가 져 온 다음 에 해당 하 는 비트 색인 을 가 져 온 다음 에 작업 을 실행 해 야 합 니 다.작업 과정 은 크게 bitmap 초기 화, 배열 에 있 는 색인 계산, 배열 에 있 는 비트 색인 계산, 관련 위치 1, 테스트 관련 위치 로 나 뉜 다.
비트 맵 초기 화
bitmap 를 초기 화 하 는 것 은 필요 한 배열 의 크기 를 계산 하 는 것 입 니 다. 보통 최대 수 를 위로 올 리 는 방법 을 사용 합 니 다. 최대 수 를 저장 하 는 배열 을 찾 을 수 있다 면 다른 수 는 문제 가 되 지 않 습 니 다.

class Bitmap():
    def __init__(self,max):
    self.size = int ((max + 31 - 1) / 31) #max             

배열 에 계 산 된 색인
배열 에 계 산 된 색인 은 btimap 를 초기 화 하 는 것 과 달리 아래로 조정 하 는 방법 을 사용 합 니 다. 다른 것 은 같 습 니 다.
배열 에 있 는 비트 인덱스 를 계산 합 니 다.
배열 요소 의 비트 인덱스 는 모드 연산 을 통 해 얻 을 수 있 습 니 다.저장 해 야 할 정수 와 31 모드 를 취하 면 비트 색인 을 얻 을 수 있 습 니 다.

def bitindex(self,num):
    return num % 31

관련 위치
바 이 너 리 는 기본적으로 0 이 고, 어떤 위치 1 은 이 자리 에 데 이 터 를 저장 했다 는 것 을 표시 합 니 다.

def set_1(self,num):
    elemindex = num / 31
    byteindex = self.bitindex(num)
    ele = self.array[elemindex]
    self.array[elemindex] = ele | (1 << byteindex)

테스트 관련 비트
어떤 분 이 1 인지 아 닌 지 를 판단 하 는 것 은 이전에 저 장 된 데 이 터 를 꺼 내기 위해 서 입 니 다.

def test_1(self,i):
    elemindex = i / 31
    byteindex = self.bitindex(i)
    if self.array[elemindex] & (1 << byteindex):
        return True
    return False

소스 코드

# -*- encoding:utf-8 -*-
class Bitmap():
    def __init__(self,max):
        '        '
        self.size = int ((max + 31 - 1) / 31)
        self.array = [0 for i in range(self.size)]

    def bitindex(self,num):
        '           '
        return num % 31

    def set_1(self,num):
        '        1'
        elemindex = num / 31
        byteindex = self.bitindex(num)
        ele = self.array[elemindex]
        self.array[elemindex] = ele | (1 << byteindex)

    def test_1(self,i):
        '         '
        elemindex = i / 31
        byteindex = self.bitindex(i)
        if self.array[elemindex] & (1 << byteindex):
            return True
        return False
if __name__ == '__main__':
    Max = ord('z')
    suffle_array = [x for x in 'qwelmfg']
    result = []
    bitmap = Bitmap(Max)
    for c in suffle_array:
        bitmap.set_1(ord(c))
    for i in range(Max+1):
        if bitmap.test_1(i):
            result.append(chr(i))
    print u'     :    %s' % suffle_array
    print u'       : %s' % result