使用一對多關係迭代嵌套字典

Question

我有一個嵌套字典，其中列表作爲值，格式如下，足夠大以至於遞歸失敗。

aDict = {"R": [ 
      {"A": [ 
       {"B": [ 
        "C", "D" 
       ]} 
      ]}, 
      {"E": [ 
       {"F": [ 
        {"G": ["H"]}, "I" 
       ]} 
      ]} 
    ]} 

我需要遍歷字典來添加和更新值;然而，我目前在迭代樹時遇到了問題，最終陷入了無限循環。除集合外，我無法在標準庫之外使用軟件包。 :(

我當前的代碼假設父的說法已經在嵌套的字典，而是孩子的說法是沒有。

def build_tree(aDict, parent, child, default=None): 
    """""" 
    stack = [iter(aDict.items())] 
    while stack: 
     for k, v in stack[-1]: # loop through keys and values 
      if isinstance(v, dict): 
       stack.append(iter(v.items())) # if v is type dict, append it to stack 
       break 
      elif isinstance(v, list): 
       for elem in v: # if v is list, loop through elements of list 
        if isinstance(v, dict): 
         stack.append(iter(v.items())) 
        elif parent == elem: 
         a_dict = {parent: [child]} # replace elem with a_dict 
         aDict[k].remove(parent) 
         aDict[k].append(a_dict) 
         return default 
        else: 
         pass 
       break 
      elif parent in k: 
       v.append(child) # add child to values list for parent 
       return default 
      elif parent in v: # assumes v is list type 
       a_dict = {parent: [child]} # replace v with a_dict 
       aDict[k].remove(parent) 
       aDict[k].append(a_dict) 
       return default 
    else: 
     stack.pop() 
    return default 

，如果下面的代碼被註釋掉的功能不進入無限循環，但由於失敗列表中嵌套字典的存在。提前

elif isinstance(v, list): 
    for elem in v: # if v is list, loop through elements of list 
     if isinstance(v, dict): 
      stack.append(iter(v.items())) 
     elif parent == elem: 
      a_dict = {parent: [child]} # replace elem with a_dict 
      aDict[k].remove(parent) 
      aDict[k].append(a_dict) 
      return default 
     else: 
      pass 
    break 

謝謝！

Answer 1

此功能的非遞歸遵循在字典/目錄結構的路徑：

def by_path(data, path): 
    """ 
    data is the dict of lists list structure: {key: [value,...]} where values are same or scalars. 
    path is a sequence of keys in the dictionaries. 
    """ 
    result = None 
    level = [data] # We always pretend to work with a list of dicts. 
    traversed = [] # Purely for error reporting. 
    for key in path: 
     traversed.append(key) 
     next_dicts = [d for d in level if isinstance(d, dict) and key in d] 
     if not next_dicts: 
      raise ValueError('Failed to make next step; traversed so far %r' % traversed) 
     if len(next_dicts) > 1: 
      raise ValueError('Duplicate keys at %r' % traversed) 
     target_dict = next_dicts[0] 
     level = target_dict[key] # Guaranteed to work. 
    # path exhausted. 
    return level # A list/scalar at the end of the path 

它的工作原理就像這樣：

>>> by_path(aDict, ['R', 'A', 'B']) 
['C', 'D'] 
>>> by_path(aDict, ['R', 'A', 'wrong', 'path']) 
(traceback elided) 
ValueError: Failed to make next step; traversed so far ['R', 'A', 'wrong'] 

我希望這有助於。

當然，如果你經常遍歷相同的長子路徑，它可能是值得高速緩存的。如果您更新了緩存，則必須使緩存無效;除非你真的看到高CPU負載並且profiler說它確實是遍歷的，否則不要這樣做。

Answer 2

你可以寫一個簡單的遞歸遍歷˚F結：

import sys 

# for Python 3.x str is iterable, too, so we'll have to check for cross-version use 
isPY3 = sys.version_info.major > 2 

def traverse(data, level=0): 
    if hasattr(data, "__iter__") and not (isPY3 and isinstance(data, str)): 
     if isinstance(data, dict): # maybe check for MutableMapping, too? 
      for k in data: 
       print("L{}: {}".format(level, k)) # dictionary key 
       traverse(data[k], level + 1) 
     else: 
      for element in data: 
       traverse(element, level + 1) 
    elif data: 
     print("L{}: {}".format(level, data)) # any other value 

將通過您的iterables遞歸遍歷加上保持它目前在平的軌跡（你可以通過其他的東西，以及像父迭代器等），這將打印出（與你的改變數據）：

L0: R 
L2: A 
L4: B 
L6: C 
L6: D 
L2: E 
L4: F 
L6: G 
L8: H 
L6: I 

但是你可以做你想要的功能範圍內（可以通過刪除PY3檢查進一步簡化它）什麼的。然而，對於非常非常深的樹，你會達到Python的遞歸極限 - 但是如果你有這樣深的樹，你應該重新考慮你的策略/數據結構，因爲肯定有更好的方式來表示相同的數據（除非你「重新嘗試比無限深的樹映射分形）...