在python中找到N个词典中的唯一（键：值）对 [英] Find unique (key: value) pair given N dictionnaries in python

问题描述

我想找到一个简单和/或快速的方式来查找在python中给出N个词典的所有常用夫妻（pair：value）。 （<3.>将是最好的）

问题

给定一组3 dicts （但它可以是任何 dict ，仅仅是为了示例）

  n1 = {'a'：1，'b'：2，'c'：3} 
 n2 = {'a'：1，'b'：4，'c'：3，'d'：4} 
 n3 = {'a'：1，'b'：2，'c' ，'d'：4} 
  

n1 ， n2 和 n3
应为：

 （{'a'：1，'c'：3}）
  

而对于 n2 和 n3 应该是

 （{'a'：1，'c'：3，'d'：4}）
  

我首先要使用一个强力算法，它将检查每对（key：value）每个dict

这是一个使用递归算法的实现

解决方案A

  list_dict = [n1，n2，n3] 
 
 def find_uniquness（ls）：
 
 def递归（ls，result）：
如果不是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} 
  
 $ b 
但不容易理解，复杂度高
（我不知道如何计算复杂度;但是由于我们比较了所有 dict 的所有元素，复杂度应该是O（N²）？）
 
 
 
然后我虽然关于 集 。因为它可以自然地比较所有元素
 
 
 
 解决方案B  
  import functools 
 
 list_dict = [n1，n2，n3] 
 set_list = [list（n.items（））for n在list_dict] 
 
 functools.reduce（lambda x，y：x& y，set_list）
＃{（'a'，1），（'c'，3）} 
  
它比以前的解决方案好多了，不幸的是，当一个键有一个列表作为值引发错误：
 >> ;> n = {'a'：[]，'b'：2，'c'：3} 
>>> set（n.items（））
  
 
 
 
 
 
 TypeError：unhashable type：列表'
 
 
我的问题是双倍：
 
 
 
 
 
是否有比 SOLUTION A 更好的算法？还是有办法通过解决方案B 避免 TypeError  
 
 
 
 
 
当然，欢迎任何其他评语。
解决方案
 p>更简单和更有效的方式：
 >>> {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：] 的额外变量可能是有益的，否则全部的短路有时会浪费。或者如果您以后不需要列表，您可以弹出主字典：
 >>> {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所建议的字典中：
 >>> marker = object（）
>>> {k：v 
 for k，v in list_dict.pop（）。items（）
如果全部（d.get（k，marker）== v 
 for d in list_dict）} 
 {'c'：3，'a'：1} 
  
 
I would like to find an easy and/or fast way to find all common couple (pair: value) given N dictionnaries in python. (3.X would be best)

PROBLEM

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}
The result for common (key: values) for n1, n2 and n3
should be:
({'a': 1, 'c': 3})
And for n2 and n3 it should be
({'a': 1, 'c': 3, 'd': 4})
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

SOLUTION 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}
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²)?)

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

SOLUTION 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)}
It is so much better than the previous solution, unfortunatly, when one of the key have a list as values it throws an error:
>>> n = {'a': [], 'b': 2, 'c': 3}
>>> set(n.items()) 



  
TypeError: unhashable type: 'list'
My question is then double:


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}
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}
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屋！