我正在寻找在 Python 中表示给定范围(比如 0-10)中的小整数集的最有效方法。在这种情况下，效率意味着快速构建(从一个未排序的列表)、快速查询(每个集合上的几个查询)，以及合理快速构建排序版本(可能每十个集合一次左右)。先验候选人正在使用 Python 的内置集合类型(快速查询)，使用排序数组(可能构造速度更快？)，或使用位数组(如果我在 C 中，一切都很快......但我怀疑 Python 会是那个高效(？))。有什么选择的建议吗？
谢谢。
请您参考如下方法:
我会使用位图并将“集合”的成员存储在 int 中……这实际上可能比内置的 set 类型更快在这种情况下——尽管我还没有测试过。它肯定需要更少的存储空间。
更新
我现在没有时间做一个完整的类实现并根据 Python 的内置类对其进行基准测试，但我认为这是一个可以说明我的建议的工作示例。正如我认为您会同意的那样，代码看起来相当快并且内存效率很高。
鉴于 Python 几乎透明的“无限”长整数功能，所编写的内容将自动处理比您需要的范围大得多的整数值，尽管这样做可能会减慢速度。 ;)
class BitSet(object):
def __init__(self, *bitlist):
self._bitmap = 0
for bitnum in bitlist:
self._bitmap |= (1 << bitnum)
def add(self, bitnum):
self._bitmap |= (1 << bitnum)
def remove(self, bitnum):
if self._bitmap & (1 << bitnum):
self._bitmap &= ~(1 << bitnum)
else:
raise KeyError
def discard(self, bitnum):
self._bitmap &= ~(1 << bitnum)
def clear(self):
self._bitmap = 0
def __contains__(self, bitnum):
return bool(self._bitmap & (1 << bitnum))
def __int__(self):
return self._bitmap
if __name__ == '__main__':
bs = BitSet()
print '28 in bs:', 28 in bs
print 'bs.add(28)'
bs.add(28)
print '28 in bs:', 28 in bs
print
print '5 in bs:', 5 in bs
print 'bs.add(5)'
bs.add(5)
print '5 in bs:', 5 in bs
print
print 'bs.remove(28)'
bs.remove(28)
print '28 in bs:', 28 in bs
