Comment fusionner des dictionnaires de dictionnaires ?

Question

J'ai besoin de fusionner plusieurs dictionnaires, voici ce que j'ai par exemple :

dict1 = {1:{"a":{A}}, 2:{"b":{B}}}

dict2 = {2:{"c":{C}}, 3:{"d":{D}}}

Avec A B C et D étant des feuilles de l'arbre, comme {"info1":"value", "info2":"value2"}

Il existe un niveau inconnu de dictionnaires, il pourrait s'agir de {2:{"c":{"z":{"y":{C}}}}}

Dans mon cas, il représente une structure de répertoires/fichiers dont les nœuds sont des documents et les feuilles des fichiers.

Je souhaite les fusionner pour obtenir :

 dict3 = {1:{"a":{A}}, 2:{"b":{B},"c":{C}}, 3:{"d":{D}}}

Je ne sais pas comment je pourrais faire cela facilement avec Python.

Answer 1

Cette procédure récursive simple permet de fusionner un dictionnaire dans un autre tout en remplaçant les clés conflictuelles :

#!/usr/bin/env python2.7

def merge_dicts(dict1, dict2):
    """ Recursively merges dict2 into dict1 """
    if not isinstance(dict1, dict) or not isinstance(dict2, dict):
        return dict2
    for k in dict2:
        if k in dict1:
            dict1[k] = merge_dicts(dict1[k], dict2[k])
        else:
            dict1[k] = dict2[k]
    return dict1

print (merge_dicts({1:{"a":"A"}, 2:{"b":"B"}}, {2:{"c":"C"}, 3:{"d":"D"}}))
print (merge_dicts({1:{"a":"A"}, 2:{"b":"B"}}, {1:{"a":"A"}, 2:{"b":"C"}}))

O

{1: {'a': 'A'}, 2: {'c': 'C', 'b': 'B'}, 3: {'d': 'D'}}
{1: {'a': 'A'}, 2: {'b': 'C'}}

Answer 2

Basé sur les réponses de @andrew cooke. Il prend en charge les listes imbriquées d'une meilleure manière.

def deep_merge_lists(original, incoming):
    """
    Deep merge two lists. Modifies original.
    Recursively call deep merge on each correlated element of list. 
    If item type in both elements are
     a. dict: Call deep_merge_dicts on both values.
     b. list: Recursively call deep_merge_lists on both values.
     c. any other type: Value is overridden.
     d. conflicting types: Value is overridden.

    If length of incoming list is more that of original then extra values are appended.
    """
    common_length = min(len(original), len(incoming))
    for idx in range(common_length):
        if isinstance(original[idx], dict) and isinstance(incoming[idx], dict):
            deep_merge_dicts(original[idx], incoming[idx])

        elif isinstance(original[idx], list) and isinstance(incoming[idx], list):
            deep_merge_lists(original[idx], incoming[idx])

        else:
            original[idx] = incoming[idx]

    for idx in range(common_length, len(incoming)):
        original.append(incoming[idx])

def deep_merge_dicts(original, incoming):
    """
    Deep merge two dictionaries. Modifies original.
    For key conflicts if both values are:
     a. dict: Recursively call deep_merge_dicts on both values.
     b. list: Call deep_merge_lists on both values.
     c. any other type: Value is overridden.
     d. conflicting types: Value is overridden.

    """
    for key in incoming:
        if key in original:
            if isinstance(original[key], dict) and isinstance(incoming[key], dict):
                deep_merge_dicts(original[key], incoming[key])

            elif isinstance(original[key], list) and isinstance(incoming[key], list):
                deep_merge_lists(original[key], incoming[key])

            else:
                original[key] = incoming[key]
        else:
            original[key] = incoming[key]

Answer 3

Si vous avez un nombre inconnu de dictionnaires, je suggérerais une fonction récursive :

