有没有办法比较 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 项组合并返回相等的对象。
所以如果
obj
中有list2
,obj.number
属性为5,obj
中有list8
,obj.number
为5,就会返回。对于两个列表,比较很简单:
for obj1 in list1:
for obj2 in list2:
if obj1.equals(obj2):
print obj1,obj2
但我不知道如何对更多的对象列表进行这种比较。
你有什么建议吗?
最佳答案
您可能知道,对于 X 个列表,时间复杂度将上升到 O(n^X),这远非最佳(在所有列表具有相同长度 =n 的情况下)
现在这一切都取决于您实际想要的输出。在我看来,您想要查找存在于多个列表中的对象。
以更高效的方式执行此操作的一种方法是使用字典(哈希图)并遍历每个列表。基于对象的 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
的对象。关于python - 比较 2 个以上列表中的对象,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31952619/