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

Im Grunde 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 ein String.

Aus meinem Beispiel ist die Ausgabe, die ich benötige, im Grunde genommen:

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

Reihenfolge ist nicht wichtig.

Ich fand diese Frage/Antwort sehr interessant, da sie mehrere verschiedene Lösungen für dasselbe Problem bietet. Ich habe all diese Funktionen genommen und sie mit einem komplexen Wörterbuchobjekt getestet. Zwei Funktionen musste ich aus dem Test nehmen, da sie zu viele Fail-Ergebnisse hatten und die Rückgabe von Listen oder Diktaten als Werte nicht unterstützten, was ich für wesentlich halte, da eine Funktion fast vorbereitet sein sollte beliebig Daten kommen.

Also habe ich die anderen Funktionen in 100.000 Iterationen durch die gepumpt timeit Modul und Ausgabe kamen 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 die gleiche Nadel, nach der gesucht werden musste („logging“) und das gleiche Dictionary-Objekt, das wie folgt aufgebaut war:

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 von den Funktionen hier angepasst, eigentlich ist es ziemlich ähnlich wie die find Funktion von Alfe, mit dem Hauptunterschied, dass ich überprüfe, ob das angegebene Objekt eine iteritems-Funktion hat, falls Strings während der Rekursion ü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_items ist unglaublich langsam und weit entfernt vom zweitlangsamsten get_recursivley während der Rest, außer dict_extract, liegt nah beieinander. Die Funktionen fun und keyHole funktionieren nur, wenn Sie nach Saiten 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']

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.items():
    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 bemerkte, dass dies nicht für direkt verschachtelte Listen funktioniert. Wenn Sie dies in Ihrer Eingabe haben, können Sie dies verwenden:

def find(key, value):
  for k, v in (value.items() 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 einfacher zu verstehen, also lasse ich es.

pip install nested-lookup

macht genau das was du suchst:

document = [ { 'taco' : 42 } , { 'salsa' : [ { 'burrito' : { 'taco' : 69 } } ] } ]

>>> print(nested_lookup('taco', document))
[42, 69]

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 mit wiederholen yield from und Akzeptieren von Top-Level-Listen.

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)