5

我需要一个使用标识 ( is) 比较的集合，add()而不是值 ( ==) 比较。

例如，我定义了一个Point类（具有不可变的 x/y），它钩子__eq__和__hash__. Points 正确比较自己，Point具有相同 x/y 值的两个实例True回答==和。我需要将两个这样的实例添加到我的集合中，重要的是结果包含两个实例，即使它们的 x/y 值相同。一些 Smalltalks 正是为此目的定义了 IdentitySet。Falseis

例如，我想知道是否可以修补内置的 set 类以包含identityAdd和identityRemove方法。这可能会奏效，但它似乎是一个黑客。

有没有更好的办法？

4

3 回答 3

8

这是一个基于id -> object地图的实现（由@nmclean建议）和collections.MutableSet：

from collections import MutableSet

class IdentitySet(MutableSet):
    key = id  # should return a hashable object

    def __init__(self, iterable=()):
        self.map = {} # id -> object
        self |= iterable  # add elements from iterable to the set (union)

    def __len__(self):  # Sized
        return len(self.map)

    def __iter__(self):  # Iterable
        return self.map.itervalues()

    def __contains__(self, x):  # Container
        return self.key(x) in self.map

    def add(self, value):  # MutableSet
        """Add an element."""
        self.map[self.key(value)] = value

    def discard(self, value):  # MutableSet
        """Remove an element.  Do not raise an exception if absent."""
        self.map.pop(self.key(value), None)

    def __repr__(self):
        if not self:
            return '%s()' % (self.__class__.__name__,)
        return '%s(%r)' % (self.__class__.__name__, list(self))

例子：

a = (1, 2)
print IdentitySet([a, (1, 2), a])
# -> IdentitySet([(1, 2), (1, 2)]) # only one instance of `a`

print s != Set([a, (1, 2), a])  # it might be unequal because new literal
                                # tuple (1, 2) might have a different id
print s | Set([a, (1, 2), a])
# -> IdentitySet([(1, 2), (1, 2), (1, 2)]) # `a` plus two tuples from literals

MutableSet自动提供方法：clear, pop, remove, __ior__, __iand__, __ixor__, __isub__, __le__, __lt__, __eq__, __ne__, __gt__, __ge__, __and__, __or__, __sub__, __xor__, 和isdisjoint.

在这里，与set基于 in 的实现不同，复合操作总是使用覆盖的基本方法，例如|( self.__or__(), union) 是根据 来实现的self.add()，因此它提供了正确的IdentitySet语义。

于 2013-06-11T08:31:07.087 回答
4

您可以将 Point 对象包装在可以比较其身份的东西中。

class Ref(object):
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return self.value is other.value

    def __hash__(self):
        return id(self.value)

这是一个IdentitySet将其元素包装在Ref对象中的实现：

from collections import MutableSet

class IdentitySet(MutableSet):
    def __init__(self, items = []):
        self.refs = set(map(Ref, items))

    def __contains__(self, elem):
        return Ref(elem) in self.refs

    def __iter__(self):
        return (ref.value for ref in self.refs)

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

    def add(self, elem):
        self.refs.add(Ref(elem))

    def discard(self, elem):
        self.refs.discard(Ref(elem))

    def __repr__(self):
        return "%s(%s)" % (type(self).__name__, list(self))
于 2013-06-08T00:05:38.237 回答
1

好吧，我不知道这是否是最好的方法，但是 id => object 的字典怎么样？IE：

def insert_object(obj):
    id_dict[id(obj)] = obj

def contains_object(obj):
    return id_dict.has_key(id(obj))

id返回真实身份（内存地址），因此比较它本质上等同于is.

但是，你不能只更新你的 eq / hash 方法真的有充分的理由吗？

编辑- 这是一个将其与@tom 的set子类方法相结合的想法：

class IdentitySet(set):
    def __init__(self, items = []):
        set.__init__(self)
        self._identitydict = {}
        for item in items:
            self.add(item)

    def __contains__(self, elem):
        return set.__contains__(self, id(elem))

    def __iter__(self):
        for identity in set.__iter__(self):
            yield self._identitydict[identity]

    def add(self, elem):
        identity = id(elem)
        set.add(self, identity)
        self._identitydict[identity] = elem

    def discard(self, elem):
        if elem in self:
            self.remove(elem)

    def pop(self):
        return self._identitydict.pop(set.pop(self))

    def remove(self, elem):
        identity = id(elem)
        set.remove(self, identity)
        del self._identitydict[identity]

该集合包含 id，并且 id 被复制为映射到对象的字典键。它基本上是相同的方法，除了@tom 将输入包装在 a 中Ref并id用作Ref' 的哈希，而我只是直接将输入包装在id. 如果没有中间类，它可能会更有效。

于 2013-06-08T00:13:16.007 回答