C++:对数字列表及其索引进行排序的最快方法

Question

我有一个看似非常基本的问题,但它是在"每个CPU滴答计数"的背景下(这是将在超级计算机上使用的更大算法的一部分).

问题很简单:对无符号长long int数及其原始索引列表进行排序的最快方法是什么？(开头时,unsigned long long int数字是完全随机的.)

Example :
Before
Numbers: 32 91 11 72
Indexes: 0 1 2 3
After
Numbers: 11 32 72 91
Indexes: 2 0 3 1 

通过"最快的方式",我的意思是:使用什么算法:std :: sort,C qsort,或网上提供的其他排序算法？使用什么容器(C数组,std :: vector,std :: map ...)？如何同时对索引进行排序(使用结构,std :: pair,std :: map ...)？

非常感谢你 !

编辑:要排序多少元素？ - >通常4Go数字

Answer 1

明显的出发点是为其operator<定义的结构:

struct data { 
    unsigned long long int number;
    size_t index;
};

struct by_number { 
    bool operator()(data const &left, data const &right) { 
        return left.number < right.number;
    }
};

...和一个用于保存数据的std :: vector:

 std::vector<data> items;

并std::sort进行排序:

 std::sort(items.begin(), items.end(), by_number());

简单的事实是,普通容器(等等)足够高效,使用它们不会使您的代码效率大大降低.你可以通过以不同的方式写一些部分来做得更好,但你可能很容易做得更糟.从可靠和可读开始,并测试 - 不要(尝试)过早优化.

编辑:当然在C++ 11中,您可以使用lambda表达式代替:

std::sort(items.begin(), items.end(), 
          [](data const &a, data const &b) { return a.number < b.number; });

这通常更方便编写.可读性取决于 - 对于像这样简单的东西,我会说它sort ... by_number非常易读,但这在很大程度上取决于您给比较运算符的名称.lambda使实际的排序标准更容易找到,因此您无需仔细选择名称以使代码可读.

Answer 2

std::pair并且std::sort理想地满足您的要求:如果您将值放入pair.first和索引中pair.second,您可以简单地调用s sort的向量pair,如下所示:

// This is your original data. It does not need to be in a vector
vector<long> orig;
orig.push_back(10);
orig.push_back(3);
orig.push_back(6);
orig.push_back(11);
orig.push_back(2);
orig.push_back(19);
orig.push_back(7);
// This is a vector of {value,index} pairs
vector<pair<long,size_t> > vp;
vp.reserve(orig.size());
for (size_t i = 0 ; i != orig.size() ; i++) {
    vp.push_back(make_pair(orig[i], i));
}
// Sorting will put lower values ahead of larger ones,
// resolving ties using the original index
sort(vp.begin(), vp.end());
for (size_t i = 0 ; i != vp.size() ; i++) {
    cout << vp[i].first << " " << vp[i].second << endl;
}