c++ - 在 Debug模式下，priority_queue变得非常慢

我目前正在为游戏编写A *寻路算法，并且遇到了关于 priority_queue 的非常奇怪的性能问题。

我正在使用典型的“开放节点列表”，在其中存储找到的但尚未处理的节点。这被实现为指向PathNodeRecord对象的指针的 STL priority_queue (openList)指针，该指针存储有关访问的节点的信息。它们按到达那里的估计费用(estimatedTotalCost)排序。

现在我注意到，每当调用寻路方法时，相应的AI线程就会完全卡住，并花费几(〜5)秒来处理算法并计算路径。随后，我使用VS2013分析器查看了花了这么长时间的原因，原因和地点。

事实证明，将推送到打开列表(优先级队列)并从中弹出是非常耗时的。我不是STL容器的专家，但是我以前从未对它们的效率有任何疑问，这对我来说很奇怪。

奇怪的是，这仅在使用VS的“调试”构建配置时发生。 “发布” session 。对我来说工作正常，并且时间恢复了正常。

我在这里做的事情根本上是错的，还是为什么priority_queue对我来说如此糟糕？目前的情况对我来说是无法接受的，因此，如果我不能尽快解决它，我将不得不退一步，使用一个更简单的容器并将其手动插入正确的位置。

任何可能导致这种情况发生的指示都将非常有帮助!

。

这是探查器显示给我的片段:

http://i.stack.imgur.com/gEyD3.jpg

。

代码部分:

这是寻路算法的相关部分，它将循环打开列表，直到没有打开的节点为止:

// set up arrays and other variables
PathNodeRecord** records = new PathNodeRecord*[graph->getNodeAmount()]; // holds records for all nodes
std::priority_queue<PathNodeRecord*> openList; // holds records of open nodes, sorted by estimated rest cost (most promising node first)


// null all record pointers
memset(records, NULL, sizeof(PathNodeRecord*) * graph->getNodeAmount());


// set up record for start node and put into open list
PathNodeRecord* startNodeRecord = new PathNodeRecord();
startNodeRecord->node = startNode;
startNodeRecord->connection = NULL;
startNodeRecord->closed = false;
startNodeRecord->costToHere = 0.f;
startNodeRecord->estimatedTotalCost = heuristic->estimate(startNode, goalNode);

records[startNode] = startNodeRecord;
openList.push(startNodeRecord);



// ### pathfind algorithm ###

// declare current node variable
PathNodeRecord* currentNode = NULL;

// loop-process open nodes
while (openList.size() > 0) // while there are open nodes to process
{
    // retrieve most promising node and immediately remove from open list
    currentNode = openList.top();
    openList.pop(); // ### THIS IS, WHERE IT GETS STUCK


    // if current node is the goal node, end the search here
    if (currentNode->node == goalNode)
        break;


    // look at connections outgoing from this node
    for (auto connection : graph->getConnections(currentNode->node))
    {
        // get end node
        PathNodeRecord* toNodeRecord = records[connection->toNode];

        if (toNodeRecord == NULL) // UNVISITED -> path record needs to be created and put into open list
        {
            // set up path node record
            toNodeRecord = new PathNodeRecord();
            toNodeRecord->node = connection->toNode;
            toNodeRecord->connection = connection;
            toNodeRecord->closed = false;
            toNodeRecord->costToHere = currentNode->costToHere + connection->cost;
            toNodeRecord->estimatedTotalCost = toNodeRecord->costToHere + heuristic->estimate(connection->toNode, goalNode);

            // store in record array
            records[connection->toNode] = toNodeRecord;

            // put into open list for future processing
            openList.push(toNodeRecord);
        }
        else if (!toNodeRecord->closed) // OPEN -> evaluate new cost to here and, if better, update open list entry; otherwise skip
        {
            float newCostToHere = currentNode->costToHere + connection->cost;

            if (newCostToHere < toNodeRecord->costToHere)
            {
                // update record
                toNodeRecord->connection = connection;
                toNodeRecord->estimatedTotalCost = newCostToHere + (toNodeRecord->estimatedTotalCost - toNodeRecord->costToHere);
                toNodeRecord->costToHere = newCostToHere;
            }
        }
        else // CLOSED -> evaluate new cost to here and, if better, put back on open list and reset closed status; otherwise skip
        {
            float newCostToHere = currentNode->costToHere + connection->cost;

            if (newCostToHere < toNodeRecord->costToHere)
            {
                // update record
                toNodeRecord->connection = connection;
                toNodeRecord->estimatedTotalCost = newCostToHere + (toNodeRecord->estimatedTotalCost - toNodeRecord->costToHere);
                toNodeRecord->costToHere = newCostToHere;

                // reset node to open and push into open list
                toNodeRecord->closed = false;
                openList.push(toNodeRecord); // ### THIS IS, WHERE IT GETS STUCK
            }
        }
    }


    // set node to closed
    currentNode->closed = true;
}

这是我的PathNodeRecord，它带有“less”运算符重载以允许在priority_queue中进行排序:

namespace AI
{
    struct PathNodeRecord
    {
        Node node;
        NodeConnection* connection;

        float costToHere;
        float estimatedTotalCost;

        bool closed;



        // overload less operator comparing estimated total cost; used by priority queue
        // nodes with a higher estimated total cost are considered "less"
        bool operator < (const PathNodeRecord &otherRecord)
        {
            return this->estimatedTotalCost > otherRecord.estimatedTotalCost;
        }
    };
}

最佳答案

std::priority_queue<PathNodeRecord*> openList
我认为原因是您有一个的priority_queue指针指向PathNodeRecord。
并且没有为指针定义顺序。

尝试先将其更改为std::priority_queue<PathNodeRecord>，如果有区别，那么您所需要的只是传递自己的比较器，该比较器知道如何比较PathNodeRecord的指针，它只会首先取消引用指针，然后进行比较。

编辑:
疯狂猜测为什么您的执行时间会非常缓慢，我认为这些指针是根据其地址进行比较的。从内存中的一点开始分配地址，然后递增。
这样就导致了堆的极端情况(数据结构中的堆而不是内存部分)，因此堆实际上是一个列表(一棵树，其中每个节点都有一个子节点，依此类推)。
因此您的操作花费了线性时间，再次只是一个猜测。