ネストされている可能性のある（最も極端な場合は10レベルの深さ）Pythonディクショナリを再帰的に検索し、指定されたキーから最初に見つかった値を返す非常に単純な関数を作成しようとしています。
ネストされた辞書でコードが機能しない理由がわかりません。
def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
_finditem(v, key)
print _finditem({"B":{"A":2}},"A")
を返しますNone。
ただし、を_finditem({"B":1,"A":2},"A")返す場合は機能し2ます。
簡単な間違いだと思いますが、見つかりません。すでに標準ライブラリやに何かがあるのでcollectionsはないかと思いますが、どちらも見つかりません。
あなたが再発するとき、あなたは次returnの結果を得る必要があります_finditem
def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
return _finditem(v, key) #added return statement
実際のアルゴリズムを修正するには、何も見つからなかった場合にそのアルゴリズムが_finditem返されることを認識する必要があるため、早期の返還を防ぐために明示的にチェックする必要があります。None
def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
item = _finditem(v, key)
if item is not None:
return item
もちろん、Noneいずれかの辞書に値がある場合、それは失敗します。その場合、この関数の番兵を設定し、object()何も見つからない場合はそれを返すことができます-次に、sentinel何かを見つけたかどうかを確認するためにに対してチェックすることができます。
これは、ネストされた辞書とリストの両方を含む辞書を検索する関数です。結果の値のリストを作成します。
def get_recursively(search_dict, field):
"""
Takes a dict with nested lists and dicts,
and searches all dicts for a key of the field
provided.
"""
fields_found = []
for key, value in search_dict.iteritems():
if key == field:
fields_found.append(value)
elif isinstance(value, dict):
results = get_recursively(value, field)
for result in results:
fields_found.append(result)
elif isinstance(value, list):
for item in value:
if isinstance(item, dict):
more_results = get_recursively(item, field)
for another_result in more_results:
fields_found.append(another_result)
return fields_found
「スタック」と「イテレータのスタック」パターン（Gareth Reesのクレジット）を使用してこれを行う方法は次のとおりです。
def search(d, key, default=None):
"""Return a value corresponding to the specified key in the (possibly
nested) dictionary d. If there is no item with that key, return
default.
"""
stack = [iter(d.items())]
while stack:
for k, v in stack[-1]:
if isinstance(v, dict):
stack.append(iter(v.items()))
break
elif k == key:
return v
else:
stack.pop()
return default
print(search({"B": {"A": 2}}, "A"))を印刷します2。
短くしようとしているだけです：
def get_recursively(search_dict, field):
if isinstance(search_dict, dict):
if field in search_dict:
return search_dict[field]
for key in search_dict:
item = get_recursively(search_dict[key], field)
if item is not None:
return item
elif isinstance(search_dict, list):
for element in search_dict:
item = get_recursively(element, field)
if item is not None:
return item
return None
評判が悪いため、@mgilstonによって提案された承認済みのソリューションにコメントを追加できませんでした。検索対象のキーがリスト内にある場合、ソリューションは機能しません。
リストの要素をループして再帰関数を呼び出すと、ネストされたリスト内の要素を検索する機能が拡張されます。
def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
item = _finditem(v, key)
if item is not None:
return item
elif isinstance(v,list):
for list_item in v:
item = _finditem(list_item, key)
if item is not None:
return item
print(_finditem({"C": {"B": [{"A":2}]}}, "A"))
複数のネストされた辞書とリストを含む辞書で、一意に指定されたキー（目的の値へのパスを指定する最小限の辞書）を見つける一般的なバージョンを作成する必要がありました。
以下の例では、検索するターゲット辞書が作成され、ワイルドカード「???」を使用してキーが作成されます。実行すると、値「D」が返されます
def lfind(query_list:List, target_list:List, targ_str:str = "???"):
for tval in target_list:
#print("lfind: tval = {}, query_list[0] = {}".format(tval, query_list[0]))
if isinstance(tval, dict):
val = dfind(query_list[0], tval, targ_str)
if val:
return val
elif tval == query_list[0]:
return tval
def dfind(query_dict:Dict, target_dict:Dict, targ_str:str = "???"):
for key, qval in query_dict.items():
tval = target_dict[key]
#print("dfind: key = {}, qval = {}, tval = {}".format(key, qval, tval))
if isinstance(qval, dict):
val = dfind(qval, tval, targ_str)
if val:
return val
elif isinstance(qval, list):
return lfind(qval, tval, targ_str)
else:
if qval == targ_str:
return tval
if qval != tval:
break
def find(target_dict:Dict, query_dict:Dict):
result = dfind(query_dict, target_dict)
return result
target_dict = {"A":[
{"key1":"A", "key2":{"key3": "B"}},
{"key1":"C", "key2":{"key3": "D"}}]
}
query_dict = {"A":[{"key1":"C", "key2":{"key3": "???"}}]}
result = find(target_dict, query_dict)
print("result = {}".format(result))
私は自分の帽子をリングに投げ込むと思いましたが、これにより、__getitem__メソッドを実装するものすべてに対して再帰的な要求が可能になります。
def _get_recursive(obj, args, default=None):
"""Apply successive requests to an obj that implements __getitem__ and
return result if something is found, else return default"""
if not args:
return obj
try:
key, *args = args
_obj = object.__getitem__(obj, key)
return _get_recursive(_obj, args, default=default)
except (KeyError, IndexError, AttributeError):
return default