奇怪的行爲Python生成器的遞歸性

我最近在一個算法中列出了Sagemath的二叉樹上的生成樹。奇怪的行爲Python生成器的遞歸性

這樣做，我的同事和我發現了一個我們並不完全瞭解的奇怪行爲。

對於規範方面，Sagemath使用Python 2.7和import absolute import from __future__。

算法使用帶有遞歸調用的「yield」關鍵字逐個列出生成樹。一次，我們在遞歸調用之前進行測試，以確保它不會觸發錯誤。但是，如果我們刪除測試並讓算法生成一個錯誤，而不捕獲它，那麼生成器不會自行停止，而是會傳遞給下一個遞歸調用。

如果我可以給一本圖文並茂的解釋，讓我們說有一個在每次遞歸調用3個步驟，我們得到了這樣的事情：

0級 - 第1步
0級 - 第2步
- 級別1 - 步驟1
- 1級 - 第2步
  - 2水平 - 步驟1 < - 這裏的錯誤發生，但不停止發電
- 1級 - 第3步
  - 2級 - 第1步
  - 2級 - 產量 -level 0 - 3步
...

如果我們用「try catch」來捕捉錯誤，那麼算法會自行停止。

我讓代碼在這裏;如果你不知道Sagemath，但我不確定你能抓住所有東西，但其中大部分是可以理解的。我會做出具體的評論來突出有趣的部分並刪除代碼的某些部分。

我希望有人能解釋我這種行爲;它就像生成器對象可以在遞歸調用期間處理異常並在生成時忽略它們。

def _rec_spanning_trees(): 
     if len(list_merged_edges) == self.order()-1: # CONDITION TO YIELD 
      for indexes in product(*list_merged_edges): 
       yield DiGraph([list_edges[index] for index in indexes], format='list_of_edges', pos=self.get_pos()) 

     # part removed 

     # THIS HERE ! 
     # "outgoing_edge_iterator" is raising an error if D does not have any edges 
     s, x, l = D.outgoing_edge_iterator(source).next() 

     # HERE ! 
     # If I remove the "if(len(...." then the line above will raise an error sometime, but do not if I let it 
     D.delete_edge(s, x, l) 
     if len(list(D.depth_first_search(source))) == D.order(): 
      for tree in _rec_spanning_trees(): 
       yield tree 
     D.add_edge(s, x, l) 

     # part removed 

     for tree in _rec_spanning_trees(): 
      yield tree 

     # part removed

來源

2017-06-15 XanX3601

向我們顯示完整的確切錯誤消息。 – user2357112

+您的代碼是如何被調用的 - 所以我們可以重新編寫 – alfasin

@ user2357112這就是要點，沒有錯誤，生成器似乎處理它。 – XanX3601

D.outgoing_edge_iterator(source).next()產生一個例外，肯定，但例外的是StopIteration。這是用來表示迭代器結束的異常，當它從您的生成器傳播出去併到達上面的for循環時，for循環將它表示循環完成。

在更新的Python版本中，此行爲爲changed;在發電機內部升起的StopIteration現在將被轉換爲RuntimeError。

來源

2017-06-15 23:10:29 user2357112

哦！好！那麼可以假設它會保持這種狀態，這是一個好辦法嗎？刪除這個「if」使得所有的算法更快 – XanX3601

@ XanX3601：我看不到你的整個算法，但是在我看來，去掉這個條件會讓你的算法錯誤;它看起來像是如果您刪除該條件，您的算法可能會開始生成斷開的子圖而不是生成樹。 – user2357112

Sage已經包含[生成樹生成函數]（http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.spanning_trees），所以你可以使用它。如果你特別需要一個迭代器（Sage的函數產生一個列表），將代碼從Sage的代碼中提取出來可能是一個很好的解決方法。 – user2357112

奇怪的行爲Python生成器的遞歸性

回答

相關問題