c++ - 在A*路径查找中,C++ 性能问题具有 std::map 性能

  显示原文与译文双语对照的内容
0 0

我目前正在学习 C++,这样我就将A*路径查找算法转换为 python,以前写入 C++ 。 尽管我不知道 C++ 库中的所有不同类型的数据类型,但我还是决定进入。

编写完程序后,C++ 版本运行的速度比 python 版本( 该程序使用 std::map 而不是 python 字典来存储移动开销) 慢。 无论你是否知道路径查找,有人可以查看我的代码并说明为什么它运行得非常低效。

我运行 Visual Studios 分析器检查什么是低效的( 我知道队列可以用来加快搜索速度,但要记住在 python 中运行了相同的代码,没有优先级队列。) 。 似乎几乎所有的时间都被 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);
 }
 }
 }
 }
}
时间: 原作者:

0 0

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

原作者:
...