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

Question

我有一个看似非常基本的问题，但它是在“每个 CPU 滴答声都很重要”(这是将在 super 计算机上使用的更大算法的一部分)的上下文中提出的。

问题很简单:对 unsigned long 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 使实际的排序标准更容易找到，因此您无需为代码可读性而仔细选择名称。