在字典中遞歸地找到一個鍵

我試圖編寫一個非常簡單的函數來遞歸搜索可能嵌套的（在極端情況下十個深度級別）Python字典，並返回它從給定的鍵中找到的第一個值。在字典中遞歸地找到一個鍵

我不明白爲什麼我的代碼不適用於嵌套字典。

它返回None。

然而，它的工作，但_finditem({"B":1,"A":2},"A")，返回2。

我敢肯定這是一個簡單的錯誤，但我找不到它。我覺得在標準庫或collections中可能會有這樣的東西，但是我也找不到這個。

來源

2013-02-19 Fredrick Brennan

請注意，檢查它是否是'dict'對象是個壞主意，因爲它排除了類似於dict的對象。相反，請'嘗試：...''，除了TypeError：...'。（請求寬恕，不允許）。 – 2013-02-19 16:32:11

另外請注意，由於字符本質上是無序的，如果你的嵌套結構中有多個鍵「A」，你永遠不會知道你會得到哪一個（就像一盒巧克力，我想......） – mgilson 2013-02-19 16:34:35

@mgilson在這個具體的案例沒關係，我考慮過這個。 :) – 2013-02-19 16:38:24

當你遞歸，你需要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以瞭解您是否找到了某些東西。

來源

2013-02-19 16:30:33 mgilson

這似乎是編寫遞歸函數時最常見的錯誤。 – 2013-02-19 16:30:56

@DanielRoseman - *聳肩* - 我自己犯了幾次這個錯誤。但是當你的函數返回'None'並且你不知道爲什麼時，這是一個暗示;-) – mgilson 2013-02-19 16:31:41

謝謝，這應該是顯而易見的。我正在看這個好一個小時！ – 2013-02-19 16:32:07

這是一個函數，它搜索包含嵌套字典和列表的字典。它創建了結果值的列表。

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

來源

2013-11-27 23:06:02

這裏是一個辦法做到這一點使用一個「堆棧」和"stack of iterators" pattern（學分加雷思·雷斯）：

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。

來源

2017-04-03 12:37:09 alecxe

在字典中遞歸地找到一個鍵

回答

相關問題