在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}]

现在我想要输出

^{pr2}$

我需要最有效的方法，因为我的list1可能包含数百万行。在

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的查找而不是线性搜索：

^{pr2}$

结果：

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

Answer 2

正如之前的海报所说，您需要从列表2中创建一个ID列表：

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

完成此操作后，还可以使用过滤器功能：

^{pr2}$

这一点虽然没有优化，但它的好处是有多个并行计算实现（如果处理的是大量数据，则可能需要这种实现）。在

也就是说，最好的解决方案性能可能是设置交集（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]

如果您确定列表不包含重复项，则可以忽略设置。在

Answer 3

当键是user_id，值是name和{}时，我会将你的{}转换成字典。在

现在，当您查看这个dict时，即使dict有很多元素，对于find来说，复杂性是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}]