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

J'ai une solution itérative - qui fonctionne beaucoup mieux avec les grands dicts et un grand nombre d'entre eux (par exemple jsons, etc.) :

import collections

def merge_dict_with_subdicts(dict1: dict, dict2: dict) -> dict:
    """
    similar behaviour to builtin dict.update - but knows how to handle nested dicts
    """
    q = collections.deque([(dict1, dict2)])
    while len(q) > 0:
        d1, d2 = q.pop()
        for k, v in d2.items():
            if k in d1 and isinstance(d1[k], dict) and isinstance(v, dict):
                q.append((d1[k], v))
            else:
                d1[k] = v

    return dict1

Notez que ceci utilisera la valeur de d2 pour remplacer d1, au cas où ils ne seraient pas tous deux des dicts. (comme la fonction dict.update() )

certains tests :

def test_deep_update():
    d = dict()
    merge_dict_with_subdicts(d, {"a": 4})
    assert d == {"a": 4}

    new_dict = {
        "b": {
            "c": {
                "d": 6
            }
        }
    }
    merge_dict_with_subdicts(d, new_dict)
    assert d == {
        "a": 4,
        "b": {
            "c": {
                "d": 6
            }
        }
    }

    new_dict = {
        "a": 3,
        "b": {
            "f": 7
        }
    }
    merge_dict_with_subdicts(d, new_dict)
    assert d == {
        "a": 3,
        "b": {
            "c": {
                "d": 6
            },
            "f": 7
        }
    }

    # test a case where one of the dicts has dict as value and the other has something else
    new_dict = {
        'a': {
            'b': 4
        }
    }
    merge_dict_with_subdicts(d, new_dict)
    assert d['a']['b'] == 4

J'ai testé avec environ ~1200 dicts - cette méthode a pris 0,4 secondes, alors que la solution récursive a pris ~2,5 secondes.

Answer 2

Comme indiqué dans de nombreuses autres réponses, un algorithme récursif est le plus logique dans ce cas. En général, lorsqu'on travaille avec la récursivité, il est préférable de créer de nouvelles valeurs plutôt que d'essayer de modifier une structure de données d'entrée.

Nous devons définir ce qui se passe à chaque étape de la fusion. Si les deux entrées sont des dictionnaires, c'est facile : nous copions les clés uniques de chaque côté, et fusionnons récursivement les valeurs des clés dupliquées. Ce sont les cas de base qui posent problème. Il sera plus facile de comprendre la logique si nous créons une fonction distincte pour cela. En guise de substitut, nous pourrions simplement envelopper les deux valeurs dans un tuple :

def merge_leaves(x, y):
    return (x, y)

Le cœur de notre logique est maintenant le suivant :

def merge(x, y):
    if not(isinstance(x, dict) and isinstance(y, dict)):
        return merge_leaves(x, y)
    x_keys, y_keys = x.keys(), y.keys()
    result = { k: merge(x[k], y[k]) for k in x_keys & y_keys }
    result.update({k: x[k] for k in x_keys - y_keys})
    result.update({k: y[k] for k in y_keys - x_keys})
    return result

Testons-le :

>>> x = {'a': {'b': 'c', 'd': 'e'}, 'f': 1, 'g': {'h', 'i'}, 'j': None}
>>> y = {'a': {'d': 'e', 'h': 'i'}, 'f': {'b': 'c'}, 'g': 1, 'k': None}
>>> merge(x, y)
{'f': (1, {'b': 'c'}), 'g': ({'h', 'i'}, 1), 'a': {'d': ('e', 'e'), 'b': 'c', 'h': 'i'}, 'j': None, 'k': None}
>>> x # The originals are unmodified.
{'a': {'b': 'c', 'd': 'e'}, 'f': 1, 'g': {'h', 'i'}, 'j': None}
>>> y
{'a': {'d': 'e', 'h': 'i'}, 'f': {'b': 'c'}, 'g': 1, 'k': None}

Nous pouvons facilement modifier la règle de fusion des feuilles, par exemple :

def merge_leaves(x, y):
    try:
        return x + y
    except TypeError:
        return Ellipsis

et observer les effets :

>>> merge(x, y)
{'f': Ellipsis, 'g': Ellipsis, 'a': {'d': 'ee', 'b': 'c', 'h': 'i'}, 'j': None, 'k': None}

Nous pourrions aussi potentiellement nettoyer cela en utilisant une bibliothèque tierce pour distribuer en fonction du type des entrées. Par exemple, en utilisant multipledispatch Nous pourrions faire des choses comme.. :

@dispatch(dict, dict)
def merge(x, y):
    x_keys, y_keys = x.keys(), y.keys()
    result = { k: merge(x[k], y[k]) for k in x_keys & y_keys }
    result.update({k: x[k] for k in x_keys - y_keys})
    result.update({k: y[k] for k in y_keys - x_keys})
    return result

@dispatch(str, str)
def merge(x, y):
    return x + y

@dispatch(tuple, tuple)
def merge(x, y):
    return x + y

@dispatch(list, list)
def merge(x, y):
    return x + y

