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

Question

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

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

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

{
    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，以便在字典中查找它并检索值 'panda'。因此，如果我通过 given.add(2) 添加回元素，恢复原来的 {1, 2, 3}，在从字典中检索 banana 之前，我将再次强制转换为 frozenset。

我觉得必须强制执行 frozenset 是一个 O(n) 操作，它违背了 O(1) 查找的目的。

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

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

Answer 1

I feel like having to coercing to a frozenset is an O(n) operation that defeats the purpose of an O(1) lookup.

它与 given 的大小成线性关系，与 dict 的大小无关。相比之下，散列的大小也是线性的 given，因此即使您不必构造 frozenset，您仍然具有相同的渐近复杂度。

如果这个成本对你来说太贵了，你可以尝试编写你自己的集合包装器 class 使用允许增量更新的散列函数，并打破可散列对象不可变的通常条件影响它们的哈希值。我个人使用基于 Zobrist hashing 的方案取得了很好的效果，其中集合的元素被分配了随机生成的哈希码，该哈希码在程序的生命周期内持续存在，并且集合的哈希是所有元素的异或元素哈希。添加或删除元素时，可以通过与元素的哈希值进行异或来更新集合的哈希值。

Answer 2

基于 user2357112 的回答。未测试，因为我失去了兴趣。

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 是 serie 中的元素数，优于 word 中的元素数。以下添加和删除操作是直接的并且成本为 O(1).

因为根据https://wiki.python.org/moin/TimeComplexity，删除系列中的元素可能会花费一些。也许直接调用 get_indices 会更好。

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

Python efficient lookup structure for dynamic subsets?

python

dictionary

set

immutability