Encontre todas as ocorrências de uma chave em listas e dicionários aninhados

Eu tenho um dicionário como este:

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

Basicamente, um dicionário com listas, dicionários e strings aninhados de profundidade arbitrária.

Qual é a melhor maneira de fazer isso para extrair os valores de cada chave "id"? Desejo obter o equivalente a uma consulta XPath como "// id". O valor de "id" é sempre uma string.

Portanto, a partir do meu exemplo, a saída de que preciso é basicamente:

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

A ordem não é importante.

Achei esta Q / A muito interessante, pois fornece várias soluções diferentes para o mesmo problema. Peguei todas essas funções e testei-as com um objeto de dicionário complexo. Tive que retirar duas funções do teste, porque eles tiveram muitos resultados reprovados e não suportavam o retorno de listas ou dictos como valores, o que considero essencial, uma vez que uma função deve ser preparada para quase todos os dados que virão.

Então eu bombeei as outras funções em 100.000 iterações através do timeit módulo e a saída veio para o seguinte resultado:

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

Todas as funções tinham o mesmo ponteiro para pesquisar ('logging') e o mesmo objeto de dicionário, que é construído assim:

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

Todas as funções forneceram o mesmo resultado, mas as diferenças de tempo são dramáticas! A função gen_dict_extract(k,o)é a minha função adaptada das funções aqui, na verdade é muito parecida com ofind função de Alfe, com a principal diferença, que estou verificando se o objeto fornecido tem função de iteritens, no caso de strings serem passadas durante a recursão:

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

Portanto, esta variante é a mais rápida e segura das funções aqui. E find_all_itemsé incrivelmente lento e distante do segundo mais lento get_recursivleyenquanto o resto, exceto dict_extract, está perto um do outro. As funções fune keyHolesó funcionam se você estiver procurando por strings.

Aspecto de aprendizagem interessante aqui :)

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 notou que isso não funcionará para listas aninhadas diretamente. Se você tiver isso em sua entrada, você pode usar isto:

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

Mas acho que a versão original é mais fácil de entender, então vou deixá-la.

Outra variação, que inclui o caminho aninhado para os resultados encontrados ( nota: esta versão não considera listas ):

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

Eu só queria repetir a excelente resposta do @hexerei-software usando yield frome aceitando listas de nível superior.

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)

Esta função pesquisa recursivamente um dicionário contendo dicionários e listas aninhados. Ele cria uma lista chamada fields_found, que contém o valor de cada vez que o campo é encontrado. O 'campo' é a chave que procuro no dicionário e em suas listas e dicionários aninhados.

def get_recursively (search_dict, field):
    "" "Obtém um dict com listas e dicts aninhados,
    e procura em todos os dicts por uma chave do campo
    forneceu.
    "" "
    fields_found = []

    para chave, valor em search_dict.iteritems ():

        if key == field:
            fields_found.append (valor)

        elif isinstance (valor, dict):
            resultados = get_recursively (value, field)
            para resultado em resultados:
                fields_found.append (resultado)

        elif isinstance (valor, lista):
            para item em valor:
                if isinstance (item, dict):
                    more_results = get_recursively (item, field)
                    para outro_resultado em more_results:
                        fields_found.append (another_result)

    return fields_found

Aqui está a minha tentativa:

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]

Acompanhando a resposta do software @hexerei e o comentário de @bruno-bronosky, se você quiser iterar em uma lista / conjunto de chaves:

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    

Observe que estou passando uma lista com um único elemento ([chave]}, em vez da chave da string.