def combineDicts(dictionary1, dictionary2):
    output = {}
    for item, value in dictionary1.iteritems():
        if dictionary2.has_key(item):
            if isinstance(dictionary2[item], dict):
                output[item] = combineDicts(value, dictionary2.pop(item))
        else:
            output[item] = value
    for item, value in dictionary2.iteritems():
         output[item] = value
    return output

Answer 4

Au cas où quelqu'un voudrait encore autre de ce problème, voici ma solution.

Les vertus Il est court, déclaratif et fonctionnel (récursif, sans mutation).

Inconvénients potentiels : Ce n'est peut-être pas la fusion que vous recherchez. Consultez la docstring pour la sémantique.

def deep_merge(a, b):
    """
    Merge two values, with `b` taking precedence over `a`.

    Semantics:
    - If either `a` or `b` is not a dictionary, `a` will be returned only if
      `b` is `None`. Otherwise `b` will be returned.
    - If both values are dictionaries, they are merged as follows:
        * Each key that is found only in `a` or only in `b` will be included in
          the output collection with its value intact.
        * For any key in common between `a` and `b`, the corresponding values
          will be merged with the same semantics.
    """
    if not isinstance(a, dict) or not isinstance(b, dict):
        return a if b is None else b
    else:
        # If we're here, both a and b must be dictionaries or subtypes thereof.

        # Compute set of all keys in both dictionaries.
        keys = set(a.keys()) | set(b.keys())

        # Build output dictionary, merging recursively values with common keys,
        # where `None` is used to mean the absence of a value.
        return {
            key: deep_merge(a.get(key), b.get(key))
            for key in keys
        }

Answer 5

Vue d'ensemble

L'approche suivante subdivise le problème d'une fusion profonde de fichiers en plusieurs parties :

1. Une fonction de fusion superficielle paramétrée merge(f)(a,b) qui utilise un fonction f pour fusionner deux dicts a et b

2. Une fonction de fusion récursive f à utiliser conjointement avec merge

---

Mise en œuvre

Une fonction permettant de fusionner deux dicts (non imbriqués) peut être écrite de différentes manières. Personnellement, j'aime bien

def merge(f):
    def merge(a,b): 
        keys = a.keys() | b.keys()
        return {key:f(a.get(key), b.get(key)) for key in keys}
    return merge

---

Une bonne façon de définir une fonction de fusion récursive appropriée f utilise multipledispatch qui permet de définir des fonctions qui s'évaluent selon différents chemins en fonction du type de leurs arguments.

from multipledispatch import dispatch

#for anything that is not a dict return
@dispatch(object, object)
def f(a, b):
    return b if b is not None else a

#for dicts recurse 
@dispatch(dict, dict)
def f(a,b):
    return merge(f)(a,b)

---

Exemple

Pour fusionner deux dicts imbriqués, il suffit d'utiliser merge(f) par exemple :

dict1 = {1:{"a":"A"},2:{"b":"B"}}
dict2 = {2:{"c":"C"},3:{"d":"D"}}
merge(f)(dict1, dict2)
#returns {1: {'a': 'A'}, 2: {'b': 'B', 'c': 'C'}, 3: {'d': 'D'}} 

---

Notes :

Les avantages de cette approche sont les suivants :

• La fonction est construite à partir de fonctions plus petites qui font chacune une seule chose ce qui rend le code plus simple à raisonner et à tester.

• Le comportement n'est pas codé en dur, mais peut être modifié et étendu selon les besoins, ce qui améliore la réutilisation du code (voir l'exemple ci-dessous).

---

Personnalisation

Certaines réponses ont également pris en compte les dicts qui contiennent des listes, par exemple, d'autres dicts (potentiellement imbriqués). Dans ce cas, il peut être utile de passer en revue les listes et de les fusionner en fonction de leur position. Cela peut être fait en ajoutant une autre définition à la fonction de fusion f :

import itertools
@dispatch(list, list)
def f(a,b):
    return [merge(f)(*arg) for arg in itertools.zip_longest(a, b)]