Rechercher toutes les occurrences d'une clé dans des dictionnaires et des listes imbriqués

J'ai un dictionnaire comme celui-ci:

{ "id" : "abcde",
  "key1" : "blah",
  "key2" : "blah blah",
  "nestedlist" : [ 
    { "id" : "qwerty",
      "nestednestedlist" : [ 
        { "id" : "xyz",
          "keyA" : "blah blah blah" },
        { "id" : "fghi",
          "keyZ" : "blah blah blah" }],
      "anothernestednestedlist" : [ 
        { "id" : "asdf",
          "keyQ" : "blah blah" },
        { "id" : "yuiop",
          "keyW" : "blah" }] } ] } 

Fondamentalement, un dictionnaire avec des listes imbriquées, des dictionnaires et des chaînes de profondeur arbitraire.

Quelle est la meilleure façon de parcourir ceci pour extraire les valeurs de chaque clé "id"? Je veux obtenir l'équivalent d'une requête XPath comme "// id". La valeur de "id" est toujours une chaîne.

Donc, d'après mon exemple, la sortie dont j'ai besoin est essentiellement:

["abcde", "qwerty", "xyz", "fghi", "asdf", "yuiop"]

L'ordre n'est pas important.

J'ai trouvé ce Q / R très intéressant, car il fournit plusieurs solutions différentes pour le même problème. J'ai pris toutes ces fonctions et les ai testées avec un objet dictionnaire complexe. J'ai dû retirer deux fonctions du test, car elles avaient trop de résultats d'échec et elles ne prenaient pas en charge le renvoi de listes ou de dictionnaires en tant que valeurs, ce que je trouve essentiel, car une fonction doit être préparée pour presque toutes les données à venir.

J'ai donc pompé les autres fonctions en 100.000 itérations à travers le timeitmodule et la sortie est arrivée au résultat suivant:

