圖算法 - 展望提高可伸縮性

我寫的，其計算和存儲DAG的所有路徑的算法，它很好地工作在小圖 - 但現在我希望提高它的效率，在更大的圖形運行。該算法的核心邏輯在下面的createSF（）和makePathList（）中，其他方法是助手 - 我可以看到append是一個瓶頸。不過，我想最大的幫助是設計一個可以將路徑存儲在字典中的數據結構，因爲許多路徑都是由其他路徑組成的，這是我的問題的關鍵。圖算法 - 展望提高可伸縮性

private Multiset<String> paths = new Multiset<String>();  

public Multiset<String> createSF(DAGNode n) { 

    for (DAGNode succ : n.getSuccessors()) 
     createSF(succ); 
    if (!n.isVisited()) 
     for (String s : makePathList(n)) 
      paths.put(s); 

    n.setVisited(true); 
    return paths; 
} 

private List<String> makePathList(DAGNode n) { 
    List<String> list = new ArrayList<String>(); 

    list.add(n.getLabel()); 
    for (DAGNode node : n.getSuccessors()) 
     list.addAll(append(n.getLabel(), makePathList(node))); 

return list; 
} 

private List<String> append(String s, List<String> src) { 
    List<String> ls = new ArrayList<String>(); 
    for (String str : src) 
    ls.add(s + "/" + str); 

    return ls; 
}

編輯：

我現在正在使用的路徑對象來表示路徑和具有針指向的瓶頸這兩種方法：

public List<Path> createPathList(Tree n) { 
    List<Path> list = new ArrayList<Path>(); 
    list.add(new Path(n.getNodeName())); 
    for (Tree node : n.getSuccessors()) { 
     list.addAll(append(n.getNodeName(), createPathList(node))); 
    } 
    return list; 
} 

public List<Path> append(String s, List<Path> src) { 
    List<Path> ls = new ArrayList<Path>(); 
    for (Path path : src) { 
     ls.add(new Path(path, s)); 
    } 
    return ls; 
}

麻煩的是當的曲線圖是大小M這些方法將被稱爲M次，這意味着這裏創建了很多列表......是否有一種更有效的方法來構建createPathList（）的返回值？

來源

2009-09-07 Robert

您期望如何處理您的路徑？爲什麼你將每一個存儲爲列表？ – Anna 2009-09-07 10:09:16

爲了回答這個問題，就必須要了解爲什麼你需要的路徑列表。路徑列表不會爲您提供有關DAG表示內容的任何其他信息。

如果要單獨計算的東西對於每個路徑，或計算類似總和/最小/最大所有路徑上，它也可以使用DAG自身完成。

如果你堅持節約單獨的路徑，一個選擇是你的DAG轉換成Trie的變體。另一種選擇可能是使用Lempel-Ziv表示法的一些變體。這取決於您的DAG類型，以及您期望如何處理路徑信息。

來源

2009-09-07 10:27:49 Anna

我特別需要它以多重路徑的形式，因爲我以這種形式將它用於確定熵複雜度的另一種算法。 – Robert 2009-09-07 11:49:59

在這種情況下，將路徑存儲在不同的數據結構中並不會對您有所幫助，因爲您需要全長字符串表示。 – Anna 2009-09-07 11:57:46

編輯：如果您可以更改第二個算法的參數，Lempel-Ziv（字典）樣式表示可能會節省一些空間，並且工作得更快。 – Anna 2009-09-07 12:00:04

看看掉血源代碼從Graphviz，它可能給你一些想法。

來源

2009-09-07 10:14:20

請允許我先放兩個（希望有用）評論：

我遇到了一些困難，瞭解你的代碼，因爲一些方法的名稱誤導我。從看名字，我預計別的東西。我建議一些重構：

makePathList -> createPathList // you actually create a List here 
append -> createPathList // yes, same name as above because it creates the same 
         // type of list, just with different parameters

（刪除了羅伯特的編輯之後變得過時了部分答案）

正如Margus說，一個StringBuilder追加鏈不增加替換字符串連接您的性能。編譯器可能優化String連接到StringBuilder無論如何追加（我見過這樣的字節碼）。

您可以嘗試將DAG轉換爲樹形結構。引入一個無形的根，所有節點都是直接的孩子。現在爲每個節點添加它的後繼者（孩子和/或兄弟姐妹）。現在葉的數量應該等於路徑的數量，並且從根到任何葉的每個圖都是DAG中的一條路徑。

編輯

小的提升 - 這是微優化，但至少會留下更少的垃圾：

private List<String> append(String node, List<String> allPathsStartingAfterNode) { 
    List<String> allPathsStartingAtNode = new ArrayList<String>(); 
    String nodeWithSeparator = node + "/"; 

    for (String aPathStartingAfterNode : allPathsStartingAfterNode) { 
     allPathsStartingAtNode.add(nodeWithSeparator + aPathStartingAfterNode); 
    } 

    return allPathsStartingAtNode; 
}

來源

2009-09-07 11:45:57

對不起，當我使用樹作爲輸入時留下了一些多餘的代碼 – Robert 2009-09-07 11:57:34

一個簡單的修改（這取決於你如何使用數據）可能是懶惰地加載路徑，這樣，如果你傾向於只使用幾條路徑，你甚至不會生成一些路徑。

當然，這完全取決於預期的使用

來源

2009-09-08 22:32:59 Martin

圖算法 - 展望提高可伸縮性

回答

相關問題