计算联合和交集的这种编程方法的官方名称

Question

当我想要同时计算两个集合(存储为列表)的并集和交集以及差异时,我[当然重新]发明了这个[wheel].初始代码(不是最严格的):

dct = {}
for a in lst1:
  dct[a] = 1
for b in lst2:
  if b in dct:
    dct[b] -= 1
  else:
    dct[b] = -1

union = [k for k in dct]
inter = [k for k in dct if dct[k] == 0]
oneminustwo = [k for k in dct if dct[k] ==  1]
twominusone = [k for k in dct if dct[k] ==  -1]

然后我意识到我应该使用00,01,10和11而不是-1,1,0,......所以,位置n处的位表示集合n中的成员资格.

这可以使用32位int推广到最多32个集合,或使用bitarray或字符串推广到任意数量的集合.因此,您预先计算此字典一次,然后使用非常快速的O(n)查询来提取感兴趣的元素.例如,所有1都表示所有集合的交集.所有0都是特殊的 - 不会发生.

无论如何,这不是为了自己的号角.这肯定是以前发明的并且有一个名字.这叫什么？这种方法是在数据库中使用的吗？

Answer 1

使用N位整数来表示N个布尔值是数据结构的一种特殊情况,称为完美哈希表.请注意,您在提示您考虑位集的想法中明确使用了dicts(通用哈希表).它是一个哈希表,因为你使用哈希来找到一个值,它是完美的,因为你从来没有碰撞.特殊情况是因为表的打包和存储方式.

制定散列函数,它显示它与数组的不同之处:

int bitset_hash(int n) {
  // domain of this function is only non-negative ints
  return 1 << n;
}

注意bitset_hash(3)是0b1000,对应于使用C int和按位运算时的第4项(偏移/索引3).(由于存储实现细节,按位操作也用于操作散列中的特定项.)

扩展使用bitwise-and/-or/-xor进行集合操作的方法很常见,并且除了"set operations"之外不需要任何特殊名称,或者如果你需要一个流行语,则需要"set theory".

最后,这是在筛子中使用它的另一个例子(我在Project Euler解决方案中使用了这个代码):

class Sieve(object):
  def __init__(self, stop):
    self.stop = stop
    self.data = [0] * (stop // 32 // 2 + 1)
    self.len = 1 if stop >= 2 else 0
    for n in xrange(3, stop, 2):
      if self[n]:
        self.len += 1
        for n2 in xrange(n * 3, stop, n * 2):
          self[n2] = False

  def __getitem__(self, idx):
    assert idx >= 2
    if idx % 2 == 0:
      return idx == 2
    int_n, bit_n = divmod(idx // 2, 32)
    return not bool(self.data[int_n] & (1 << bit_n))

  def __setitem__(self, idx, value):
    assert idx >= 2 and idx % 2 != 0
    assert value is False
    int_n, bit_n = divmod(idx // 2, 32)
    self.data[int_n] |= (1 << bit_n)

  def __len__(self):
    return self.len

  def __iter__(self):
    yield 2
    for n in xrange(3, self.stop, 2):
      if self[n]:
        yield n

Answer 2

是的，它有时用在数据库中，例如 PostgreSQL。正如维基百科提到的：

一些不提供持久位图索引的数据库系统在内部使用位图来加速查询处理。例如，PostgreSQL 8.1 及更高版本实现了“位图索引扫描”优化，以加速单个表上的可用索引之间的任意复杂的逻辑操作。

（来自http://en.wikipedia.org/wiki/Bitmap_index）