现在的位置: 主页 > 主打产品 > 文章正文

[从头学数学] 第253节 Python实现数据结构:比特集(Bi

作者:成都渝祥金属丝网制品有限公司 来源:www.cdyuxiang.com 未知发布时间:2018-04-01 22:51:00
[从头学数学] 第253节 Python实现数据结构:比特集(BitSet) 剧情提要:
阿伟看到了一本比较有趣的书,是关于《计算几何》的,2008年由北清派出版。很好奇
它里面讲了些什么,就来看看啦。


正剧开始:
星历2016年08月01日 10:17:09, 银河系厄尔斯星球中华帝国江南行省。

[工程师阿伟]正在和[机器小伟]一起研究[计算几何]]。

\

\

Python的实现:

### # @usage 比特集 # @author mw # @date 2016年08月01日 星期一 08:06:58 # @param # @return # ### class BitSet(object): # from low to high "00000001 00000010 00000011", the array is [1, 2, 3] def __init__(self, capacity = 64): #"B"类型相当于 C 语言的 unsigned char, 即占用1byte(8位),所以size大小设置为8 self.unit_size = 8 self.unit_count = abs(math.floor((capacity + self.unit_size - 1) / self.unit_size)); self.capacity = capacity self.arr = array.array("B", [0] * self.unit_count) def any(self): #是否存在置为 1 的位 for a in self.arr: if a != 0: return True return False def all(self): #是否所有位都为 1, 即是否存在置为 0 的位 t = (1 << self.unit_size) - 1 for a in self.arr: if (a & t) != t: return False return True def none(self): #是否所有位都为 0,即是否不存在置为 1 的位 for a in self.arr: if a != 0: return False return True #所有位为零为真 def isEmpty(self): return self.none(); #至少一位为1,返回真 def intersects(self): return self.any(); #位的数量 def length(): return self.size(); def __len__(): return self.size(); def size(self): #所有位的个数 return self.unit_count * self.unit_size def count(self): #置为 1 的位的个数 c = 0 for a in self.arr: while a > 0: if a & 1: c += 1 a = a>>1 return c def get(self, pos): #获取第 pos 位的值 index = int(pos / self.unit_size) offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size return (self.arr[index] >> offset) & 1 #寻找下一个零位 def nextClearBit(self, startIndex = 0): for i in range(startIndex+1, self.size()): if self.get(i) == 0: return i; return -1; #寻找下一个非零位 def nextSetBit(self, startIndex = 0): for i in range(startIndex+1, self.size()): if self.get(i) == 1: return i; return -1; def test(self, pos): #判断第 pos 位的值是否为 1 if self.get(pos): return True return False def set(self, pos=-1): #设置第 pos 位的值为 1,若 pos 为 -1, 则所有位都置为 1 if pos >= 0: index = int(pos / self.unit_size) offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size self.arr[index] = (self.arr[index]) | (1 << offset) else: t = (1 << self.unit_size) - 1 for i in range(self.unit_count): self.arr[i] = self.arr[i] | t def reset(self, pos=-1): #设置第 pos 位的值为 0,若 pos 为 -1, 则所有位都置为 0 if pos >= 0: index = int(pos / self.unit_size) offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size x = (1 << offset) self.arr[index] = (self.arr[index]) & (~x) else: for i in range(self.unit_count): self.arr[i] = 0 #所有位清零 def clear(self): self.reset(-1); # def __getitem__(self, idx): if idx < 0 or idx >= self.size(): raise IndexError("index out of range."); return self.get(idx); def __setitem__(self, idx, val): if idx < 0 or idx >= self.size(): raise IndexError("index out of range."); if (val == 0): self.reset(idx); elif(val == 1): self.set(idx); #非操作 def flip(self, pos=-1): #把第 pos 位的值取反,若 pos 为 -1, 则所有位都取反 if pos >= 0: if self.get(pos): self.reset(pos) else: self.set(pos) else: for i in range(self.unit_count): self.arr[i] = ~self.arr[i] + (1 << self.unit_size) #两个bitset的按位与操作 def andOp(self, otherbit): if type(self) != type(otherbit): raise TypeError("and Op undefined for " + str(type(self)) + " + " + str(type(other))) size_1 = self.size(); size_2 = otherbit.size(); minsize = min(size_1, size_2); #如果比特集是从高位到低位排列,而操作应该是低位对齐 #所以应该是逆序迭代,但这种方式在两个比特集位数不等时会有问题 #所以还是默认比特集是小头序,即低字节先读取 #这样这个类设置数据时就是默认把低位设满 for i in range(minsize): a = self.get(i); b = otherbit.get(i); if (a & b == 1): self.set(i); else: self.reset(i); #两个bitset的按位或操作 def orOp(self, otherbit): if type(self) != type(otherbit): raise TypeError("or Op undefined for " + str(type(self)) + " + " + str(type(other))) size_1 = self.size(); size_2 = otherbit.size(); minsize = min(size_1, size_2); #如果比特集是从高位到低位排列,而操作应该是低位对齐 #所以应该是逆序迭代,但这种方式在两个比特集位数不等时会有问题 #所以还是默认比特集是小头序,即低字节先读取 #这样这个类设置数据时就是默认把低位设满 for i in range(minsize): a = self.get(i); b = otherbit.get(i); if (a | b == 1): self.set(i); else: self.reset(i); #两个bitset的按位异或操作 def xorOp(self, otherbit): if type(self) != type(otherbit): raise TypeError("xor Op undefined for " + str(type(self)) + " + " + str(type(other))) size_1 = self.size(); size_2 = otherbit.size(); minsize = min(size_1, size_2); #如果比特集是从高位到低位排列,而操作应该是低位对齐 #所以应该是逆序迭代,但这种方式在两个比特集位数不等时会有问题 #所以还是默认比特集是小头序,即低字节先读取 #这样这个类设置数据时就是默认把低位设满 for i in range(minsize): a = self.get(i); b = otherbit.get(i); if (a != b): self.set(i); else: self.reset(i); #浅拷贝,重复调用BitSet中对象 def clone(self, otherbit): self.unit_size = otherbit.unit_size; self.unit_count = otherbit.unit_count; self.capacity = otherbit.capacity; self.arr = otherbit.arr; #比特集信息显示 def binstr(self): b = "" for a in self.arr: t = bin(a) b += "0" * (self.unit_size - len(t) + 2) + t + "," return "[" + b.replace("0b", "").strip(",") + "]" def show(self): return self.arr #类对象的hash码 def hashCode(self): #return hash(str(self.show())); return hash(self);

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:新洲网站建设 http://www.xzwzjs.com.cn

上一篇:ASP.NET MVC中Action返回值类型 下一篇:最后一页