我的这部分代码旨在采用不规则形状的轮廓 Tile
对象并循环创建一个环并降低环中瓷砖的高度值,同时每次扩大环以包括前一个环外的那些瓷砖(这有意义吗?)。然而,我发现我的性能大幅下降,每个循环都比之前的循环慢得离谱。为什么会这样?
我在想这可能是因为菜鸟 oldEdge = theEdge;
和可比较的线(都是 vector ,我将一个分配给另一个)。但即便如此,我还是不明白巨大的性能下降。也许我正在做一些明显愚蠢的事情。有人可以让我直截了当吗?
请注意 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]);
}
}
}
}
最佳答案
据我所知,您的算法在边和相邻图 block 的数量上是 O(n^2 * m)
。很可能只是一个小的增加导致渐近性能爆炸,你会看到减速。如果边缘容器已排序,您可以改用二进制搜索,或者如果您能够对它们进行哈希处理,那也是一种选择。
我对您尝试使用的算法还不够熟悉,但如果您应该使用一种根本不同的方法,您可能想重新考虑一下。
关于c++ - 巨大的性能下降 - vector 问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6510921/