構建緩慢的路徑列表

我構建了一個代表樹中根節點路徑的散列列表。我的功能可行，但它們在大型樹結構上的速度非常慢 - 有沒有更好的方法？我試過在一個函數中構建列表，但我得到了獨特的哈希，我不想要它們。構建緩慢的路徑列表

public ArrayList<Integer> makePathList(AbstractTree<String> tree){ 
    StringBuilder buffer = new StringBuilder(); 
    ArrayList<Integer> pl = new ArrayList<Integer>(); 
    ArrayList<StringBuilder> paths = getPaths(tree, buffer); 
    for(StringBuilder sb : paths){ 
     pl.add(sb.toString().hashCode()); 
    } 

    return pl; 
} 

public ArrayList<StringBuilder> getPaths(AbstractTree<String> tree, StringBuilder parent){ 
     ArrayList<StringBuilder> list = new ArrayList<StringBuilder>(); 
     parent.append("/"); 
     parent.append(tree.getNodeName()); 
     list.add(new StringBuilder(parent)); 

     if (!tree.isLeaf()){  
      int i = 0; 
      Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
      while (i < tree.getChildren().size()){ 
       list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
       i++; 
      } 
     } 
     return list; 
}

UPDATE：

馬爾欽的建議，使樹遍歷期間散列給出了錯誤的答案，但也許這是我做的方式？

public ArrayList<Integer> getPaths(AbstractTree<String> tree, StringBuilder parent){ 
    ArrayList<Integer> list = new ArrayList<Integer>(); 

    parent.append("/"); 
    parent.append(tree.getNodeName()); 
    list.add(new StringBuilder(parent).toString().hashCode()); 

    if (!tree.isLeaf()){  
     int i = 0; 
     Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size()){ 

      list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
      i++; 
     } 
    } 
    return list; 
}

來源

2009-07-24 Robert

我認爲你的主要問題是你正在產生的重複數據量：對於樹的每一片葉子，你將製作一個通向該葉片的整個路徑的副本並計算該路徑的散列值。即如果在一個頂級節點下有50,000張葉子，則該節點的路徑名稱將被複制50,000次，並且其散列計算50,000次。

如果您可以組織您的數據，以便共享路徑前綴被重新用作樹葉之間的引用，並且對這些前綴進行散列計算可以被緩存和重用，您可以大幅減少要完成的實際工作量。

來源

2009-07-24 12:20:20

jvisualvm表明性能瓶頸在哪裏？

來源

2009-07-24 12:07:33

我不知道如何使用jvisualvm，但我使用100MB XML樹計時了這些方法。使得路徑... \t做[3614ms] 創建的散列碼... \t做[962ms] \t共完成[4576ms] – Robert 2009-07-24 12:13:04

它將無法識別的核心問題在這種情況下，但你真的應該學會如何使用visualvm等分析器。這是攻擊性能問題的唯一專業方式。 – 2009-07-24 12:24:20

我強烈建議學習如何使用分析器。 jvisualvm是最低的掛果。 – 2009-07-24 12:32:07

你首先創建一個所有路徑的列表，然後一旦你有他們所有你計算哈希。所有這些路徑的列表大小是O（n^3）（有O（n^2）個路徑，每個O（n）長）爲什麼？爲什麼不在你遍歷樹的時候計算哈希？通過這種方式，您可以在整個時間複雜度範圍內取得整個n。

適當溶液的代碼（結果在整數值列表傳遞結束）：

public void getPaths(AbstractTree<String> tree, StringBuilder parentPath, 
    List<Integer> list) 
    StringBuilder newPath = parentPath.clone(); 
    newPath.append("/"); 
    newPath.append(tree.getNodeName()); 
    list.add(newPath.toString().hashCode()); 
    if (!tree.isLeaf()){  
    Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
    for (AbstractTree<String> child : tree.getChildren()){ 
     getPaths(child, newPath, list) 
    } 
    } 
}

這仍然是O（n^2）。這是因爲O（n^2）值的字符串散列化（每個節點的路徑長度與其深度成比例），如果你有一個給定節點只需要散列的散列，你甚至可以把它放到O（N）一個散列其父母的路徑，並以某種方式修改它。

Furhter優化包括： - 並行樹遍歷 - 使用更加智能散列（即孩子的散列是孩子的功能，並且父路徑的散列，而不是整個父路徑）。

來源

2009-07-24 12:20:30 Marcin

我覺得複雜性還是一樣的。無論你使用內聯創建哈希（O（n^2））還是在遞歸（O（n^2 + n）= O（n^2））之後執行它。尋找快速方法的唯一機會是在另一個地方完成一些工作。例如您可以在插入節點時對散列路徑進行散列處理，並僅在其他點收集所有散列。

來源

2009-07-24 14:27:57

構建緩慢的路徑列表

回答

相關問題