python数据结构之bitmap，python六种数据结构,#_*_coding

python数据结构之bitmap，python六种数据结构,#_*_coding

#_*_coding=utf-8_*_‘‘‘常见数据结构-bitmap（位图）‘‘‘classBitmap:‘‘‘初始化‘‘‘def__init__(self,max):‘‘‘#计算需要多少个数组的数量‘‘‘self.size=int((max+31-1)/31)‘‘‘为每个数组生成单元，每个单元存储为0‘‘‘self.array=[0foriinrange(self.size)]defbitindex(self,num):‘‘‘位索引，这个方法求余的操作就是判断某个数在某个数组中的具体的第几位‘‘‘returnnum%31defset(self,num):‘‘‘计算到某个数对应在位图中的哪个数之后，需要将对应的位置成1‘‘‘‘‘‘#判断需要计算的数字具体是在哪个数组中‘‘‘elemindex=num/31‘‘‘#表示计算数的位索引‘‘‘byteindex=self.bitindex(num)‘‘‘#选择哪个数组进行操作‘‘‘elem=self.array[elemindex]#逻辑或，进行置1的操作，1向左移动了byteindex位self.array[elemindex]=elem|(1<<byteindex)deftest(self,i):‘‘‘#判断对应的数字在第几个数组上‘‘‘elemindex=i/31‘‘‘#进行位索引‘‘‘byteindex=self.bitindex(i)‘‘‘#逻辑与操作，判断某一位到底在不在bitmap上，如果在就代表着应该取出并遍历出来，遍历的时候出现1的位置就将这个位置上的数转换为十进制然后取出来，依次遍历生成排序序列‘‘‘ifself.array[elemindex]&(1<<byteindex):returnTruereturnFalseif__name__=="__main__":‘‘‘将z转换为assci码最大的数‘‘‘MAX=ord(‘z‘)suffle_array=[xforxin‘coledraw‘]result=[]‘‘‘#调用这个类，将最大数的传递给它。生成位图表‘‘‘bitmap=Bitmap(int(MAX))‘‘‘分别遍历这个数组‘‘‘forcinsuffle_array:bitmap.set(ord(c))foriinrange(int(MAX)+1):‘‘‘#存在1的话，就取出数据‘‘‘ifbitmap.test(i):‘‘‘#存储到列表里‘‘‘result.append(chr(i))print("原始数组:%s"%suffle_array)print("排序后数组:%s"%result)

本文出自 “运维杂谈Q群：223843163” 博客，请务必保留此出处http://freshair.blog.51cto.com/8272891/1896331

python数据结构之bitmap