提高圖連通性計算的性能

我正在編寫一個程序來生成一個圖並檢查它是否連接。以下是代碼。這裏有一些解釋：我在隨機位置的飛機上生成了許多點。然後我連接節點，而不是僅基於接近度。我的意思是說節點更可能連接到更近的節點，這是由我在代碼（h_sq）和距離中使用的隨機變量確定的。因此，我生成了所有鏈接（對稱的，即，如果我可以與j對話，反之亦然），然後檢查BFS以查看圖形是否已連接。
我的問題是代碼似乎正常工作。然而，當節點數量大於2000時，它非常慢，爲了模擬目的，我需要多次運行這個函數。我甚至試圖用其他庫來繪製圖形，但性能是一樣的。有誰知道我怎麼可能加快一切？提高圖連通性計算的性能

感謝，

int Graph::gen_links() { 
    if(save == true) { // in case I want to store the structure of the graph 
     links.clear(); 
     links.resize(xy.size()); 
    } 

    double h_sq, d; 
    vector< vector<luint> > neighbors(xy.size()); 

    // generate links 
    double tmp = snr_lin/gamma_0_lin; 
    // xy is a std vector of pairs containing the nodes' locations 
    for(luint i = 0; i < xy.size(); i++) { 
     for(luint j = i+1; j < xy.size(); j++) { 
      // generate |h|^2 
      d = distance(i, j); 
      if(d < d_crit) // for sim purposes 
       d = 1.0; 
      h_sq = pow(mrand.randNorm(0, 1), 2.0) + pow(mrand.randNorm(0, 1), 2.0); 
      if(h_sq * tmp >= pow(d, alpha)) { 
       // there exists a link between i and j 
       neighbors[i].push_back(j); 
       neighbors[j].push_back(i); 
       // options 
       if(save == true) 
        links.push_back(make_pair(i, j)); 
      } 
     } 
     if(neighbors[i].empty() && save == false ) { 
     // graph not connected. since save=false i dont need to store the structure, 
     // hence I exit 
      connected = 0; 
      return 1; 
     } 
    } 

    // here I do BFS to check whether the graph is connected or not, using neighbors 
    // BFS code... 
    return 1; 
}

UPDATE：的主要問題似乎是循環內內的的push_back調用。在這種情況下，這是大部分時間需要花費的部分。我應該使用reserve（）來提高效率嗎？

來源

2011-04-15 Bob

你確定緩慢是由代而不是你的搜索算法造成的嗎？

圖的生成是O（n^2），你不能做太多。但是，如果至少在某些實驗中點位置是固定的，那麼您可以在某些時間交換內存。

首先，所有節點對和pow（d，alpha）的距離都可以預先計算並保存到內存中，這樣就不需要一次又一次地計算它們。 10000個節點額外的內存成本將大約800MB雙400MB和浮法..

此外，普通變量的平方之和是卡方分佈，如果我沒記錯的話..也許你可以有一些預先計算表查找準確性是否允許？最後，如果距離超過某個值時兩個節點連接的概率非常小，那麼你不需要O（n^2），並且可能只能計算那些有距離的節點對小於一些限制？

來源

2011-04-15 07:37:21 user534498

即使我固定的位置，該算法的不同運行產生不同的鏈路配置，所以我不能預先計算。 BFS引入了額外的複雜性，但如果我想檢查圖形是否連接，則無法避免它。然而，通過使用代碼玩一下，似乎這兩個for循環佔用了大部分時間，原因是平均而言，如果圖形斷開連接，BFS可能會終止 – Bob 2011-04-15 07:41:46

作爲第一步，您應該嘗試使用內部和外部向量的保留。

如果這不會使性能達到您的預期，我相信這是因爲內存分配仍在發生。

在類似的情況下，有一個方便的類，llvm :: SmallVector（在谷歌找到它）。它提供了一個預分配項很少的向量，因此您可以減少每個向量一個分配的數量。它在預分配空間中的項目用完時仍會增長。

所以： 1）檢查項目你平均的載體具有運行時（我說的是內部和外部的載體） 2）在LLVM將:: SmallVector用的預分配的數量這樣的大小（如向量在堆棧上分配，您可能需要增加堆棧大小，或者如果受限於可用堆棧內存，則減少預分配）。

約SmallVector的另一個好處是，它具有幾乎相同的界面的std ::向量（可以很容易地把代替它）

來源

2012-04-10 14:08:10

提高圖連通性計算的性能

回答

相關問題