排序数字及其索引的最快方法 [英] Fastest way to sort a list of number and their index

问题描述

我有一个看似很基本的问题，但这是在每个CPU滴答声都非常重要"的情况下进行的(这是将在超级计算机上使用的较大算法的一部分).

I have a question that could seem very basic, but it is in a context where "every CPU tick counts" (this is a part of a larger algorithm that will be used on supercomputers).

问题很简单:对无符号long long int数字及其原始索引进行排序的最快方法是什么? (一开始，无符号long long int数是完全随机的顺序.)

The problem is quite simple : what is the fastest way to sort a list of unsigned long long int numbers and their original indexes ? (At the beginning, the unsigned long long int numbers are in a completely random order.)

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 ...)?

By "fastest way", I mean : what algorithm to use : std::sort, C qsort, or another sorting algorithm available on the web ? What container to use (C array, std::vector, std::map...) ? How to sort the indexes at the same time (use structures, std::pair, std::map...) ?

要排序多少个元素? ->通常为4Go数字

How many element to sort ? -> typically 4Go of numbers

推荐答案

显而易见的起点是为它定义了operator<的结构:

The obvious starting point would be a structure with operator< defined for it:

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:

...and an std::vector to hold the data:

 std::vector<data> items;

和std::sort进行排序:

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

一个简单的事实是，普通容器(等等)足够高效，因此使用它们不会使您的代码效率大大降低.通过使用不同的方式编写某些部分，您可能可以做得更好，但是您可能同样容易做得更糟.从扎实，易读的内容开始，然后进行测试-不要(试图)过早地进行优化.

The simple fact is, that the normal containers (and such) are sufficiently efficient that using them doesn't make your code substantially less efficient. You might be able to do better by writing some part in a different way, but you might about as easily do worse. Start from solid and readable, and test -- don't (attempt to) optimize prematurely.

当然，在C ++ 11中，您可以改用lambda表达式:

of course in C++11, you can use a lambda expression instead:

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

这通常更方便编写.可读性取决于-对于这样的简单事情，我想说sort ... by_number可读性很强，但这(很大程度上)取决于您给比较运算符提供的名称. lambda使实际的排序标准更易于查找，因此您无需仔细选择名称即可使代码可读.

This is generally a little more convenient to write. Readability depends--for something simple like this, I'd say sort ... by_number is pretty readable, but that depends (heavily) on the name you give to the comparison operator. The lambda makes the actual sorting criteria easier to find, so you don't need to choose a name carefully for the code to be readable.

这篇关于排序数字及其索引的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！