巨大なパフォーマンスの低下 - 問題のベクトルですか？

Question

私のコードのこの部分は、Tileオブジェクトの不規則な形の輪郭を取り、リングを作成し、リング内のタイルの高さ値を減らしながらリングを展開して、直前のタイルリング（それは理にかなっていますか？）しかし、私が見つけたのは、大規模なパフォーマンスの低下が起こっていることです。各ループは以前よりも馬鹿げて遅くなっています。なぜこれができますか？

私はそれがnoobish oldEdge = theEdge;とそれに類する行（両方ともベクトルであり、私はもう一方を割り当てている）のためかもしれないと思っていました。しかし、それでも、私は巨大なパフォーマンス低下を理解していません。たぶん私は明らかに愚かな何かをしている。誰かが私をまっすぐにすることができます

なお、oldEdge,theEdgeおよびnewEdgeはすべてvector<Tile*>である。

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]); 
      } 
     } 
    } 
} 

Answer 1

あなたのアルゴリズムでは、私が言うことができる最善のように、エッジと隣接するタイルの数でO(n^2 * m)です。ほとんどの場合、わずかな増加は漸近的なパフォーマンスを爆発させ、あなたは減速を見ます。エッジコンテナがソートされている場合は、代わりにバイナリ検索を使用するか、代わりにハッシュすることができればオプションになります。

私はあなたが使用しようとしているアルゴリズムに慣れていませんが、根本的に異なる手法を使用しなければならない場合は、もう一度見直したいかもしれません。

Answer 2

これはベクトルではなく、アルゴリズムです。

あなたはそこに3回ネストされたループを持っています。いくつかのデバッグステートメントを入れて、各ループを何度実行するかを調べます。