Python中的IdentitySet？

Question

我需要一个使用identity(is)比较的集合,add()而不是value(==)比较.

例如,我已经定义了一个Point挂钩__eq__和类的类(具有不可变的x/y)__hash__.Point小号正确地比较自己和两个实例Point使用相同的X/Y值的答案True来==和False到is.我需要在我的集合中添加两个这样的实例,重要的是结果包含两个实例,即使它们的x/y值相同.一些Smalltalks为此目的定义了IdentitySet.

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

有没有更好的办法？

Answer 1

这是基于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基于实现的实现不同,复合操作总是使用重写的基本方法,例如,|(self.__or__(),union)是根据语义实现的self.add(),因此它提供了IdentitySet语义的正确性.

Answer 2

您可以将 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))