最有效的方式找出不在两个列表中的对象

Question

我正在做一个模块，需要检查两个列表中是否有对象缺失。这个模块是用Python写的。

先来看一个简单的对象定义：

class Foo(object):

  def __init__(self, attr_one=None, attr_two=None):
    self.attr_one = attr_one
    self.attr_two = attr_two

  def __eq__(self, other):
    return self.attr_one == other.attr_one and self.attr_two == other.attr_two

我有两个独立的列表，每个列表可以包含多个Foo类的实例，具体如下：

list1 = [Foo('abc', 2), Foo('bcd', 3), Foo('cde', 4)]
list2 = [Foo('abc', 2), Foo('bcd', 4), Foo('efg', 5)]

我需要找出在一个列表中存在而在另一个列表中缺失的对象，依据是attr_one这个属性。在这种情况下，第一列表中存在而第二列表中缺失的项目的期望输出如下：

`['Foo('bcd', 3), Foo('cde', 4)]` 

同样，第二列表中存在但第一列表中缺失的项目：

 [Foo('bcd', 4), Foo('efg', 5)]

我想知道有没有办法根据attr_one这个属性来进行匹配。

  List 1                 List 2        
  Foo('bcd', 3)          Foo('bcd', 4)
  Foo('cde', 4)          None
  None                   Foo('efg', 5)

Answer 1

我有两种方法可以做到这一点——要么用 sets，要么用 filter：

class Foo(object):

    def __init__(self, attr_one=None, attr_two=None):
        self.attr_one = attr_one
        self.attr_two = attr_two

    def __eq__(self, other):
        return self.attr_one == other.attr_one and self.attr_two == other.attr_two

    def __hash__(self):
        return hash(self.attr_one)

    def __repr__(self):
        return "<Foo {} {}>".format(self.attr_one, self.attr_two)

def main():
    a = Foo('test', 1)
    b = Foo('test', 1)

    list1 = [Foo('abc', 2), Foo('bcd', 3), Foo('cde', 4)]
    list2 = [Foo('abc', 2), Foo('bcd', 4), Foo('efg', 5)]

    # With sets
    list1set = set(list1)
    list2set = set(list2)

    print list1set.intersection(list2set) 
    # Returns set([<Foo abc 2>])

    # With filter
    list2attr_one = [l.attr_one for l in list2]
    print filter(lambda x: x.attr_one in list2attr_one, list1)
    # Returns [<Foo abc 2>, <Foo bcd 3>]

Answer 2

一个快速比较两个列表的方法，看看哪个列表里有而另一个没有的元素，就是把原来的列表转换成集合，然后计算这两个集合之间的差异。要把列表变成集合，里面的元素必须是可以被“哈希”的，也就是说，你需要为你的Foo对象定义一个新的__hash__()方法：

def __hash__(self):
    return hash((self.attr_one,self.attr_two))

需要注意的是，由于元组是可以被哈希的，只要attr_one和attr_two是可以哈希的类型，这个实现应该是相当可靠的。

现在，想要找出一个列表里有而另一个没有的元素，可以这样做：

set1 = set(list1)
set2 = set(list2)
missing_from_1 = set2 - set1
missing_from_2 = set1 - set2

如果只想根据其中一个属性来判断，可以只用这些属性来创建集合：

set1 = set([i.attr_one for i in list1])

当然，这样做的结果只会告诉你哪些attr_one的值在一个列表里有而在另一个列表里没有，而不会给你实际的Foo对象。不过，一旦你找到了“缺失”的集合，找到这些对象本身也并不难：

missing_Foos = set()
for attr in missing_from_2:
    for i in list1:
        if i.attr_one == attr:
            missing_Foos.add(i)

不过，如果你的列表很长，这样的计算可能会比较耗时。

补充说明：使用集合的方式主要适合处理非常大的列表，这样可以利用集合操作的计算效率。否则，使用列表推导式可能会更简单，就像其他答案中提到的那样。

Answer 3

因为你已经定义了一个 __eq__ 方法，所以你可以使用列表推导式来找出两个列表中对象的独特性。

print [obj for obj in list1 if obj not in list2]