C ++：最快的排序数量和它们的索引列表的方式 [英] C++ : 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 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 

通过最快的方式，我的意思是：用什么算法：性病::排序，C的qsort或其他可在网络上的排序算法？用什么容器（C数组的std ::矢量，性病::地图...）？如何在同一时间索引（使用结构，标准::对，性病::地图...）进行排序？

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

EDIT : how many element to sort ? -> typically 4Go of numbers

推荐答案

最明显的起点是具有结构运营商的LT; 为它定义的：

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 ::向量来保存数据：

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

 std::vector<data> items;

和的std ::排序来进行排序：

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

一个简单的事实是，在正常的容器（等等）是充分有效的利用它们不会使你的code大大效率较低。您的也许的是能够做到通过编写一些部分以不同的方式更好，但你可能会有关的轻松做到雪上加霜。开始由固体和可读性，和测试 - 不（尝试）优化prematurely

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 EX pression来代替：

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; });

这通常是一个更方便一点来写。可读性取决于 - 简单的东西就是这样，我想说排序... by_number 是pretty的可读性，但是这取决于（严重），你给的名字到比较运算符。拉姆达使得实际的分类标准更容易被发现，所以你并不需要选择一个名字精心为code是可读的。

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.

这篇关于C ++：最快的排序数量和它们的索引列表的方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！