在嵌套的python字典和列表中查找所有出现的键

Question

我有一本这样的字典：

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

基本上是一个包含嵌套列表、字典和字符串的字典，具有任意深度。

什么是遍历它以提取每个“id”键的值的最佳方式？我想实现类似“//id”的XPath查询。“id”的值总是一个字符串。

所以从我的例子来看，我需要的输出基本上是：

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

秩序并不重要。

Answer 1

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

Answer 2

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

编辑：@Anthon注意到这对直接嵌套的列表不起作用。如果您的输入中包含此项，则可以使用此项：

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

但我觉得原版比较容易理解，所以我就不写了。

Answer 3

我发现这个Q/A非常有趣，因为它为同一个问题提供了几种不同的解决方案。我取了所有这些函数，并用一个复杂的dictionary对象测试它们。我不得不将两个函数从测试中取出，因为它们必须有许多失败的结果，而且它们不支持将列表或dict作为值返回，我认为这是必要的，因为一个函数应该为几乎所有的数据做好准备。

所以我在100.000次迭代中通过timeit模块泵送了其他函数，结果如下：

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

所有函数都有相同的指针来搜索（'logging'）和相同的dictionary对象，其结构如下：

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

所有函数都提供了相同的结果，但时间差异是戏剧性的！函数gen_dict_extract(k,o)是我从这里的函数改编而来的函数，实际上它非常类似于Alfe的find函数，主要区别在于，我检查给定的对象是否有iteritems函数，以防在递归过程中传递字符串：

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

所以这个变种是这里最快最安全的函数。而find_all_items的速度非常慢，与第二慢的get_recursivley相差很远，而除dict_extract外，其余的都很近。函数fun和keyHole仅在查找字符串时才起作用。

有趣的学习方面：）