@dispatch(int, int):
def merge(x, y):
    raise ValueError("integer value conflict")

@dispatch(object, object):
    return (x, y)

Cela nous permet de gérer diverses combinaisons de cas spéciaux de type feuille sans écrire notre propre vérification de type, et remplace également la vérification de type dans la fonction récursive principale.

Answer 3

Le code dépendra de vos règles de résolution des conflits de fusion, bien entendu. Voici une version qui peut prendre un nombre arbitraire d'arguments et qui les fusionne récursivement jusqu'à une profondeur arbitraire, sans utiliser de mutation d'objet. Elle utilise les règles suivantes pour résoudre les conflits de fusion :

• Les dictionnaires ont la priorité sur les valeurs non-dict ( {"foo": {...}} a la priorité sur {"foo": "bar"} )

• les arguments ultérieurs ont la priorité sur les arguments antérieurs (si vous fusionnez {"a": 1} , {"a", 2} et {"a": 3} dans l'ordre, le résultat sera {"a": 3} )

  try: from collections import Mapping except ImportError: Mapping = dict

  def merge_dicts(*dicts):
  """
  Return a new dictionary that is the result of merging the arguments together.
  In case of conflicts, later arguments take precedence over earlier arguments.
  """
  updated = {}

  grab all keys

  keys = set()                                                                    
  for d in dicts:                                                                 
      keys = keys.union(set(d))                                                   
  
  for key in keys:                                                                
      values = [d[key] for d in dicts if key in d]                                
      # which ones are mapping types? (aka dict)                                  
      maps = [value for value in values if isinstance(value, Mapping)]            
      if maps:                                                                    
          # if we have any mapping types, call recursively to merge them          
          updated[key] = merge_dicts(*maps)                                       
      else:                                                                       
          # otherwise, just grab the last value we have, since later arguments    
          # take precedence over earlier arguments                                
          updated[key] = values[-1]                                               
  return updated

Answer 4

J'avais deux dictionnaires ( a et b ) qui pourraient contenir chacun un nombre quelconque de dictionnaires imbriqués. Je voulais les fusionner récursivement, avec b qui a la priorité sur a .

En considérant les dictionnaires imbriqués comme des arbres, ce que je voulais était :

• Mettre à jour a de sorte que chaque chemin vers chaque feuille de b serait représenté dans a
• Pour écraser les sous-arbres de a si une feuille est trouvée dans le chemin correspondant dans b
  • Maintenir l'invariant selon lequel tous les b les nœuds feuilles restent des feuilles.

Les réponses existantes étaient un peu compliquées à mon goût et laissaient certains détails en suspens. J'ai bricolé ce qui suit, qui passe les tests unitaires pour mon ensemble de données.

  def merge_map(a, b):
    if not isinstance(a, dict) or not isinstance(b, dict):
      return b

    for key in b.keys():
      a[key] = merge_map(a[key], b[key]) if key in a else b[key]
    return a

Exemple (formaté pour plus de clarté) :

 a = {
    1 : {'a': 'red', 
         'b': {'blue': 'fish', 'yellow': 'bear' },
         'c': { 'orange': 'dog'},
    },
    2 : {'d': 'green'},
    3: 'e'
  }

  b = {
    1 : {'b': 'white'},
    2 : {'d': 'black'},
    3: 'e'
  }

  >>> merge_map(a, b)
  {1: {'a': 'red', 
       'b': 'white',
       'c': {'orange': 'dog'},},
   2: {'d': 'black'},
   3: 'e'}

Les chemins en b qui devaient être maintenus sont les suivants :

• 1 -> 'b' -> 'white'
• 2 -> 'd' -> 'black'
• 3 -> 'e' .

a ont eu des parcours uniques et non contradictoires :

• 1 -> 'a' -> 'red'
• 1 -> 'c' -> 'orange' -> 'dog'

afin qu'elles soient toujours représentées dans la carte fusionnée.

Answer 5

Et juste une autre petite variation :

Voici une fonction de mise à jour profonde basée sur un ensemble en python3. Elle met à jour des dictionnaires imbriqués en parcourant un niveau à la fois et en s'appelant elle-même pour mettre à jour chaque niveau suivant des valeurs du dictionnaire :

def deep_update(dict_original, dict_update):
    if isinstance(dict_original, dict) and isinstance(dict_update, dict):
        output=dict(dict_original)
        keys_original=set(dict_original.keys())
        keys_update=set(dict_update.keys())
        similar_keys=keys_original.intersection(keys_update)
        similar_dict={key:deep_update(dict_original[key], dict_update[key]) for key in similar_keys}
        new_keys=keys_update.difference(keys_original)
        new_dict={key:dict_update[key] for key in new_keys}
        output.update(similar_dict)
        output.update(new_dict)
        return output
    else:
        return dict_update

Un exemple simple :

x={'a':{'b':{'c':1, 'd':1}}}
y={'a':{'b':{'d':2, 'e':2}}, 'f':2}

print(deep_update(x, y))
>>> {'a': {'b': {'c': 1, 'd': 2, 'e': 2}}, 'f': 2}