Temukan semua kemunculan kunci dalam kamus dan daftar bertingkat

Saya punya kamus seperti ini:

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

Pada dasarnya kamus dengan daftar bersarang, kamus, dan string, dengan kedalaman yang berubah-ubah.

Apa cara terbaik untuk melintasi ini untuk mengekstrak nilai dari setiap kunci "id"? Saya ingin mencapai yang setara dengan kueri XPath seperti "// id". Nilai "id" selalu berupa string.

Jadi dari contoh saya, output yang saya butuhkan pada dasarnya adalah:

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

Keteraturan tidak penting.

Menurut saya Tanya Jawab ini sangat menarik, karena memberikan beberapa solusi berbeda untuk masalah yang sama. Saya mengambil semua fungsi ini dan mengujinya dengan objek kamus yang kompleks. Saya harus mengambil dua fungsi dari pengujian, karena mereka memiliki banyak hasil yang gagal dan mereka tidak mendukung daftar yang dikembalikan atau dicts sebagai nilai, yang menurut saya penting, karena suatu fungsi harus disiapkan untuk hampir semua data yang akan datang.

Jadi saya memompa fungsi lain dalam 100.000 iterasi melalui timeitmodul dan keluarannya menghasilkan hasil sebagai berikut:

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

Semua fungsi memiliki jarum yang sama untuk mencari ('logging') dan objek kamus yang sama, yang dibuat seperti ini:

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

Semua fungsi memberikan hasil yang sama, tetapi perbedaan waktu sangat dramatis! Fungsinya gen_dict_extract(k,o)adalah fungsi saya yang diadaptasi dari fungsi-fungsi di sini, sebenarnya sangat mirip dengan findfungsi dari Alfe, dengan perbedaan utama, bahwa saya memeriksa apakah objek yang diberikan memiliki fungsi iteritems, jika string dilewatkan selama rekursi:

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

Jadi varian ini adalah fungsi tercepat dan teraman di sini. Dan find_all_itemssangat lambat dan paling lambat kedua get_recursivleysementara sisanya, kecuali dict_extract, dekat satu sama lain. Fungsi fundan keyHolehanya berfungsi jika Anda mencari string.

Aspek pembelajaran yang menarik di sini :)

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 memperhatikan bahwa ini tidak akan berfungsi untuk daftar bersarang secara langsung. Jika Anda memiliki ini dalam masukan Anda, Anda dapat menggunakan ini:

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

Tapi menurut saya versi aslinya lebih mudah dimengerti, jadi saya akan tinggalkan.

Variasi lain, yang mencakup jalur bersarang ke hasil yang ditemukan ( catatan: versi ini tidak mempertimbangkan daftar ):

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

Saya hanya ingin mengulangi jawaban yang sangat baik @ hexerei-software menggunakan yield fromdan menerima daftar tingkat atas.

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)

Fungsi ini secara rekursif mencari kamus yang berisi kamus dan daftar bertingkat. Itu membangun daftar yang disebut field_found, yang berisi nilai untuk setiap kali field ditemukan. 'Bidang' adalah kunci yang saya cari di kamus dan daftar bersarang serta kamusnya.

def get_recursively (search_dict, field):
    "" "Mengambil dikt dengan daftar dan dict bersarang,
    dan mencari semua penis untuk kunci lapangan
    disediakan.
    "" "
    field_found = []

    untuk kunci, nilai di search_dict.iteritems ():

        jika kunci == bidang:
            field_found.append (nilai)

        elif isinstance (nilai, dikt):
            hasil = get_recursively (nilai, bidang)
            untuk hasil dalam hasil:
                field_found.append (hasil)

        elif isinstance (nilai, daftar):
            untuk item dalam nilai:
                if isinstance (item, dict):
                    more_results = get_recursively (item, field)
                    untuk another_result in more_results:
                        field_found.append (hasil_lain)

    mengembalikan field_found

Inilah tusukan saya:

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]

Menindaklanjuti jawaban software @hexerei dan komentar @ bruno-bronosky, jika Anda ingin mengulang daftar / set kunci:

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    

Perhatikan bahwa saya meneruskan daftar dengan satu elemen ([key]}, bukan kunci string.

pip install nested-lookup melakukan apa yang Anda cari:

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

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