python - 这种计算并集和交集的编程方法的正式名称

Question

当我想同时计算两个集合(存储为列表)的并集、交集和差集时，我 [surely re] 发明了这个 [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 位整数推广到最多 32 个集合，或者使用位数组或字符串推广到任意数量的集合。所以，你预先计算这个字典一次，然后使用非常快的 O(n) 查询来提取感兴趣的元素。例如，全 1 表示所有集合的交集。全 0 是一个特殊的 - 不会出现。

无论如何，这不是自鸣得意。这肯定是以前发明的并且有名字。这叫什么？这种方法是否在某处的数据库中使用？

Answer 1

使用 N 位整数来表示 N 个 bool 值是数据结构的一个特例，称为完美哈希表。请注意，在促使您考虑位集的想法中，您明确地使用了字典(这是一般的哈希表)。它是一个散列表，因为您使用散列来查找值，而且它是完美的，因为您永远不会发生冲突。特殊情况是因为表的打包和存储方式。

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

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)。 (由于存储实现细节，位运算也用于操作哈希中的特定项。)

扩展使用按位与/-或/-xor 进行集合运算的方法是 common ，并且不需要任何特殊名称，除了“集合操作”或者，如果你需要一个流行语，“集合论”。

最后，这是在 prime sieve 中使用它的另一个示例(我在 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