巨大的性能下降 - 向量是否是问题？

Question

我的代码的这一部分旨在接受一个不规则形状的Tile对象轮廓，并循环创建一个环，每次扩展环以包含刚刚超出前一个环的那些瓷砖，并降低环中瓷砖的高度值（这有意义吗？）。 然而，我发现每次循环都会出现巨大的性能下降，比之前的循环要慢得多。 为什么会这样呢？

我认为问题可能出在新手式的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]);
            }
        }
    }
}

- GarrickW

---

为什么要使用 Tile* 而不是 Tile？你尝试过将赋值更改为 swap 吗，因为你无论如何都会丢弃 newEdge？ - Konrad Rudolph

你有一个三层嵌套的循环。首先看内部循环。例如：theEdge[i]->m_AdjacentTiles[j]可以移出循环。（不要指望编译器会这样做。）此外，我会倒序计数，如for(int k = theEdge.size(); valid && --k >= 0;)。 - Mike Dunlavey

你能大概说明一下你处理的 size() 数字的范围吗？虽然这并不一定影响逻辑，但它可以帮助指导优化方向。 - dolphy

你尝试过对代码进行性能分析吗？ - Gnawme

我不确定这是否是答案，但如果你在调试模式下对 std 容器（std::map、std::vector 等）进行速度测量，读数将会偏离。 - Valmond

Answer 1

据我所知，您的算法在边缘数量和相邻瓷砖方面的时间复杂度为O(n^2 * m)。很可能只有一点点增加就会导致渐近性能崩溃并看到减速。如果排序边缘容器，则可以使用二进制搜索，或者如果您能够对其进行哈希，则也是一种选择。

我不太熟悉您尝试使用的算法，但您可能需要重新考虑是否应该使用根本上不同的方法。

- Mark B

Answer 2

问题不在于向量，而在于算法。

您在其中有一个三重嵌套循环。添加一些调试语句以查找每个循环运行的次数。

- Peter Alexander