A*路径查找中std::map性能的C++性能问题。

Question

我目前正在学习C++，在这样做的过程中，我正在将我之前用Python语言编写的A*路径查找算法转换为C++。尽管对C++库中所有不同类型的数据类型了解不多，但我还是决定一头扎进去。

编写完程序后，C++版本的运行速度要比Python版本慢得多(该程序使用std::map而不是Python字典来存储移动成本)。不管你是否知道路径查找，有没有可能有人看着我的代码，告诉我为什么它的运行效率如此之低？

我运行了visual studios profiler来检查效率如此之低的原因(我知道队列可以用来加快搜索速度，但请记住，在Python语言中，使用相同的代码且没有优先级队列时，这种方法的运行速度要快x50倍)。似乎几乎所有的时间都由std::map []运算符使用：

Function Name   Total CPU (%) -> 88.01 %
+ std::map<std::pair<int,int>,int,std::less<std::pair<int,int>>,
  std::allocator<std::pair<std::pair<int,int> const ,int> > >::
  operator[]

我的代码：

    void findPath(pair<int, int> startLocation, pair<int, int> endLocation){

    vector<pair<int, int>> openSet;
    vector<pair<int, int>> closedSet;
    openSet.push_back(startLocation);

    map<pair<int, int>, pair<int, int>> cameFrom;
    map<pair<int, int>, int> gCosts;
    map<pair<int, int>, int> fCosts;

    gCosts[startLocation] = 0;
    fCosts[startLocation] = heuristic(startLocation, endLocation);

    pair<int, int> currentNode;
    while (openSet.size() > 0){

        currentNode = openSet[0];

        for (std::vector<pair<int, int>>::iterator it = openSet.begin(); it != openSet.end(); ++it){
            pair<int, int> node = *it;
            if (fCosts[node] < fCosts[currentNode])
                currentNode = node;
        }

        if (DEBUG){
            cout << "Current Node: " << currentNode.first << " " << currentNode.second << endl;
        }

        if (currentNode == endLocation){
            break;
        }

        openSet.erase( remove(openSet.begin(), openSet.end(), currentNode), openSet.end() );
        closedSet.push_back(currentNode);

        vector<pair<int, int>> neighbors = getNeighbors(currentNode);

        for (std::vector<pair<int, int>>::iterator it = neighbors.begin(); it != neighbors.end(); ++it){
            pair<int, int> neighbor = *it;
            if (std::find(closedSet.begin(), closedSet.end(), neighbor) != closedSet.end()) {
                continue;
            }

            int possiblegCost = gCosts[currentNode] + heuristic(currentNode, neighbor);

            bool inOpenSet = find(openSet.begin(), openSet.end(), neighbor) != openSet.end();
            if (!inOpenSet || (possiblegCost < gCosts[neighbor])) {
                cameFrom[neighbor] = currentNode;
                gCosts[neighbor] = possiblegCost;
                fCosts[neighbor] = possiblegCost + heuristic(neighbor, endLocation);

                /*if (DEBUG){
                console() << "Modifying neighbor: " << neighbor.first << "," << neighbor.second << " Costs of: "
                << gCosts[neighbor] << " " << fCosts[neighbor] << endl;
                }*/

                if (!inOpenSet){
                    openSet.push_back(neighbor);
                }
            }

        }
    }

}

Answer 1

使用std::map::find和/或std::map::emplace/std::map::emplace_hint可能比使用std::map operator[]快得多