优化两个列表的嵌套循环

Question

我有一个程序，它会在两个不同的列表中查找，咱们叫它们list1和list2。

我只想打印出list1和list2中相同的项目。问题是，这两个列表中的项目并不是全部都能匹配，但第一个、第三个和第四个项目是应该匹配的。

如果它们匹配，我希望把完整的列表（包括那些不匹配的项目）添加到两个对应的列表中。

我写了以下代码：

for item in list1:
    for item2 in list2:
        if (item[0] and item[2:4])==(item[0] and item2[2:4]):
            newlist1.append(item)
            newlist2.append(item2)
            break

这个方法可以用，但效率不高。对于一些较大的文件，匹配的过程可能需要超过10秒，而理想情况下应该最多只要5秒。

我在想，每次运行代码时，不应该每次都从list2的开头开始，而是应该从上次匹配的地方继续。但我不知道该怎么在代码中实现。

Answer 1

from operator import itemgetter

getter = itemgetter(0, 2, 3)
for item,item2 in zip(list1, list2):
    if getter(item) == getter(item2):
        newlist1.append(item)
        newlist2.append(item2)
        break

这可能会稍微减少一些时间复杂度……

Answer 2

你的条件 (item[0] and item[2:4])==(item[0] and item2[2:4]) 是不对的。

另外，第二个 item[0] 可能应该改成 item2[0]。这里的 (item[0] and item[2:4]) 的意思是：

• 如果 item[0] 是 0，那么结果就是 item[0] 本身，也就是 0
• 如果 item[0] 不是 0，那么结果就是 item[2:4] 的值

然后这个结果会和第二个条件的结果进行比较。所以，[0,1,1,1] 会被认为和 [0,2,2,2] 相等，而 [1,1,1,1] 会被认为和 [2,1,1,1] 相等。

你可以试试用 tuples 来代替：

if (item[0], item[2:4]) == (item2[0], item2[2:4]):

或者可以使用 operator.itemgetter，就像其他回答中提到的那样。

---

为了加快两个列表中项的配对匹配，可以把第一个列表中的项放到一个字典里，使用这些元组作为键，然后遍历另一个列表，在字典中查找匹配的项。这样复杂度会变成 O(n+m)，而不是 O(n*m)（n 和 m 是列表的长度）。

key = operator.itemgetter(0, 2, 3)

list1_dict = {}
for item in list1:
    list1_dict.setdefault(key(item), []).append(item)

for item2 in list2:
    for item in list1_dict.get(key(item2), []):
        newlist1.append(item)
        newlist2.append(item2)