有没有一种方法可以在O(1)时间内从集合中获取一个项目？

Question

考虑以下代码：

可能是重复问题：
Python：从集合中检索项目

请看下面的代码：

>>> item1 = (1,)
>>> item2 = (2,)
>>> s = set([item1, item2])
>>> s
set([(2,), (1,)])
>>> new_item = (1,)
>>> new_item in s
True
>>> new_item == item1
True
>>> new_item is item1
False

所以new_item在s中，因为它等价于其中一个项目，但它是另一个对象。

我想要从s中得到item1，已知new_item在s中。

我想到的一个解决方案很直接，但不太有效:

def get_item(s, new_item):
    for item in s:
        if item == new_item:
            return item

>>> get_item(s, new_item) is new_item
False
>>> get_item(s, new_item) is item1
True

另一种解决方案看起来更有效，但实际上并不起作用：

 def get_item_using_intersection1(s, new_item):
     return set([new_item]).intersection(s).pop()

不是这个：

 def get_item_using_intersection2(s, new_item):
     return s.intersection(set([new_item])).pop()

由于交集的工作方式未定义：

>>> get_item_using_intersection1(s, new_item) is new_item
True
>>> get_item_using_intersection1(s, new_item) is item1
False

>>> get_item_using_intersection2(s, new_item) is new_item
True
>>> get_item_using_intersection2(s, new_item) is item1
False

如果有关系的话，我正在使用Windows 7上的Python 2.7 x64，但我需要一个跨平台的解决方案。

---

感谢大家，我想出了以下临时解决方案：

class SearchableSet(set):

    def find(self, item):
        for e in self:
            if e == item:
                return e

这将来会被以下解决方案所取代（目前非常不完整）：

class SearchableSet(object):

    def __init__(self, iterable=None):
        self.__data = {}
        if iterable is not None:
            for e in iterable:
                self.__data[e] = e

    def __iter__(self):
        return iter(self.__data)

    def __len__(self):
        return len(self.__data)

    def __sub__(self, other):
        return SearchableSet(set(self).__sub__(set(other)))

    def add(self, item):
        if not item in self:
            self.__data[item] = item

    def find(self, item):
        return self.__data.get(item)

- utapyngo

---

但是... 你提出的“低效解决方案”已经是线性的了。 - kennytm

为什么不直接使用new_item，如果它与item1等效呢？（在这种情况下应该是这样的。）如果实际上这些项并不等价，则存在设计问题：您不应将这些对象存储在集合中，就好像它们是一样的。（从你提供的一般性问题描述中很难判断。） - millimoose

如果你的类实现了__hash__和__eq__方法，并且两个相等的实例不可互换，那么我认为这是一个设计缺陷。在非“值对象”中实现这些方法并不是一个好主意。 - millimoose

我查看了交集的C源代码。它检查哪个集合更小（自身或参数），并迭代地使用“in”检查每个元素与另一个集合。所以，是的，它的时间复杂度为O(min(n1, n2))。结果集是从较小的集合构建的，因此您的代码始终从pop()返回new_item，因为您的临时集合只有1个元素，而s有2个。您应该像其他人建议的那样使用dict。 - yak

只是一个问题。为什么你现在这么担心效率？你的应用程序真的很慢吗？你已经对它进行了分析，并发现设置操作是主要瓶颈吗？ - Pedro Werneck

Answer 1

那就不要使用 set 了。只需使用将某个值映射到其本身的 dict。在您的情况下，它映射为：

d[item1] = item1
d[item2] = item2

所以任何等于item1的东西都会在d中被找到，但值是item1本身。这比线性时间好得多 ;-)

P.S. 我希望我正确理解了你问题的意图。如果没有，请澄清一下。

- Eli Bendersky

---

谢谢。我知道可以使用dict，但我也知道从技术上讲，仍然可以使用set（假设有一种内部方法可以通过哈希查找项）。此外，我不想重写我的旧代码，因为我密集地使用了集合操作。 - utapyngo

如果代码错误，最好重新编写。 set 简单地不是为此设计的 - 使用更合适的数据结构。 - Eli Bendersky

如何在线性时间内执行这些字典的交集、并集和差集操作？ - utapyngo

@utapyngo：既然你可以在O(n)的时间内遍历一个字典，并在O(1)的时间内检查另一个字典中的成员资格，那么这会有什么问题呢？唯一真正的问题是，这些操作将比集合慢得多，因为Python解释器中的集合并/交等操作是在C级别上实现的。 - Eli Bendersky

@utapyngo：另一个可能的方向是，如果您需要这样的解决方案表现良好，请考虑编写从set派生并保留所需信息的C扩展类型，以便可以有效地访问它。 - Eli Bendersky

Answer 2

如果你需要 O(1) 的查找，以及对象标识（而不仅仅是相等性）和快速集合操作（无需每次都创建新的集合），那么一个相当直接的方法是同时使用 dict 和 set 两个结构。需要同时维护这两个结构以保持同步，但这将允许您保持 O(1) 访问（只是带有更大的常数因子）。 （也许这就是您在编辑中提到的“未来解决方案”，目前非常不完整的内容。）

然而，你没有提到你正在处理的数据量或者你是否遇到了任何性能问题，所以我并不确定你真正需要这样做。可能已经足够快的是根据需要创建 set 的 dict，或者具有线性查找的 set。

- John Y