python - 比较来自 2 个以上列表的对象

Question

有没有办法比较超过 2 个列表的所有 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，obj在list8 里面有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)

---

为了说明这一点，我创建了一个使用 2 个列表的简短示例:

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 的对象。