首页 > 代码库 > 位图bitbucket

位图bitbucket

2024-07-12 09:26:33   212人阅读

问题：假设有500w条数据，数据是在2^32-1的范围内，数据重复，如何减少内存对数字进行统计呢？

　　如果用字典来标记数字是否已经统计过来，数字做为key, value仅为０ or１,那么这样需要消耗

内存32*500w+32*500w,key和value占用内存相加。

　　但如果我们用value的位来标记数据是否统计过，32bit可以存３２个不同的数字，这样可以减少

为500w/32+500w/32.这就是bit bucket的魅力所在。

#!/usr/bin/env python#-*- coding:utf-8 -*-SHIFT = 5  # 如果计算机为32位,SHIFT为5;如果计算机为64位,SHIFT为6MASK = 0x1F  # 如果计算机为32位,MASK为0x1F;如果计算机为64位,MASK为0x3Fclass BitBucket(object):    def __init__(self):        self._unique_key_count = 0   # 唯一的key有多少个        self._total_key_count = 0    # 加入的key有多少个        self._bit = {}

    def set(self, value):        """return last bit"""        self._total_key_count += 1        if not self._has_key(value):            self._unique_key_count += 1            key = value >> SHIFT            self._bit[key] = self._bit.get(key, 0) | (1 << (value & MASK))            return 0        return 1    def exist(self, value):        if self._has_key(value):            return True        return False    def clear(self, value):        if self._has_key(value):            self._unique_key_count -= 1            self._total_key_count -= 1            key = value >> SHIFT            self._bit[key] = self._bit[key] & (~(1 << (value & MASK)))            return True        return False    def get_total_count(self):        return self._total_key_count    def get_bit_count(self):        return self._unique_key_count    def _has_key(self, value):        key = value >> SHIFT        return self._bit.get(key, 0) & (1 << (value & MASK))if __name__ == ‘__main__‘:    bitBucket = BitBucket()    for i in range(1, 27):        bitBucket.set(i)    print bitBucket.get_total_count()     print bitBucket.get_bit_count()    count = 0    for i in range(1, 30):        if bitBucket.exist(i):            count += 1    assert count == bitBucket.get_bit_count()


联系
我们