6

可能重复:
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_items因为它等同于它的一个项目,但它是一个不同的对象。

我想要的是item1s给定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)
4

2 回答 2

12

那么,不要使用 a set。只需使用dict将一些值映射到自身的 a 。在您的情况下,它映射:

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

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

PS我希望我能正确理解你的问题的意图。如果不是,请澄清一下。

于 2012-04-30T12:45:13.000 回答
2

如果您绝对需要 O(1) 查找对象标识(不仅仅是相等)快速集合操作(​​无需在每次想要执行集合操作时创建新集合),那么一种相当简单的方法是同时使用adict和一个set。您必须维护两个结构以使它们保持同步,但这将允许您保持 O(1) 访问(只是具有更大的常数因子)。(也许这就是您在编辑中使用“现在非常不完整的未来解决方案”的目标。)

但是,您没有提到您正在使用的数据量,或者您遇到的性能问题(如果有的话)。所以我不相信你真的需要这样做。可能是dict通过按需set创建或set线性查找已经足够快了。

于 2012-04-30T14:27:00.360 回答