爪哇 - 遞歸 - 例外在線程「主要」 java.lang.StackOverflowError的

試圖打印出文件相關的名單時，我遇到了一個問題。爪哇 - 遞歸 - 例外在線程「主要」 java.lang.StackOverflowError的

方案簡介：

掃描給出*依賴關係.c文件，更具體查找「的#include 「％」
查找這些文件並掃描他們的依賴遞歸
所有信息被存儲在一個的ConcurrentHashMap（鍵：字符串值：字符串的鏈接列表）。theTable，其中鏈接字符串列表包含依賴性列表
處理某個文件後，我結束了第e以下哈希表：

來源

2013-11-27 chuckfinley

爲什麼在這裏需要一個ConcurrentHashMap？ – isnot2bad

因爲我在完成單線程版本後需要實現併發。 – chuckfinley

在大多數情況下，與遞歸有關的StackOverflowError意味着你的停止條件是錯誤的 –

的問題是，我圖的遍歷了，我沒有處理週期。工作代碼在下面提供。

private static String printDependencies(ConcurrentHashMap<String, LinkedList<String>> theTable, LinkedList<String> dependencies, ConcurrentHashMap<String, Boolean> alreadyPrinted) { 

    String output = ""; 

    for (String d : dependencies) { 
     boolean isPrinted = alreadyPrinted.containsKey(d); 
     if (!isPrinted) { 
      output += " " + d; 
      alreadyPrinted.put(d, true); 
     }   
    } 

    for (String d : dependencies) { 
     LinkedList<String> key = theTable.get(d); 
     if (key != null) { 
      LinkedList<String> unvisited = new LinkedList<String>(); 
      for (String filename : key) 
       if (!alreadyPrinted.containsKey(filename)) 
        unvisited.add(filename); 
      if (unvisited != null)    
       output += printDependencies(theTable, unvisited, alreadyPrinted);    
     } 
    } 

    return output; 
} 

private static void printDependencies(ConcurrentHashMap<String, LinkedList<String>> theTable, ConcurrentLinkedQueue<String> toProcess) { 
    String output = ""; 

    for (String current : toProcess) { 
     ConcurrentHashMap<String, Boolean> alreadyPrinted = new ConcurrentHashMap<String, Boolean>(); // Keeps track of dependencies already printed 
     output += current + ":" + printDependencies(theTable, theTable.get(current), alreadyPrinted) + "\n"; 
    } 

    System.out.println(output);  
}

來源

2013-11-27 13:09:30 chuckfinley

測試是否已經打印相關性的唯一地方是循環的第一個地方。你也應該檢查第二個循環！

for (String d : dependencies) { 
    if (!alreadyPrinted.containsKey(d)) { 
     LinkedList<String> key = theTable.get(d);   
     if (key != null)    
      output += printDependencies(theTable, key, alreadyPrinted); 
    } 
}

來源

2013-11-27 12:03:41 isnot2bad

這是相當容易看到你的算法遞歸，只要一些依賴的樣子：

item: ...., item, ....

（我聽到你說：「那是不可能發生的，因爲......」。然而，SO顯示，無論是它確實發生了，或者你的籌碼是太小了。）

通過，您維護地圖「已經打印」的方式，但它是無處使用？這暗示你的實現存在缺陷。

來源

2013-11-27 12:04:49 Ingo

如你保持一定的狀態（alreadyPrinted和輸出），我會建議移動狀態，以實例變量都和使用對象和無類的方法。

來源

2013-11-27 12:05:30 AlexS

如果我沒有理解什麼地圖輸出是說，有你的頭文件一個週期（一個循環的#include）。

i_50.h=[i_35.h, i_28.h, i_45.h, i_44.h, i_46.h], 
.... 
i_35.h=[i_50.h, i_51.h]

這意味着您的依賴關係是一個圖而不是DAG。而這反過來意味着一個簡單的遞歸步行將不起作用。

通過它的外觀，你試圖做一個圖形走，但由於某些原因，你的循環檢測/避免不工作，你的算法進入「無限」遞歸。

看完代碼後，我想我可以看到問題出在哪裏。在第一種方法中，您檢查是否已經打印了依賴關係，然後將alreadyPrinted映射中的條目設置爲已聲明。但是，您繼續打印而不考慮。然後在第二種方法中，您（無法形容）每次遞歸到第一個方法時都會創建一個新的alreadyPrinted映射。換句話說，你的循環迴避的邏輯被打破了。

而不是修理你爲你的代碼，我會建議你去你喜歡的「數據結構和算法」教科書和索引查找「圖遍歷」。另外，這裏是我在一些網上講義發現了一個頁面：

http://underpop.online.fr/j/java/algorithims-in-java-1-4/ch05lev1sec8.htm

還有在維基百科圖的遍歷，和其他地方的東西。谷歌的「java遞歸圖遍歷」，並嘗試找到對你有意義的東西。

一般的算法是這樣的：

traverse(Node node): 
     traverse_0(node, new Set<Node>()) 

    traverse_0(Node node, Set<Node> visited): 
     if (visited.contains(node)) 
      return 
     visited.add(node) 
     for (Node child: node.children) 
      traverse_o(child, visited)

來源

2013-11-27 12:28:02

爪哇 - 遞歸 - 例外在線程「主要」 java.lang.StackOverflowError的

回答

相關問題