8

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

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 是一个特殊的 - 不会发生。

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

4

4 回答 4

7

使用 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 进行集合运算的方法很常见，并且不需要任何特殊名称，除了“集合运算”，或者，如果您需要一个流行词，“集合论”。

最后，这是在素筛中使用它的另一个示例（我在 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
于 2010-01-06T01:55:01.237 回答
4

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

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

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

于 2010-01-06T02:03:27.977 回答
2

使用整数来表示一组小整数是很常见的；它通常被称为bitset或bitvector。在这里，您使用整数来表示“包含此值的输入序列集”。

你正在做的操作让我想起了反转 multimap。

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

[["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]}

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

原始数据结构（列表列表）使迭代给定列表的所有值变得容易。反向数据结构（列表字典）可以很容易地找到所有具有给定值的列表。

于 2010-01-06T00:27:50.353 回答
1

位域的想法是您正在寻找的吗？... 字段的每一点（因为没有更好的词）都代表一个标志。在这种情况下，您的标志是集合 N 中的成员。

编辑 - 我想我误解了你指的是哪个想法。漠视？

于 2010-01-06T00:25:42.260 回答