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}，并且我想查看关联的值(value)。我必须将我的集合强制设置为 freezeset 才能在字典中查找它并检索值'panda'。因此，如果我通过 given.add(2) 添加回元素，恢复原始的 {1, 2, 3}，我将再次强制转换为 freezeset在从字典中检索 banana 之前。

我觉得必须强制转换为 freezeset 是一个 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.

它与给定的大小成线性关系，而不是与字典的大小成线性关系。为了进行比较，哈希值与给定的大小也是线性的，因此即使您不必构造卡住集，您仍然具有相同的渐近复杂度。

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