巨大的性能放緩 - 矢量的問題？

我的代碼的這一部分是爲了取得一個不規則形狀的Tile對象輪廓，並通過創建一個環並減少環中的方塊的高度值，同時展開環，每次將環包括在之前的外面環（這是否有道理？）。但是，我發現我的性能下降速度很快，每個循環比前一個循環都荒謬得多。爲什麼會這樣呢？巨大的性能放緩 - 矢量的問題？

我在想這可能是因爲noobish oldEdge = theEdge;和類似的行（都是向量，我將其中一個賦值給另一個）。但即便如此，我也不理解巨大的性能下降。也許我做的事情顯然很愚蠢。有人能讓我挺身而出嗎？

請注意，oldEdge,theEdge和newEdge都是vector<Tile*> s。

int decrease = 1; 
while(decrease < 10) 
{ 
    cout << "Trying to smooth!\n"; 
    //First, modify the new edge. 
    int newHeight = 70 - decrease; 
    cout << "Height at: " << newHeight << endl; 
    for(int i = 0; i < newEdge.size(); ++i) 
    { 
     newEdge[i]->SetHeight(newHeight); 
    } 
    //Increment decrease. 
    decrease += 1; 
    //Set the oldEdge and theEdge variables. 
    oldEdge = theEdge; 
    theEdge = newEdge; 
    newEdge.clear(); 
    //Finally, find the new edge. 
    cout << "Finding new edge!\n"; 
    for(int i = 0; i < theEdge.size(); ++i) 
    { 
     //cout << "Checking a tile's neighbors!\n"; 
     for(int j = 0; j < theEdge[i]->m_AdjacentTiles.size(); ++j) 
     { 
      bool valid = true; 
      //Is this neighbor in theEdge? 
      //cout << "Is this neighbor in theEdge?\n"; 
      for(int k = 0; k < theEdge.size(); ++k) 
      { 
       if(theEdge[i]->m_AdjacentTiles[j] == theEdge[k]) 
       { 
        valid = false; 
        break; 
       } 
      } 
      //If not, is it in oldEdge? 
      if(valid) 
      { 
       //cout << "Is this neighbor in oldEdge?\n"; 
       for(int k = 0; k < oldEdge.size(); ++k) 
       { 
        if(theEdge[i]->m_AdjacentTiles[j] == oldEdge[k]) 
        { 
         valid = false; 
         break; 
        } 
       } 
      } 
      //If neither, it must be valid for continued expansion. 
      if(valid) 
      { 
       newEdge.push_back(theEdge[i]->m_AdjacentTiles[j]); 
      } 
     } 
    } 
}

來源

2011-06-28 GarrickW

爲什麼'Tile *'而不是'Tile'？你試過改變'swap'的任務，因爲你放棄了'newEdge'嗎？ –

你有一個3嵌套循環。首先看最內層的循環。例如：'theEdge [i] - > m_AdjacentTiles [j]'可以移出循環。（不要指望編譯器這樣做。）另外，我會倒數，如'for（int k = theEdge.size（）; valid && - > = 0;）'。 –

你可以給出你正在處理的size（）'數字的粗略概念嗎？並不一定會影響邏輯，但它可以幫助指導優化的位置。 – dolphy

你的算法，盡我所知，在邊緣和相鄰區塊的個數O(n^2 * m)。很可能只是小幅上漲導致漸近的表現爆炸，你會看到放緩。如果邊緣容器被排序，則可以使用二進制搜索，或者如果您能夠對它們進行哈希處理，那麼這也是一個選項。

我對您嘗試使用的算法不夠熟悉，但如果您應該使用根本不同的方法，您可能需要重新考慮。

來源

2011-06-28 18:54:47

它不是矢量，它是算法。

你有三次嵌套循環。通過放入一些調試語句來了解每次循環的次數。

來源

2011-06-28 18:56:00

巨大的性能放緩 - 矢量的問題？

回答

相關問題