我目前正在学习 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);
}
}
}
}
}