如何提高算法的速度？

Question

我有两张单子：

list1 = [(key1,val_key1), (key2,val_key2)]
list2 = [(key1,val_val1), (key2,val_val2)]

这是我的密码：

for lst1 in list1:
    for lst2 in list2:
        if lst1[0] == lst2[0]:
            list_allpairs.append((lst1[1],lst2[1]))

结果如下：

list_allpairs = [(val_key1,val_val1), (val_key2,val_val2)]

有可能使算法更快吗？我认为如果我对第二个循环（list2）使用pop方法，它应该工作得更快。你知道吗

Answer 1

正如Albin-paul所说，你的算法有一个O（n2）的顺序。您需要的是找到一种只迭代一次的方法。你知道吗

如果键相同，列表长度相同，并且两个列表已排序，则可以执行以下操作：

pairs = [list(zip(list1[i], list2[i]))[1] for i in range(len(list1))]

否则你应该像前面的答案所建议的那样去做一个口述。你知道吗

Answer 2

该算法在O(n)运行时复杂度下运行。这比以O(n^2)运行时复杂度运行的算法要快。我使用字典来存储键和值，然后比较一个键是否存在于另一个键中，然后生成结果。你知道吗

list1 =[('key1','val_key1'), ('key2','val_key2')]

list2 = [('key1','val_val1'), ('key2','val_val2')]

dict2 = {element1:element2 for element1,element2 in list2}

result = []
for key,value in list1:
    if key in dict2:
        result.append((value,dict2[key]))
print(result)

输出

[('val_key1', 'val_val1'), ('val_key2', 'val_val2')]