Python高效的动态子集查找结构

Question

我正在尝试对与某个给定集合的子集相关联的值进行恒定时间查找，其中顺序是不保证的。

我将积极处理原始集合，删除/添加回元素，并希望在执行过程中查找其余元素的相关值。

例如，如果我给定的集合是given = {1, 2, 3}，也许我会构建一个dict，看起来像这样。。。

{
    frozenset([]): 'apple',
    frozenset([1]): 'orange',
    frozenset([2]): 'ice bear',
    frozenset([3]): 'peach',
    frozenset([1, 2]): 'grizzly',
    frozenset([2, 3]): 'pear',
    frozenset([1, 3]): 'panda',
    frozenset([1, 2, 3]): 'banana',
}

假设我通过given.remove(2)从给定集合中移除一个元素，剩下{1, 3}，并且我想查看相关的值。我必须将我的集合强制为frozenset，以便在dict中查找它并检索值'panda'。因此，如果我通过given.add(2)添加回元素，恢复原始的{1, 2, 3}，那么在从dict中检索banana之前，我将不得不再次强制使用frozenset

我觉得必须强制到frozenset是一种O（n）运算，它违背了O（1）查找的目的。

有没有一种方法可以在Python中更有效地实现这种查找？或者有什么数据结构可以帮助我吗？

我使用的是Py2.7，但如果Py3对此更好，请告诉我。谢谢

Answer 1

我觉得必须强制到frozenset是一种O（n）运算，它违背了O（1）查找的目的。

它在given的大小上是线性的，而不是在dict的大小上。相比之下，哈希在given的大小上也是线性的，所以即使你不必构造frozenset，你仍然会有同样的渐近复杂度。

如果这种成本对您来说太高，您可以尝试使用允许增量更新的哈希函数编写自己的集合包装器类，并打破可哈希对象不能以影响其哈希值的方式更改的通常条件。我个人在一个基于Zobrist哈希的方案中取得了很好的结果，其中集合的元素被分配为随机生成的哈希码，这些哈希码在程序的整个生命周期内持续存在，集合的哈希是所有元素哈希的XOR。当添加或删除元素时，可以通过将其与元素的哈希进行异或来更新集合的哈希。

Answer 2

基于用户2357112的回答。没有测试，因为我失去了兴趣。

from random import Random
class FastRehashableSet(set):
    _initial_hash = 12345
    def __init__(self, seq=()):
        super(FastRehashableSet, self).__init__(seq)
        self._hash = self._initial_hash
        for x in seq:
            self._hash_single_value(x)
    def _hash_single_value(self, val):
        # Introduce extra randomness since the intended elements are ints
        # which just return themselves when hashed
        self._hash ^= Random(hash(val)).randrange(4294967296)
    def __hash__(self):
        return self._hash
    def add(self, elem):
        super(FastRehashableSet, self).add(elem)
        self._hash_single_value(elem)
    def remove(self, elem):
        super(FastRehashableSet, self).remove(elem)
        self._hash_single_value(elem)
    def discard(self, elem):
        change = elem in self
        super(FastRehashableSet, self).discard(elem)
        if change:
            self._hash_single_value(elem)
    def pop(self):
        val = super(FastRehashableSet, self).pop()
        self._hash_single_value(val)
        return val
    def clear(self):
        super(FastRehashableSet, self).clear()
        self._hash = self._initial_hash
    # You get the idea, I'm not doing these
    def update(self):
        raise NotImplemented
    def intersection_update(self):
        raise NotImplemented
    def difference_update(self):
        raise NotImplemented
    def symmetric_difference_update(self):
        raise NotImplemented

Answer 3

将元素列表中的单词标记用二进制编码：

words = ["apple","orange","ice bear","peach","grizzly","panda","pear","banana"]
def get_indice(L):
    return sum(2**(i-1) for i in L)
# initial serie of elements
serie = [1,2,3]
# first computation of indice
ind = get_indice([1,2,3])
print serie,words[ind]
# remove the 2
val = 2
serie.remove(val)
ind -= 2**(val-1)
print serie,words[ind]
# add the 2
val = 2
serie.append(val)
serie = sorted(serie)
ind += 2**(val-1)
print serie,words[ind]

输出：

[1, 2, 3] banana
[1, 3] panda
[1, 2, 3] banana

注意，第一次计算花费N次运算，其中N是级数中的元素数量，这比单词中的元素数要好。下面的添加和删除操作是直接的，成本为O（1）。

根据https://wiki.python.org/moin/TimeComplexity。也许直接调用get_indices更好。