计算并集和交集的编程方法的正式名称

Question

当我想同时计算两个集合（存储为列表）的并集、交集和差异时，我[当然是重新]发明了这个[轮子]。初始代码（不是最严格的）：

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 个集合，或者使用位数组或字符串可以推广到任意数量的集合。因此，您预先计算该字典一次，然后使用非常快的 O(n) 查询来提取感兴趣的元素。例如，全 1 表示所有集合的交集。全 0 是一种特殊的 - 不会发生。

无论如何，这并不是我自吹自擂。这肯定是以前发明的并且有一个名字。它叫什么？这种方法是否在数据库中使用过？

Answer 1

使用 N 位整数来表示 N 个布尔值是称为完美哈希表的数据结构的一种特殊情况。请注意，您在提示您考虑位集的想法中明确使用了字典（它们是通用哈希表）。它是一个哈希表，因为您使用哈希来查找值，并且它是完美的，因为您永远不会发生冲突。特殊情况是由表的打包和存储方式决定的。

制定哈希函数，这显示了它与数组的不同之处：

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 进行集合运算是 常见，并且不需要除“设置操作”之外的任何特殊名称，或者，如果您需要流行语，“集合论”。

最后，这是在 prime sieve 中使用它的另一个示例（我已在欧拉项目解决方案）：

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）

Answer 3

使用整数来表示一组小整数是很常见的；它通常称为位集或位向量。这里您使用一个整数来表示“包含该值的输入序列集”。

你所做的操作让我想起了反转多重地图。

在您的情况下，输入是列表的列表：

[["a", "b"], ["a", "c", "d"]]

但是您可以将其视为一袋有序对，如下所示：

0, "a"
0, "b"
1, "a"
1, "c"
1, "d"

您只需构建一个包含反转对的表，

"a", 0
"b", 0
"a", 1
"c", 1
"d", 1

如下所示：

{"a": [0, 1],
 "b": [0],
 "c": [1],
 "d": [1]}

并且您碰巧使用位向量表示这些整数数组。

原始数据结构（列表的列表）可以轻松迭代给定列表的所有值。反向数据结构（列表字典）可以轻松查找具有给定值的所有列表。