快速排序数字列表及其索引的最快方法

Question

我有一个问题，可能看起来非常基础，但它是在“每个CPU时钟都很重要”的上下文中（这是将在超级计算机上使用的更大算法的一部分）。

问题相当简单：如何以最快的方式对无符号长整型数字和它们的原始索引进行排序？（起初，无符号长整型数字是完全随机的。）

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等）？

需要排序多少个元素？-> 通常是4GB的数字。

- Vincent

---

要排序的元素数量（最大值）是多少？ - Paul R

C数组和std::vector之间，结构体和std::pair之间不应该有任何区别。 - Mark Ransom

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使得实际排序标准更容易找到，因此您不需要精心选择名称才能使代码易读。

- Jerry Coffin

---

+1 我甚至会建议使用 map，除非分析表明不应该这样做。 - Mark B

@MarkB：这肯定是一种可能性，特别是如果他需要在插入/删除操作中维护顺序。 - Jerry Coffin

by_number 应该实现 operator()（而不是 operator<）吗？ - Branko Dimitrijevic

@BrankoDimitrijevic：哎呀，非常正确。已经修复--谢谢。 - Jerry Coffin

Answer 2

std::pair 和 std::sort 是完美符合您需求的：如果您将值放入pair.first，索引放入pair.second，则可以在pair向量上简单地调用sort，如下所示：

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

- Sergey Kalinichenko

Answer 3

std::sort已被证明比旧的qsort更快，因为它没有间接引用和内联关键操作的可能性。

std::sort的实现很可能高度优化且难以超越，但并非不可能。如果您的数据是固定长度且较短，您可能会发现基数排序更快。 Timsort相对较新，对Python提供了良好的结果。

您可以将索引数组与值数组分开，但我认为额外的间接级别将证明是速度杀手。最好将它们放在一个结构体或std::pair中。

像任何速度关键的应用程序一样，您必须尝试一些实际的实现并将它们进行比较，以确切知道哪个最快。

- Mark Ransom

---

Timsort 利用容器通常是无意中部分排序的事实。如果容器是真正随机的，那么 Timsort 将比传统的排序算法稍微慢一些。请参见此处的第 54 页幻灯片（libc++ 没有特别使用 Timsort，但它使用了类似的思想）。 - bames53

@bames53 这就是为什么我试图强调基准测试的重要性。没有一种适用于所有情况的通用建议。 - Mark Ransom

Timsort在Python和Java中都有很好的表现。它非常快速，不仅适用于部分排序的数据。 - user1277476

Answer 4

或许将数字和索引分开，然后仅对索引进行排序是值得的，像这样：

#include <vector>
#include <algorithm>
#include <iostream>

void PrintElements(const std::vector<unsigned long long>& numbers, const std::vector<size_t>& indexes) {

    std::cout << "\tNumbers:";
    for (auto i = indexes.begin(); i != indexes.end(); ++i)
        std::cout << '\t' << numbers[*i];
    std::cout << std::endl;

    std::cout << "\tIndexes:";
    for (auto i = indexes.begin(); i != indexes.end(); ++i)
        std::cout << '\t' << *i;
    std::cout << std::endl;

}

int main() {

    std::vector<unsigned long long> numbers;
    std::vector<size_t> indexes;

    numbers.reserve(4); // An overkill for this few elements, but important for billions.
    numbers.push_back(32);
    numbers.push_back(91);
    numbers.push_back(11);
    numbers.push_back(72);

    indexes.reserve(numbers.capacity());
    indexes.push_back(0);
    indexes.push_back(1);
    indexes.push_back(2);
    indexes.push_back(3);

    std::cout << "BEFORE:" << std::endl;
    PrintElements(numbers, indexes);

    std::sort(
        indexes.begin(),
        indexes.end(),
        [&numbers](size_t i1, size_t i2) {
            return numbers[i1] < numbers[i2];
        }
    );

    std::cout << "AFTER:" << std::endl;
    PrintElements(numbers, indexes);

    return EXIT_SUCCESS;

}

这将打印：

BEFORE:
        Numbers:        32      91      11      72
        Indexes:        0       1       2       3
AFTER:
        Numbers:        11      32      72      91
        Indexes:        2       0       3       1

这种排序思想的前提是被排序的元素相对较小，因此在排序过程中移动速度快。然而，在现代CPU上，对于numbers的间接访问可能会破坏缓存，所以我建议在做出最终决定之前，在真实数据量上进行基准测试。

- Branko Dimitrijevic

Answer 5

这将在超级计算机上使用吗？

如果是这样，您可能需要研究并行排序算法。这只对排序大数据集有意义，但如果需要，获得的胜利是巨大的。

- btilly

Answer 6

使用 std::vector 和 std::sort，这应该提供最快的排序方法。要查找原始索引，请创建一个结构体。

struct A {
    int num;
    int index;
}

然后为排序创建自己的比较谓词，以比较结构体中的数字。

struct Predicate {
    bool operator()(const A first, const A second) {
        return first.num < second.num;
    }
}

std::sort(vec.begin(), vec.end(), Predicate())

std::sort(vec.begin(), vec.end(), Predicate())

- andre

Answer 7

struct SomeValue
{
    unsigned long long val;
    size_t index;
    bool operator<(const SomeValue& rhs)const
    { 
       return val < rhs.val;
    }
}

 #include <algorithm>
 std::vector<SomeValue> somevec;
 //fill it...
 std::sort(somevec.begin(),somevec.end());

- clanmjc

Answer 8

你可能会发现 这篇文章 很有趣。我建议从STL的sort开始，然后再尝试在其基础上进行改进。我不确定您是否可以在这台超级计算机上使用C++11编译器（例如gcc4.7），但我建议使用std :: futures和std :: threads的std :: sort可以在可维护的方方式中使问题并行化。

这里是另一个问题，比较了std :: sort和qsort。

最后，这里有一篇文章来比较并行算法的性能，它发表在Dr. Dobb's上。

- Carl