Огромное замедление производительности - векторы проблемы?

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

Answer 1

Ваш алгоритм, насколько я могу судить, равен O(n^2 * m) по количеству ребер и соседних плиток.Скорее всего, небольшое увеличение вызывает асимптотическую производительность, и вы видите замедление.Если бы граничные контейнеры были отсортированы, вы могли бы вместо этого использовать бинарный поиск, или если бы вы могли их хешировать, это тоже было бы вариантом.

Я недостаточно знаком с алгоритмом, который вы пытаетесь использоватьиспользовать, но вы можете вернуться к нему, если есть принципиально другой подход, который вы должны использовать.

Answer 2

Это не вектор, это алгоритм.

У вас есть трехкратный вложенный цикл.Поместите несколько операторов отладки, чтобы узнать, сколько раз он проходит через каждый цикл.