比较两个以上列表中的对象

Question

有没有办法比较两个以上列表的所有2项组合？你知道吗

假设有一个对象：

class obj():
   def __init__():
       self.name = # some name
       self.number = random(10)
   def equals(obj):
       if self.number == obj.number:
           return True
       else: return False

list1,list2,list3....listX-所有这些列表都包含类obj的实例

我想比较这些列表中的所有2项组合并返回相等的对象。你知道吗

因此，如果在list2中有一个obj，它的obj.number属性是5，而在list8中有一个obj，它的obj.number属性是5，那么它将被返回。你知道吗

对于两个列表，比较很简单：

   for obj1 in list1:
      for obj2 in list2:
          if obj1.equals(obj2):
               print obj1,obj2

但我不知道如何对更多的对象列表进行比较。 你有什么建议吗？你知道吗

Answer 1

您可能知道，对于X列表，时间复杂度将上升到O（n^X），这远不是最佳的（在所有列表的长度都相同的情况下=n）

现在一切都取决于你想要什么样的输出。在我看来，您似乎想找到存在于多个列表中的对象。你知道吗

一种更有效的方法是使用字典（hashmap）并遍历每个列表。基于对象的self.number散列对象。你知道吗

这将产生如下结果：{1: [obj1], 2: [obj2, obj3], 3: [obj4], ...}，其中键是对象的编号，值是将这些值作为编号的对象。你知道吗

通过遍历这个字典，并且只考虑列表大小大于或等于2的条目，您将得到相等的对象。你知道吗

这里的时间复杂度等于O（n*X），即~O（n）

---

为了说明这一点，我创建了一个简短的示例，其中使用了两个列表：

from collections import defaultdict

class Obj():
   def __init__(self, value):
       self.number = value


def find_equals(list1,list2):
    d = defaultdict(list)
    for obj1 in list1:
        d[obj1.number].append(obj1)
    for obj2 in list2:
        d[obj2.number].append(obj2)
    return [d[i] for i in d if len(d[i]) >= 2]

def test():
    l1 = [Obj(1),Obj(2),Obj(3),Obj(4)]
    l2 = [Obj(5),Obj(2),Obj(3),Obj(6)]
    print find_equals(l1,l2)
test()

它可能可以用漂亮的python构造进行优化，但它显示了它背后的思想。你知道吗

输出为：

[[<__main__.Obj instance at 0x103278440>, <__main__.Obj instance at 0x103278560>], [<__main__.Obj instance at 0x103278488>, <__main__.Obj instance at 0x1032785a8>]]

它们是在测试样本中使用的带有数字2和3的对象。你知道吗

Answer 2

一个（非常）简单的方法是获得对象列表的交集。 为此，您必须使对象可散列，为每个对象列表构建一个集合。你知道吗

def __hash__(self):
    return self.number

然后，要检查多个列表，只需选择集合交点：

x = [Obj(1) Obj(3) Obj(8) Obj(10) Obj(3)] 
y = [Obj(2) Obj(9) Obj(10) Obj(3)] 

intersection = x & y  # -> returns {Obj(3), Obj(10)}

此实现具有最坏情况复杂性(n - 1) * O(L)，其中L是集合长度的最大值，n是集合数。 所以，就复杂性而言，我认为詹森的答案更快。你知道吗

但是，如果性能不是问题（例如，你有小列表等），我认为能够写：

def intersect(*lists):
     return set.intersection(*map(set, lists))

或者用λ表示法来表示：

intersect = lambda *lists: set.intersection(*map(set, lists))