2

我试图使用 STL sort() 函数按存储在地图中的值对对象向量进行排序。令我大吃一惊的是，我的算法是在二次时间中运行的。我尽可能地简化了它，试图找出一个明显的错误，但无济于事。这是简化版：

#include <map>
#include <vector>
#include <algorithm>

using namespace std;

struct a{
  map<a*,float> vals;
  bool operator()(a* a1, a* a2){return (vals[a1]>vals[a2]);}
  void asort();
};

void a::asort(){
  vector<a*> v;
  map<a*,float>::iterator it = vals.begin();
  for(;it!=vals.end();it++){v.push_back((*it).first);}
  sort(v.begin(),v.end(),*this);
}

int main(){
  a a0;
  int imax=8000;
  for(int i=0;i<imax;i++){a0.vals[new a]=rand();}
  a0.asort();
}

当我运行 imax=2000、4000、8000 时，分别需要大约 1s、4s、18s。这怎么可能？为什么我没有得到预期的 imax*log(imax) 依赖？我对C ++的经验有限，请帮助！谢谢！

更新：感谢 Xeo、Rick 和所有回复的人。正如 Xeo 和 Rick 解释的那样，问题在于比较器（在我的情况下struct a是包含值的映射）在每次比较时都被复制，因此计算复杂度O(imax^2 log(imax))。我可以看到的一种解决方法（因此对我的代码的更改是最小的）是使用指向地图的指针，即map<a*,float>* vals，而不是map<a*,float> vals. 然后避免了地图复制，复杂度又回到O(imax log(imax)). 非常感谢！

4

2 回答 2

8

std::sort按值取谓词，意义

sort(v.begin(),v.end(),*this);
//                     ^^^^^

将复制包含的地图。

接下来，您将在比较期间进行两次地图查找，即O(log N)，而预计这pred(a,b)是一个恒定操作。

您可以通过为 (C++11) 定义单独的比较器std::sort并使用std::unordered_map(C++11) 来解决此问题。

于 2012-10-10T03:07:19.217 回答
1

地图已经排序。std::sort可能基于 Quicksort，其最坏情况下的性能是在输入预排序时。

于 2012-10-10T03:05:33.633 回答