计算并集和交集的编程方法的官方名称是什么
我在想要同时计算两个集合（用列表存储）的并集、交集和差集时，肯定是重新发明了这个“轮子”。最初的代码（虽然不是最简洁的）是：
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等。这样，某个位置的位（bit）就表示这个元素是否属于某个集合。
这个方法可以扩展到最多32个集合，使用一个32位的整数，或者用位数组（bitarray）或字符串来表示任意数量的集合。你只需要先计算好这个字典，然后就可以用非常快速的O(n)查询来提取你感兴趣的元素。例如，所有的1表示所有集合的交集，而所有的0是一个特殊情况——这种情况不会出现。
总之，我并不是想自夸，这个方法肯定在我之前就有人发明过，并且有个名字。这个方法叫什么呢？在数据库中有没有用到这种方法？
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]}
而且你恰好是用位向量来表示这些整数数组。
原始的数据结构（列表的列表）让你可以方便地遍历给定列表的所有值。而反转后的数据结构（字典的列表）则让你可以轻松找到包含某个特定值的所有列表。
用一个N位的整数来表示N个布尔值，这是一种叫做完美哈希表的数据结构的特例。注意到你在想要使用位集的想法中，明确使用了字典（这是一种通用的哈希表）。它之所以叫哈希表，是因为你用哈希值来查找一个值，而之所以叫完美，是因为你从来不会遇到冲突。这个特例是因为表格的存储和打包方式。
接下来，制定哈希函数，看看它与数组有什么不同：
int bitset_hash(int n) {
// domain of this function is only non-negative ints
return 1 << n;
}
注意到bitset_hash(3)的结果是0b1000，这对应于使用C语言整数和位运算时的第4个项目（偏移量/索引为3）。(由于存储实现的细节，位运算也用于操作哈希中的特定项目。)
将这种方法扩展到使用位与、位或、位异或进行集合操作是常见的，不需要其他特别的名称，除了“集合操作”，或者如果你需要一个流行词，可以叫“集合理论”。
最后，这里还有一个在素数筛选法中的另一个示例（我在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
是的，有时候在数据库中会用到，比如PostgreSQL。维基百科上提到：
一些不提供持久位图索引的数据库系统，会在内部使用位图来加快查询处理。例如，PostgreSQL 8.1及以后的版本实现了一种“位图索引扫描”的优化，目的是加速在单个表上进行复杂逻辑操作时对可用索引的处理。