[解決済み] ネストされた辞書やリスト内のキーの出現回数をすべて検索する

質問

このような辞書があります。

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

順番は重要ではありません。

どのように解決するのですか？

このQ/Aは、同じ問題に対していくつかの異なる解決策を提供しているので、非常に興味深いものでした。私はこれらの関数をすべて受け取り、複雑な辞書オブジェクトでそれらをテストしました。2 つの関数をテストから外さなければなりませんでした。なぜなら、失敗結果が多すぎたことと、リストまたはディクショナリーを値として返すことをサポートしていなかったからです。 どんな のデータに対して準備される必要があるからです。

そこで、私は他の関数を100.000回繰り返して timeit モジュールに100,000回出力してみたところ、以下のような結果になりました。

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'）で、辞書オブジェクトも同じで、このように構成されていました。

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) は、ここで紹介されている関数を参考にしたもので、実際のところ、この関数は 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 は信じられないほど遅く、2 番目に遅い get_recursivley を除き、残りは dict_extract を除く残りの部分は互いに接近している。関数 fun と keyHole は、文字列を探す場合のみ機能します。

興味深い学習面ですね :)