迭代過程中字典大小發生變化

在我的生活中，我不知道Python如何認爲我的dict在迭代期間正在改變大小。我嘗試了幾次修改代碼，並且無法弄清楚我會在哪裏修改字典。迭代過程中字典大小發生變化

概述：我正在研究層次聚類算法，其中我創建了一個MST，創建了一個圖，然後刪除弱於指定閾值的邊。這一切似乎都很好，但現在當我正在計算clusters（列表列表）時，我遇到了這個非常奇怪的錯誤。下面是我的代碼：

def compute_clusters(self): 
    """ wrapper function to compute clusters via DFS """ 
    mst = self.mst 
    total_nodes = len(mst.keys()) 
    visited = set() 
    for node in mst.keys(): 
     if node not in visited: 
      self.clusters += self.cluster_dfs(mst, node, visited) 

def cluster_dfs(self, mst, node, visited, cluster=[]): 
    """ creates clusters through dfs """ 
    cluster.append(node) 
    if self.dfs_finished(mst, node, visited): 
     return cluster 
    for neighbor in self.mst[node].keys(): 
     if neighbor not in visited: 
      visited.add(neighbor) 
      cluster.append(neighbor) 
      self.cluster_dfs(mst, neighbor, visited, cluster) 

def dfs_finished(self, mst, node, visited): 
    for neighbor in self.mst[node].keys(): 
     if neighbor not in visited: 
      return False 
    return True

基本上，mst是我的MST（defaultdict（字典））的副本，它映射的所有節點，以他們的鄰居：權重。

我想一個簡單的方法是從MST中的每個節點執行DFS，但尚未被DFS觸及。通過這個邏輯，遞歸只會在該特定集羣中的所有元素都被訪問之後纔會返回。然後它進入下一個集羣並執行DFS。

我的運行時錯誤是：

Traceback (most recent call last): 
File "cluster.py", line 91, in <module> 
    cluster.build_clusters() 
File "cluster.py", line 25, in build_clusters 
    self.compute_clusters() # compute final clusters 
File "cluster.py", line 66, in compute_clusters 
    for node in mst.keys(): 
RuntimeError: dictionary changed size during iteration

有誰看到一個地方，我可能會被意外修改dict？道歉，如果這是一個愚蠢的錯誤 - 我有點累。

來源

2016-11-30 Jack Ryan

不與你的問題有關，但是我擔心你的函數定義包含'cluster = []'。你知道[默認可變參數gotcha]（http://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument）？如果它讓你感到意外，它會導致一些難以察覺的問題。 – Kevin

'cluster_dfs'的最後一行是否應該有'return'？否則，您將在'self.clusters'中添加'None's –

我沒有在您共享的代碼中看到任何明顯的字典修改。你能提供[mcve]嗎？我會很有興趣在我自己的機器上覆制錯誤。 – Kevin

有沒有人看到一個地方，我可能會意外修改字典？

鑑於mst是defaultdict，一個可能的嫌疑人是：

for neighbor in self.mst[node].keys():

因爲這可能增加node到self.mst。如果這是它的問題如何;因爲更多的上下文/ mst設置可能會有所幫助。

好像它一樣，訪問一個不存在的key到defaultdict會添加鍵值。 ....一個MCVE ..

d = collections.defaultdict(int) 
print(d) 
keys = ['a','b','c'] 
for key in keys: 
    print(key, hex(d[key])) 
print(d) 

>>> 
defaultdict(<class 'int'>, {}) 
a 0x0 
b 0x0 
c 0x0 
defaultdict(<class 'int'>, {'a': 0, 'c': 0, 'b': 0}) 
>>>

來源

2016-11-30 19:31:06 everial

當然，使用它尚未包含的鍵索引defaultdict會導致其大小發生變化。但它看起來像'node'一直是'mst'中的一個鍵，因爲它最初從mst.keys（）中的節點獲得它的值......我同意更多的上下文將非常有用。 – Kevin

同意它會令人驚訝;我想象的情況是，有些節點認爲它有一個鄰居（無論出於何種原因）沒有在最初的'mst'中結束，並且它正在遞歸調用之一中死去。編輯：sniped由凱文=） – everial

糟糕，我看到'節點'也可以來自''在遞歸的情況下'的鄰居。所以這仍然是一個真正的可能性。 – Kevin

我猜的錯誤是在這裏：

for neighbor in self.mst[node].keys(): 
        ^^^^^^^^^ 
    if neighbor not in visited: 
     self.cluster_dfs(mst, neighbor, visited, cluster) 
         ^^^

mst[node]具有關鍵neighbor但是，這並不需要爲mst是真實本身直接

來源

2016-11-30 19:45:26

迭代過程中字典大小發生變化

回答

相關問題