python数据结构之bitmap-Ttr

shuaiwei588

#_*_coding=utf-8_*_　　
'''常见数据结构-bitmap（位图）'''
　　

　　
class Bitmap:
　　
    '''初始化'''
　　
    def __init__(self,max):
　　
        '''#计算需要多少个数组的数量'''
　　
        self.size = int((max + 31-1) / 31)
　　
        '''为每个数组生成单元，每个单元存储为0'''
　　
        self.array = [0 for i in range(self.size)]
　　

　　
    def bitindex(self,num):
　　
        '''位索引，这个方法求余的操作就是判断某个数在某个数组中的具体的第几位'''
　　
        return  num % 31
　　

　　
    def set(self,num):
　　
        '''计算到某个数对应在位图中的哪个数之后，需要将对应的位置成1'''
　　

　　
        '''#判断需要计算的数字具体是在哪个数组中'''
　　
        elemindex = num / 31
　　
        '''#表示计算数的位索引'''
　　
        byteindex = self.bitindex(num)
　　
        '''#选择哪个数组进行操作'''
　　
        elem = self.array[elemindex]
　　

　　
         #逻辑或，进行置1的操作，1向左移动了byteindex位
　　
        self.array[elemindex] = elem | (1 << byteindex)
　　

　　
    def test(self,i):
　　
        '''#判断对应的数字在第几个数组上'''
　　
        elemindex = i / 31
　　
        '''#进行位索引'''
　　
        byteindex = self.bitindex(i)
　　
        '''#逻辑与操作，判断某一位到底在不在bitmap上，如果在就代表着应该取出并遍历出来，遍历的时候出现1的位置就将这个位置上的数转换为十进制然后取出来，依次遍历生成排序序列'''
　　
        if self.array[elemindex] & (1 << byteindex):
　　
            return True
　　
        return False
　　

　　
if __name__ == "__main__":
　　
    '''将z转换为assci码最大的数'''
　　
    MAX = ord('z')
　　
    suffle_array = [x for x in 'coledraw']
　　
    result = []
　　
    '''#调用这个类，将最大数的传递给它。生成位图表'''
　　
    bitmap = Bitmap(int(MAX))
　　

　　
    '''分别遍历这个数组'''
　　
    for c in suffle_array:
　　
        bitmap.set(ord(c))
　　
    for i in range(int(MAX) + 1):
　　
        '''#存在1的话，就取出数据'''
　　
        if bitmap.test(i):
　　
            '''#存储到列表里'''
　　
            result.append(chr(i))
　　

　　
    print("原始数组: %s" % suffle_array)
　　
    print("排序后数组: %s" % result)