0.11 usec/pass on gen_dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
6.03 usec/pass on find_all_items(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.15 usec/pass on findkeys(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1.79 usec/pass on get_recursively(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.14 usec/pass on find(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.36 usec/pass on dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Toutes les fonctions avaient la même aiguille à rechercher ('journalisation') et le même objet dictionnaire, qui est construit comme ceci:

o = { 'temparature': '50', 
      'logging': {
        'handlers': {
          'console': {
            'formatter': 'simple', 
            'class': 'logging.StreamHandler', 
            'stream': 'ext://sys.stdout', 
            'level': 'DEBUG'
          }
        },
        'loggers': {
          'simpleExample': {
            'handlers': ['console'], 
            'propagate': 'no', 
            'level': 'INFO'
          },
         'root': {
           'handlers': ['console'], 
           'level': 'DEBUG'
         }
       }, 
       'version': '1', 
       'formatters': {
         'simple': {
           'datefmt': "'%Y-%m-%d %H:%M:%S'", 
           'format': '%(asctime)s - %(name)s - %(levelname)s - %(message)s'
         }
       }
     }, 
     'treatment': {'second': 5, 'last': 4, 'first': 4},   
     'treatment_plan': [[4, 5, 4], [4, 5, 4], [5, 5, 5]]
}

Toutes les fonctions donnent le même résultat, mais les décalages horaires sont dramatiques! La fonction gen_dict_extract(k,o)est ma fonction adaptée des fonctions ici, en fait, c'est un peu comme la findfonction d'Alfe, avec la principale différence, que je vérifie si l'objet donné a une fonction iteritems, au cas où des chaînes seraient passées pendant la récursivité:

def gen_dict_extract(key, var):
    if hasattr(var,'iteritems'):
        for k, v in var.iteritems():
            if k == key:
                yield v
            if isinstance(v, dict):
                for result in gen_dict_extract(key, v):
                    yield result
            elif isinstance(v, list):
                for d in v:
                    for result in gen_dict_extract(key, d):
                        yield result

Cette variante est donc la plus rapide et la plus sûre des fonctions ici. Et find_all_itemsest incroyablement lent et loin du deuxième plus lent get_recursivleytandis que le reste, sauf dict_extract, est proche l'un de l'autre. Les fonctions funet keyHolene fonctionnent que si vous recherchez des chaînes.

Aspect d'apprentissage intéressant ici :)

d = { "id" : "abcde",
    "key1" : "blah",
    "key2" : "blah blah",
    "nestedlist" : [ 
    { "id" : "qwerty",
        "nestednestedlist" : [ 
        { "id" : "xyz", "keyA" : "blah blah blah" },
        { "id" : "fghi", "keyZ" : "blah blah blah" }],
        "anothernestednestedlist" : [ 
        { "id" : "asdf", "keyQ" : "blah blah" },
        { "id" : "yuiop", "keyW" : "blah" }] } ] } 


def fun(d):
    if 'id' in d:
        yield d['id']
    for k in d:
        if isinstance(d[k], list):
            for i in d[k]:
                for j in fun(i):
                    yield j

>>> list(fun(d))
['abcde', 'qwerty', 'xyz', 'fghi', 'asdf', 'yuiop']

d = { "id" : "abcde",
    "key1" : "blah",
    "key2" : "blah blah",
    "nestedlist" : [
    { "id" : "qwerty",
        "nestednestedlist" : [
        { "id" : "xyz", "keyA" : "blah blah blah" },
        { "id" : "fghi", "keyZ" : "blah blah blah" }],
        "anothernestednestedlist" : [
        { "id" : "asdf", "keyQ" : "blah blah" },
        { "id" : "yuiop", "keyW" : "blah" }] } ] }


def findkeys(node, kv):
    if isinstance(node, list):
        for i in node:
            for x in findkeys(i, kv):
               yield x
    elif isinstance(node, dict):
        if kv in node:
            yield node[kv]
        for j in node.values():
            for x in findkeys(j, kv):
                yield x

print(list(findkeys(d, 'id')))

def find(key, value):
  for k, v in value.iteritems():
    if k == key:
      yield v
    elif isinstance(v, dict):
      for result in find(key, v):
        yield result
    elif isinstance(v, list):
      for d in v:
        for result in find(key, d):
          yield result

EDIT: @Anthon a remarqué que cela ne fonctionnera pas pour les listes directement imbriquées. Si vous avez ceci dans votre entrée, vous pouvez utiliser ceci:

def find(key, value):
  for k, v in (value.iteritems() if isinstance(value, dict) else
               enumerate(value) if isinstance(value, list) else []):
    if k == key:
      yield v
    elif isinstance(v, (dict, list)):
      for result in find(key, v):
        yield result

Mais je pense que la version originale est plus facile à comprendre, je vais donc la laisser.

Une autre variante, qui inclut le chemin imbriqué vers les résultats trouvés ( note: cette version ne prend pas en compte les listes ):

def find_all_items(obj, key, keys=None):
    """
    Example of use:
    d = {'a': 1, 'b': 2, 'c': {'a': 3, 'd': 4, 'e': {'a': 9, 'b': 3}, 'j': {'c': 4}}}
    for k, v in find_all_items(d, 'a'):
        print "* {} = {} *".format('->'.join(k), v)    
    """
    ret = []
    if not keys:
        keys = []
    if key in obj:
        out_keys = keys + [key]
        ret.append((out_keys, obj[key]))
    for k, v in obj.items():
        if isinstance(v, dict):
            found_items = find_all_items(v, key, keys=(keys+[k]))
            ret += found_items
    return ret

Je voulais juste parcourir l'excellente réponse de @ hexerei-software en utilisant yield fromet en acceptant les listes de premier niveau.

def gen_dict_extract(var, key):
    if isinstance(var, dict):
        for k, v in var.items():
            if k == key:
                yield v
            if isinstance(v, (dict, list)):
                yield from gen_dict_extract(v, key)
    elif isinstance(var, list):
        for d in var:
            yield from gen_dict_extract(d, key)

Cette fonction recherche de manière récursive un dictionnaire contenant des dictionnaires et des listes imbriqués. Il construit une liste appelée fields_found, qui contient la valeur à chaque fois que le champ est trouvé. Le «champ» est la clé que je recherche dans le dictionnaire et ses listes et dictionnaires imbriqués.

def get_recursively (search_dict, champ):
    "" "Prend un dict avec des listes et des dictées imbriquées,
    et recherche tous les dictionnaires pour une clé du champ
    à condition de.
    "" "
    fields_found = []

    pour clé, valeur dans search_dict.iteritems ():

        si clé == champ:
            fields_found.append (valeur)

        elif isinstance (valeur, dict):
            résultats = get_recursively (valeur, champ)
            pour résultat dans les résultats:
                fields_found.append (résultat)

        elif isinstance (valeur, liste):
            pour l'article en valeur:
                if isinstance (item, dict):
                    more_results = get_recursively (élément, champ)
                    pour un autre_résultat dans more_results:
                        fields_found.append (another_result)

    return fields_found

Voici ma tentative:

def keyHole(k2b,o):
  # print "Checking for %s in "%k2b,o
  if isinstance(o, dict):
    for k, v in o.iteritems():
      if k == k2b and not hasattr(v, '__iter__'): yield v
      else:
        for r in  keyHole(k2b,v): yield r
  elif hasattr(o, '__iter__'):
    for r in [ keyHole(k2b,i) for i in o ]:
      for r2 in r: yield r2
  return

Ex.:

>>> findMe = {'Me':{'a':2,'Me':'bop'},'z':{'Me':4}}
>>> keyHole('Me',findMe)
<generator object keyHole at 0x105eccb90>
>>> [ x for x in keyHole('Me',findMe) ]
['bop', 4]

Suivi de la réponse du logiciel @hexerei et du commentaire de @ bruno-bronosky, si vous souhaitez parcourir une liste / un ensemble de clés:

def gen_dict_extract(var, keys):
   for key in keys:
      if hasattr(var, 'items'):
         for k, v in var.items():
            if k == key:
               yield v
            if isinstance(v, dict):
               for result in gen_dict_extract([key], v):
                  yield result
            elif isinstance(v, list):
               for d in v:
                  for result in gen_dict_extract([key], d):
                     yield result    

Notez que je passe une liste avec un seul élément ([clé]}, au lieu de la clé de chaîne.