在我的应用程序中,我解决了给定点列表上的几何问题。
0 x0 y0
1 x1 y1
...
解决方案文件应包含点的特定顺序,这些点表示为它们的索引列表。
1
0
...
解决问题后我有一个result = std::vector<Point>()
按一定顺序的点对象 vector 以及原始点列表作为 original = std::vector<Point>()
vector 。两个 vector 自然具有相同的大小。为了生成输出文件,我检查了 result
vector 并在 original
中搜索点的索引 vector 。这是非常低效的,因为它确实需要 O(n^2)
时间。作为一个小小的改进,我做了以下事情:
std::ofstream out(filename);
std::vector<int> indices(instance.size);
std::iota(indices.begin(), indices.end(), 0);
for(auto &point : instance.result.points)
{
for(std::size_t i=0; i<indices.size(); i++)
{
int id = indices[i];
if(point == instance.points[id])
{
out << id << std::endl;
indices.erase(indices.begin()+i);
break;
}
}
}
out.close();
这让我不必重新访问我之前已经找到的要点。可悲的是,对于一个 100 万点的实例,这个过程超出了我的时间限制,我不希望导出我的解决方案比解决问题本身花费更多的时间。有没有一种方法可以有效地获取 C++ 中某个 vector 的预突变索引?如果需要,该解决方案可以使用大量内存。
最佳答案
一种易于实现且非常有效的解决方案是创建一个临时的 std::unordered_map<Point,size_t>
其中键是点,值是 original
中的位置,然后在该 map 中进行查找。关于如何使用您的(或库提供的)数据类型作为 std::unordered_map
中的键的详细信息提供here
关于c++ - 获取给定 vector 的置换索引列表的最佳方法是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56279942/