集合操作中对象的行为

Question

我正在尝试创建一个自定义对象，希望它在集合操作中表现得正常。

我大致上已经搞定了，但我想确保我完全理解其中的含义。特别是，我对对象中有额外数据但没有包含在相等或哈希方法中的情况很感兴趣。看起来在“交集”操作中，它返回的是被比较的对象集合，而在“并集”操作中，它返回的是比较的对象集合。

举个例子：

class MyObject:
    def __init__(self,value,meta):
        self.value = value
        self.meta = meta
    def __eq__(self,other):
        return self.value == other.value
    def __hash__(self):
        return hash(self.value)

a = MyObject('1','left')
b = MyObject('1','right')
c = MyObject('2','left')
d = MyObject('2','right')
e = MyObject('3','left')
print a == b # True
print a == c # False

for i in set([a,c,e]).intersection(set([b,d])):
    print "%s %s" % (i.value,i.meta)
#returns:
#1 right
#2 right

 for i in set([a,c,e]).union(set([b,d])):
    print "%s %s" % (i.value,i.meta)
#returns:
#1 left
#3 left
#2 left

这种行为有没有什么文档说明，或者是确定的？如果有的话，背后的原则是什么？

Answer 1

假设你的对象有两种不同类型的属性：关键属性和数据属性。在你的例子中，MyObject.value就是一个关键属性。

把所有的对象存储在一个字典里，字典的键就是这些关键属性的值。确保只有你想要的对象（比如说时间戳最早的那个）被放进这个字典里。进行集合操作时，使用和字典中相同的键，然后从字典中取出实际的对象：

result= [dict1[k] for k in set_operation_result]

Answer 2

顺序似乎并不重要：

>>> [ (u.value, u.meta) for u in set([b,d]).intersection(set([a,c,e])) ]
[('1', 'right'), ('2', 'right')]

>>> [ (u.value, u.meta) for u in set([a,c,e]).intersection(set([b,d])) ]
[('1', 'right'), ('2', 'right')]

但是，如果你这样做：

>>> f = MyObject('3', 'right')

并且把 f 加入到“右边”的集合中：

>>> [ (u.value, u.meta) for u in set([a,c,e]).intersection(set([b,d,f])) ]
[('1', 'right'), ('3', 'right'), ('2', 'right')]

>>> [ (u.value, u.meta) for u in set([b,d,f]).intersection(set([a,c,e])) ]
[('1', 'left'), ('3', 'left'), ('2', 'left')]

所以你可以看到，行为取决于集合的大小（如果你使用 union，也会出现同样的效果）。这可能还与其他因素有关。如果你想知道原因，可能需要查看一下 Python 的源代码。

Answer 3

不，这个问题不是确定性的。问题在于你破坏了相等性和哈希值之间的关系，也就是说两个对象在被认为相等时应该是等价的。你需要修正你的对象，不要试图聪明地利用集合的实现方式。如果某个元值是 MyObject 的身份的一部分，它应该包含在相等性和哈希值的计算中。

你不能指望集合的交集会遵循任何顺序，所以没有简单的方法来实现你想要的效果。你最终会做的是仅通过值来获取交集，然后在所有对象中查找一个较旧的对象来替换它，针对每一个对象都要这样做。没有什么好的算法可以做到这一点。

并集就没那么糟糕：

##fix the eq and hash to work correctly
class MyObject:
    def __init__(self,value,meta):
        self.value = value
        self.meta = meta
    def __eq__(self,other):
        return self.value, self.meta == other.value, other.meta
    def __hash__(self):
        return hash((self.value, self.meta))
    def __repr__(self):
        return "%s %s" % (self.value,self.meta)

a = MyObject('1','left')
b = MyObject('1','right')
c = MyObject('2','left')
d = MyObject('2','right')
e = MyObject('3','left')

union =  set([a,c,e]).union(set([b,d]))
print union
#set([2 left, 2 right, 1 left, 3 left, 1 right])

##sort the objects, so that older objs come before the newer equivalents
sl = sorted(union, key= lambda x: (x.value, x.meta) )
print sl
#[1 left, 1 right, 2 left, 2 right, 3 left]
import itertools
##group the objects by value, groupby needs the objs to be in order to do this
filtered = itertools.groupby(sl, lambda x: x.value)
##make a list of the oldest (first in group)
oldest = [ next(group) for key, group in filtered]
print oldest
#[1 left, 2 left, 3 left]