Finden Sie alle Vorkommen eines Schlüssels in verschachtelten Wörterbüchern und Listen

Ich habe ein Wörterbuch wie dieses:

{ "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" }] } ] } 

Grundsätzlich ein Wörterbuch mit verschachtelten Listen, Wörterbüchern und Zeichenfolgen beliebiger Tiefe.

Was ist der beste Weg, dies zu durchlaufen, um die Werte jedes "id" -Schlüssels zu extrahieren? Ich möchte das Äquivalent einer XPath-Abfrage wie "// id" erreichen. Der Wert von "id" ist immer eine Zeichenfolge.

In meinem Beispiel ist die Ausgabe, die ich brauche, im Grunde:

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

Ordnung ist nicht wichtig.

Ich fand diese Frage / Antwort sehr interessant, da sie verschiedene Lösungen für dasselbe Problem bietet. Ich habe all diese Funktionen übernommen und sie mit einem komplexen Wörterbuchobjekt getestet. Ich musste zwei Funktionen aus dem Test herausnehmen, weil sie zu viele Fehlschläge hatten und keine Rückgabe von Listen oder Diktaten als Werte unterstützten, was ich für wesentlich halte, da eine Funktion für fast alle kommenden Daten vorbereitet werden sollte .

Also habe ich die anderen Funktionen in 100.000 Iterationen durch das timeitModul gepumpt und die Ausgabe kam zu folgendem Ergebnis:

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)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Alle Funktionen hatten dieselbe Nadel zum Suchen ('Protokollierung') und dasselbe Wörterbuchobjekt, das wie folgt aufgebaut ist:

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]]
}

Alle Funktionen lieferten das gleiche Ergebnis, aber die Zeitunterschiede sind dramatisch! Die Funktion gen_dict_extract(k,o)ist meine Funktion, die von den Funktionen hier angepasst wurde. Eigentlich ist sie der findFunktion von Alfe ziemlich ähnlich , mit dem Hauptunterschied, dass ich überprüfe, ob das angegebene Objekt eine Iteritems-Funktion hat, falls während der Rekursion Zeichenfolgen übergeben werden:

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

Diese Variante ist also die schnellste und sicherste der Funktionen hier. Und find_all_itemsist unglaublich langsam und weit weg von der zweitlangsamsten, get_recursivleywährend der Rest, außer dict_extract, nahe beieinander liegt. Die Funktionen funund funktionieren keyHolenur, wenn Sie nach Zeichenfolgen suchen.

Interessanter Lernaspekt hier :)

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']

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

BEARBEITEN: @Anthon hat festgestellt, dass dies für direkt verschachtelte Listen nicht funktioniert. Wenn Sie dies in Ihrer Eingabe haben, können Sie Folgendes verwenden:

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

Aber ich denke, die Originalversion ist leichter zu verstehen, also werde ich sie verlassen.

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')))

Eine weitere Variante, die den verschachtelten Pfad zu den gefundenen Ergebnissen enthält ( Hinweis: Diese Version berücksichtigt keine Listen ):

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

Ich wollte nur die ausgezeichnete Antwort von @ hexerei-software anhand von yield fromListen der obersten Ebene wiederholen .

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)

Diese Funktion durchsucht rekursiv ein Wörterbuch mit verschachtelten Wörterbüchern und Listen. Es wird eine Liste mit dem Namen fields_found erstellt, die den Wert für jedes Mal enthält, wenn das Feld gefunden wird. Das 'Feld' ist der Schlüssel, nach dem ich im Wörterbuch und seinen verschachtelten Listen und Wörterbüchern suche.

def get_recursively (search_dict, Feld):
    "" "Nimmt ein Diktat mit verschachtelten Listen und Diktaten,
    und durchsucht alle Wörter nach einem Schlüssel des Feldes
    unter der Voraussetzung.
    "" "
    fields_found = []

    für Schlüssel Wert in search_dict.iteritems ():

        if key == Feld:
            fields_found.append (Wert)

        elif isinstance (Wert, Diktat):
            results = get_recursively (Wert, Feld)
            für Ergebnis in Ergebnissen:
                fields_found.append (Ergebnis)

        elif isinstance (Wert, Liste):
            für Wertgegenstand:
                if isinstance (item, dict):
                    more_results = get_recursively (Element, Feld)
                    für ein anderes Ergebnis in mehr Ergebnissen:
                        fields_found.append (ein anderes_Ergebnis)

    return fields_found

Hier ist mein Stich:

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]

Folgen Sie der Antwort der @ Hexerei-Software und dem Kommentar von @ bruno-bronosky, wenn Sie eine Liste / einen Satz von Schlüsseln durchlaufen möchten:

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    

Beachten Sie, dass ich eine Liste mit einem einzelnen Element ([Schlüssel]} anstelle des Zeichenfolgenschlüssels übergebe.