在Python中找到给定N个字典的唯一(键:值)对 [英] Find unique (key: value) pair given N dictionaries in python

问题描述

我想找到一种简单和/或快速的方法来找到给定N个字典的所有 common 对(对:value). ( 3.X最好)

I would like to find an easy and/or fast way to find all common couple (pair: value) given N dictionaries in python. (3.X would be best)

问题

给出一组3个dicts(但可以是任何dict，仅用于示例)

Given a set of 3 dicts (but it could be any dict, it is just for the example)

n1 = {'a': 1, 'b': 2, 'c': 3}
n2 = {'a': 1, 'b': 4, 'c': 3, 'd': 4}
n3 = {'a': 1, 'b': 2, 'c': 3, 'd': 4}

n1，n2和n3的通用(键:值)结果 应该是:

The result for common (key: values) for n1, n2 and n3 should be:

({'a': 1, 'c': 3})

n2和n3应该是

({'a': 1, 'c': 3, 'd': 4})

我首先要使用一种
brute force 算法，该算法将检查每个字典的每一对(键:值)

I first though about using a brute force algorithm that will check every pair (key: value) for every dict

这是使用递归算法的实现

Here is a implementation using a recursive algorithm

解决方案A

list_dict = [n1, n2, n3]

def finding_uniquness(ls):

    def recursion(ls, result):
        if not ls:
            return result
        result = {k: v  for k, v in result.items()  for k1, v1 in ls[0].items() if k == k1 and v == v1}
        return recursion(ls[1:], result)

    return recursion(ls[1:], ls[0])


finding_uniquness(list_dict)
# {'c': 3, 'a': 1}

但是它不容易理解并且复杂度很高 (我不确定如何计算复杂度；但是由于我们比较了所有dict上的所有元素，所以复杂度应该为O(N²)?)

But it is not easily understandable and the complexity is high (I'm not sure how to calculate complexity; but since we compare all the elements on all dict, the complexity should be O(N²)?)

然后，尽管如此，我还是 Sets .因为它可以自然地比较所有元素

Then, I though about Sets. because it could naturally compare all the element

解决方案B

import functools

list_dict = [n1, n2, n3]
set_list = [set(n.items()) for n in list_dict]

functools.reduce(lambda x, y: x & y, set_list)
 # {('a', 1), ('c', 3)}

它比以前的解决方案好得多，不幸的是，当key中的一个具有list作为值时，它会引发错误:

It is so much better than the previous solution, unfortunately, when one of the key have a list as values it throws an error:

>>> n = {'a': [], 'b': 2, 'c': 3}
>>> set(n.items()) 

TypeError:不可散列的类型:列表"

TypeError: unhashable type: 'list'

然后我的问题是双重的:

My question is then double:

• 有没有比解决方案A 更好的算法?
• 还是可以通过解决方案B 来避免TypeError吗?

• is there any better algorithm than SOLUTION A?
• or is there a way to avoid the TypeError with SOLUTION B?

当然，我们欢迎其他任何评论.

of course, any other remarks will be welcome.

推荐答案

更简单，更有效的方法:

Simpler and more efficient way:

>>> {k: v
     for k, v in list_dict[0].items()
     if all(k in d and d[k] == v
            for d in list_dict[1:])}
{'c': 3, 'a': 1}

为list_dict[1:]使用一个额外的变量可能是有益的，否则all的短路会有些浪费.或者，如果以后不需要列表，则可以弹出主"字典:

Using an extra variable for list_dict[1:] might be beneficial, otherwise the short-circuiting of all somewhat goes to waste. Or if you don't need the list afterwards you could just pop the "master" dictionary:

>>> {k: v
     for k, v in list_dict.pop().items()
     if all(k in d and d[k] == v
            for d in list_dict)}
{'c': 3, 'a': 1}

或使用get，其默认值不能出现在@Jean-FrançoisFabre建议的字典中:

Or using get with a default that cannot be in the dictionary as suggested by @Jean-FrançoisFabre:

>>> marker = object()
>>> {k: v
         for k, v in list_dict.pop().items()
         if all(d.get(k, marker) == v
                for d in list_dict)}
{'c': 3, 'a': 1}

这篇关于在Python中找到给定N个字典的唯一(键:值)对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！