Python中查找两个字典列表之间共同元素的最快方法

Question

我有两个字典列表。

list1 = [{'user_id':23, 'user_name':'John', 'age':30},
         {'user_id':24, 'user_name':'Shaun', 'age':31},
         {'user_id':25, 'user_name':'Johny', 'age':32}]

list2 =[{'user_id':23},
        {'user_id':25}]

现在我需要输出

list3 = [{'user_id':23, 'user_name':'John', 'age':30},
         {'user_id':25, 'user_name':'Johny','age':32}]

我希望找到最高效的方法，因为我的list1可能包含数百万行。

- curiousguy

---

你有尝试过一些速度不够快的东西吗？ - Ry-

你看过这个或者这个吗？速度不够快吗？你尝试过实现它们，但遇到了性能问题吗？ - idjaw

如果您只需要对list1执行一次扫描，那么您应该使用Jean-François Fabre的策略。但是，如果您需要多次搜索它，则应认真考虑将列表转换为字典，如omri_saadon的答案所述。与使用新字典的内部项目的字典不同，如果您使用元组或命名元组，则可以节省RAM。 - PM 2Ring

Answer 1

你需要将list2转化一下，以便快速查找。我会将其转化为一个set。

list1 = [{'user_id':23, 'user_name':'John','age':30},
         {'user_id':24, 'user_name':'Shaun','age':31},
         {'user_id':25, 'user_name':'Johny','age':32}]

list2 =[{'user_id':23},
        {'user_id':25}]

list2_ids = {d['user_id'] for d in list2}

然后使用过滤列表推导式构建list3。在这种情况下，in list2_ids非常快，因为它使用了来自set的查找，而不是线性搜索：

list3 = [x for x in list1 if x['user_id'] in list2_ids]

print(list3)

结果：

[{'user_id': 23, 'user_name': 'John', 'age': 30}, {'user_id': 25, 'user_name': 'Johny', 'age': 32}]

- Jean-François Fabre

Answer 2

我会将您的list1转换为一个字典，其中键是user_id，值是name和age。

现在，当您查找这个dict时，即使dict有很多元素，查找的复杂度也是O(1)。

在这种情况下，查找所有用户ID的整个复杂度为O(len(list2))。

dict1 = {23 : {'user_name':'John', 'age':30},
         24 : {'user_name':'Shaun', 'age':31},
         25 : {'user_name':'Johny', 'age':32}}

list2 =[{'user_id':23},
        {'user_id':25}]

res = [dict1.get(user['user_id']) for user in list2 if user['user_id'] in dict1]

print (res)

>>> [{'user_name': 'John', 'age': 30}, {'user_name': 'Johny', 'age': 32}]

- omri_saadon

---

要再次转换我的list1，我需要遍历整个list1。这本身就增加了复杂性。 - curiousguy

@curiousguy，你只需要做一遍。完成后，你就会拥有这个数据结构，可以在O(1)复杂度下进行大量的搜索操作。 - omri_saadon

是的，我同意你的观点，使用这种格式进行搜索非常快速。问题在于我的list1和list2根据输入不断变化。因此，我每次都需要重新执行这个操作。 - curiousguy

@curiousguy，你不能像上面的结构一样动态构建list1吗？难道不是由你控制吗？ - omri_saadon

是的，实际上我一定会尝试的。 - curiousguy

还要看@PM 2Ring的评论。当您需要进行多次搜索时，此解决方案非常好。如果您只需要搜索一次，则Jean-François Fabre的解决方案更合适。 - omri_saadon

Answer 3

你可以使用pandas将两个DataFrame合并在一起。
1. 将字典转换成DataFrame
2. 在"user_id"上合并两个DataFrame

import pandas as pd
list1 = [{'user_id':23, 'user_name':'John', 'age':30},
          {'user_id':24, 'user_name':'Shaun', 'age':31},
          {'user_id':25, 'user_name':'Johny', 'age':32}] 
list2 =[{'user_id':23},
         {'user_id':25}] 
df1 = pd.DataFrame(list1)
df1
   age  user_id user_name
0   30       23      John
1   31       24     Shaun
2   32       25     Johny
df2 = pd.DataFrame(list2)
df2
   user_id
0       23
1       25

pd.merge(df2,df1,on='user_id')
   user_id  age user_name
0       23   30      John
1       25   32     Johny

- galaxyan

---

实际上我这里避免使用pandas。 - curiousguy

Answer 4

就像之前的帖子所说，您需要从列表2中创建一个ID列表：

list2_ids = {d['user_id'] for d in list2}

完成这个步骤后，你还可以使用过滤函数：

filter(lambda x: x['user_id'] in list2_ids, list1)

虽然这种方法并不是最优化的，但它有一个好处，就是可以为并行计算提供多个实现（如果你正在处理大量数据，则可能需要这样做）。

话虽如此，从性能角度来看，最佳解决方案可能是集合交集（comparison）：

unique_ids = set([d['user_id'] for d in list1]) & set([d['user_id'] for d in list2])
list3 = [x for x in list1 if x['user_id'] in unique_ids]

如果你确定列表中不包含重复项，可以忽略set。

- Djib2011