Intersection de deux dictionnaires

Question

Je travaille sur un programme de recherche sur un index inversé. L'index lui-même est un dictionnaire dont les clés sont des termes et dont les valeurs sont elles-mêmes des dictionnaires de documents courts, avec des numéros d'identification comme clés et leur contenu textuel comme valeurs.

Pour effectuer une recherche "ET" sur deux termes, je dois donc croiser leurs listes d'affichages (dictionnaires). Quelle est une façon claire (et pas nécessairement très intelligente) de faire cela en Python ? J'ai commencé par essayer la méthode longue avec iter :

p1 = index[term1]  
p2 = index[term2]
i1 = iter(p1)
i2 = iter(p2)
while ...  # not sure of the 'iter != end 'syntax in this case
...

Answer 1

Un fait peu connu est que vous n'avez pas besoin de construire set pour ce faire :

Dans Python 2 :

In [78]: d1 = {'a': 1, 'b': 2}

In [79]: d2 = {'b': 2, 'c': 3}

In [80]: d1.viewkeys() & d2.viewkeys()
Out[80]: {'b'}

Dans Python 3, remplacez viewkeys con keys ; il en va de même pour viewvalues y viewitems .

D'après la documentation de viewitems :

In [113]: d1.viewitems??
Type:       builtin_function_or_method
String Form:<built-in method viewitems of dict object at 0x64a61b0>
Docstring:  D.viewitems() -> a set-like object providing a view on D's items

Pour les plus grands dict ce qui est aussi légèrement plus rapide que de construire set puis en les croisant :

In [122]: d1 = {i: rand() for i in range(10000)}

In [123]: d2 = {i: rand() for i in range(10000)}

In [124]: timeit d1.viewkeys() & d2.viewkeys()
1000 loops, best of 3: 714 µs per loop

In [125]: %%timeit
s1 = set(d1)
s2 = set(d2)
res = s1 & s2

1000 loops, best of 3: 805 µs per loop

For smaller `dict`s `set` construction is faster:

In [126]: d1 = {'a': 1, 'b': 2}

In [127]: d2 = {'b': 2, 'c': 3}

In [128]: timeit d1.viewkeys() & d2.viewkeys()
1000000 loops, best of 3: 591 ns per loop

In [129]: %%timeit
s1 = set(d1)
s2 = set(d2)
res = s1 & s2

1000000 loops, best of 3: 477 ns per loop

Nous comparons des nanosecondes ici, ce qui peut ou non avoir de l'importance pour vous. Dans tous les cas, vous obtenez en retour un set donc en utilisant viewkeys / keys élimine un peu de désordre.

Answer 2

En général, pour construire l'intersection de dictionnaires en Python, vous pouvez d'abord utiliser la fonction & opérateur pour calculer l'intersection des ensembles des clés du dictionnaire ( les clés du dictionnaire sont des objets de type ensemble dans Python 3) :

dict_a = {"a": 1, "b": 2}
dict_b = {"a": 2, "c": 3} 

intersection = dict_a.keys() & dict_b.keys()  # {'a'}

Avec Python 2, vous devez convertir vous-même les clés du dictionnaire en ensembles :

keys_a = set(dict_a.keys())
keys_b = set(dict_b.keys())
intersection = keys_a & keys_b

Puis, étant donné l'intersection des clés, vous pouvez ensuite construire l'intersection de vos valeurs comme vous le souhaitez. Vous devez faire un choix ici, car le concept d'intersection d'ensembles ne vous dit pas quoi faire si les valeurs associées diffèrent. (C'est sans doute la raison pour laquelle le & l'opérateur d'intersection n'est pas défini directement pour les dictionnaires en Python).

Dans ce cas, il semble que vos valeurs pour la même clé soient égales, vous pouvez donc simplement choisir la valeur dans l'un des dictionnaires :

dict_of_dicts_a = {"a": {"x":1}, "b": {"y":3}}
dict_of_dicts_b = {"a": {"x":1}, "c": {"z":4}} 

shared_keys = dict_of_dicts_a.keys() & dict_of_dicts_b.keys()

# values equal so choose values from a:
dict_intersection = {k: dict_of_dicts_a[k] for k in shared_keys }  # {"a":{"x":1}}

D'autres méthodes raisonnables de combinaison des valeurs dépendent des types de valeurs dans vos dictionnaires et de ce qu'elles représentent. Par exemple, vous pourriez aussi vouloir l'union des valeurs pour les clés partagées de dictionnaires de dictionnaires. Puisque l'union de dictionnaires ne dépend pas des valeurs, elle est bien définie, et en python vous pouvez l'obtenir en utilisant la fonction | opérateur :

# union of values for each key in the intersection:
dict_intersection_2 = { k: dict_of_dicts_a[k] | dict_of_dicts_b[k] for k in shared_keys }

