在两个字典中查找匹配的键值对

Question

在两个字典中查找匹配的键值对

python

5

如何高效地检查一个字典的键值对是否也存在于另一个字典中。
假设我有两个名为dict1和dict2的字典，并且这两个字典有一些相同的键值对。我想找到它们并打印出来。最高效的方法是什么？请给予建议。

- gliese581g

4个回答

2

关于...

matching_dict_values = {}
for key in dict1.keys():
    if key in dict2.keys():
        if dict1[key] == dict2[key]:
            matching_dict_values[key]=dict1[key]

- Cam

这与我的解决方案#1相同，但不作为一行代码。 - zmo

你知道哪个更有效率吗？ - Cam

你的意思是什么？是的，我明白了。实际上，我的解决方案＃1比你的更好，因为我使用了.iteritems()并遵循了@DSM的建议不要使用.keys()。请参阅我的答案以获取所有细节。 - zmo

0

更新至@zmo的答案

解决方案1：

d_inter = {k:v for k, v in dict1.items() if k in dict2 and dict2[k] == v}

解决方案2：

d_inter = dict(set(dict1.items()).intersection(dict2.items()))

- murat yalçın

0

我不明白为什么你需要比这更高级的东西：

if all([testKey in dict1, testKey in dict2]) and dict1[testKey] == dict2[testKey]:

我们不必担心KeyError，因为布尔测试会在and之前失败（与一个不存在的键相关联的值将永远不会被测试）

因此，要获取完整的公共键值对列表，您可以执行以下操作：

for testKey in set(dict1.keys() + dict2.keys()):
    if all([testKey in dict1, testKey in dict2]) and dict1[testKey] == dict2[testKey]:
        commonDict[testKey] = dict1[testKey]

- wnnmaw

他想要两个字典的交集，而不是判断一个给定的键是否在两个字典中都存在。因此，要将您的解决方案应用于他的问题，您需要告诉他执行 for testKey in dict1.keys()+dict2.keys(): ... ？！ - zmo

@zmo，在我看来，这里的真正问题是找出一个键值对是否同时存在于两个对象中，一旦找到了这些公共的键值对，其他的事情就相对容易了。但我会更新代码以获取完整的公共键值对列表。 - wnnmaw

尽管你的解决方案回答了问题，但它并不高效，因为它意味着一个常数 O(n*m*(n+m))，在最坏情况下是 O(n3)。 - zmo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- zmo · Accepted Answer

一种方法是：

d_inter = dict([k, v for k, v in dict1.iteritems() if k in dict2 and dict2[k] == v])

另一个：

d_inter = dict(set(d1.iteritems()).intersection(d2.iteritems()))

我不确定哪个更有效，所以让我们比较一下它们：

1. 通过字典迭代的解决方案:

- 我们解析dict1的所有键：for k,v in dict1.iteritems() -> O(n) - 然后我们检查该键是否在dict2中，if k in dict2 and dict2[k] == v -> O(m)

这使得它的全局最坏复杂度为O(n+m) ->O(n) 2. 使用set的解决方案：

- 如果我们假设将dict转换为set是O(n)：

我们解析d1的所有项目，创建第一个集合set(d1.iteritems()) ->O(n)
我们解析d2的所有项目，创建第二个集合set(d2.iteritems()) ->O(m)
我们获取两者的交集，平均情况下为O(min(len(s), len(t))或最坏情况下为O(n * m)

这使得全局最坏情况复杂度为O(2n*n*m)，对于大小相同的字典可以视为O(n^3)，因此方案1是最佳的

如果我们假设将dict转换为集合是O(1)（常数时间）

平均情况下为O(min(n,m))，最坏情况下为O(n*m)，那么在平均情况下方案2更好，因为O(n+m) > O(min(n,m))。

总之，你选择的解决方案将取决于你的数据集和你要进行的测量！;-)

注：我在那里考虑了set()的复杂性。

注2：对于解决方案#1，始终将最小的字典命名为dict2，对于解决方案#2，将最小的字典命名为dict1。

注意2016年：这个解决方案是为python2编写的。以下是使其准备好使用python3所需的更改：

用items()替换iteritems();
你也可以使用较新的字典推导语法：{[k，v for … == v]};
由于d.items()返回dict_items，它不再是可哈希的，因此你必须使用frozenset()而不是{frozenset(d1.items()).intersection(d2.items())}。