Ce qui, dans ce cas, avec des valeurs de dictionnaire identiques pour la clé "a" dans les deux, donnerait le même résultat.

Answer 3

In [1]: d1 = {'a':1, 'b':4, 'f':3}

In [2]: d2 = {'a':1, 'b':4, 'd':2}

In [3]: d = {x:d1[x] for x in d1 if x in d2}

In [4]: d
Out[4]: {'a': 1, 'b': 4}

Answer 4

En Python 3, vous pouvez utiliser

intersection = dict(dict1.items() & dict2.items())
union = dict(dict1.items() | dict2.items())
difference = dict(dict1.items() ^ dict2.items())

Answer 5

Aucune des solutions proposées jusqu'à présent ne résout le cas général de l'intersection de N dictionnaires.

Donc, si vous voulez gérer l'intersection de N des dictionnaires arbitraires :

from functools import reduce

def dict_intersection(*dict_list):
    return reduce(lambda a,b: dict(a.items() & b.items()), dict_list)

a = {k:k for k in range(0,5)} # {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
b = {k:k for k in range(2,7)} # {2: 2, 3: 3, 4: 4, 5: 5, 6: 6}
c = {k:k for k in range(3,8)} # {3: 3, 4: 4, 5: 5, 6: 6, 7: 7}

dict_intersection(a,b,c)  # {3:3, 4:4}
# or if you have a list of dicts
dicts = [{k:k for k in range(0+n,5+n)} for n in (0,2,3)] # == [a,b,c]
dict_intersection(*dicts) # {3:3, 4:4}

Utilisation de functools.reduce permet de réaliser l'opération en une seule itération sur la liste des dictionnaires au lieu des multiples boucles de certaines solutions. Elle n'exécute pas non plus d'instructions conditionnelles supplémentaires.

Compromis

Changer dict_intersection_v1 a dict_intersection_v2 nous pouvons voir qu'il fonctionne plus rapidement pour une plus grande liste de dictionnaires et/ou de dictionnaires (concevoir une expérience appropriée pour tester quel est le facteur le plus important est en dehors de la portée de cette solution). Ce gain de performance est dû à la réduction du nombre d'instanciations de dictionnaires.

def dict_intersection_v1(*dict_list):
    return reduce(lambda a,b: dict(a.items() & b.items()),  dict_list)

def dict_intersection_v2(*dict_list):
    return dict(reduce(lambda a,b: a & b, (d.items() for d in dict_list)))

dict_lst1 = [{k:k for k in range(0+n,5+n)} for n in (0,2,3)] # = [a,b,c]
dict_lst2 = [{k:k for k in range(0,50,n)} for n in range(1,5)]]
dict_lst3 = [{k:k for k in range(0,500,n)} for n in range(40)]
dict_lst4 = [{k:k for k in range(0+n,500+n)} for n in range(400)]

liste de dictées

nombre de paires de kv

dict_intersection_v1

dict_intersection_v2

différence relative

1

15

808 ns ± 4,31 ns par boucle (moyenne ± écart-type de 7 exécutions, 1000000 boucles chacune)

821 ns ± 0,785 ns par boucle (moyenne ± écart-type de 7 exécutions, 1000000 boucles chacune)

+ 1.6%

2

105

3,14 µs ± 11,9 ns par boucle (moyenne ± écart-type de 7 exécutions, 100000 boucles chacune)

2,38 µs ± 5,76 ns par boucle (moyenne ± écart-type de 7 exécutions, 100000 boucles chacune)

-24.2%

3

2155

36,9 µs ± 61,9 ns par boucle (moyenne ± écart-type de 7 exécutions, 10000 boucles chacune)

25,1 µs ± 131 ns par boucle (moyenne ± écart-type de 7 exécutions, 10000 boucles chacune)

-32.0%

4

200_000

9,08 ms ± 22 µs par boucle (moyenne ± écart-type de 7 passages, 100 boucles chacun)

4,88 ms ± 5,31 µs par boucle (moyenne ± écart-type de 7 passages, 100 boucles chacun)

-46.3%

La régression pour le résultat dict_lst1 est principalement dû à la différence de surcharge entre la création d'un dictionnaire après chaque intersection et la surcharge due à dict.items() dans le générateur (et le surcoût général des appels de fonctions de Python).

NB : J'ai fait un test en utilisant la liste pré-calculée de dict.items() pour le pour un dictionnaire au lieu de la v2's qui construit le générateur à la volée.

J'ai testé les deux passages dans la liste pré-calculée en dehors des timings et dans les timings, et, bien que ce soit statistiquement significatif, c'est moins de 30 μs et 10 μs respectivement. Si vous essayez d'obtenir ces gains en regardant un langage différent ou Cython pourrait être mieux.