9

我有一个看起来非常基本的问题，但它是在“每个 CPU 滴答计数”的上下文中（这是将在超级计算机上使用的更大算法的一部分）。

问题很简单：对 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 的数字

4

8 回答 8

16

显而易见的起点是为其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 使实际的排序标准更容易找到，因此您无需仔细选择名称即可使代码可读。

于 2012-04-23T20:45:58.323 回答
5

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

// 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;
}
于 2012-04-23T20:51:28.980 回答
3

std::sortqsort由于缺乏间接性和内联关键操作的可能性，已被证明比旧的更快。

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

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

与任何速度关键的应用程序一样，您必须尝试一些实际的实现并比较它们以确定哪个是最快的。

于 2012-04-23T20:53:59.910 回答
3

可能值得将数字和索引分开，然后对索引进行排序，如下所示：

#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对缓存的影响可能会破坏这些收益，因此我建议在最终决定使用它之前对实际数据量进行基准测试。

于 2012-04-23T23:02:45.720 回答
1

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

struct A {
    int num;
    int index;
}

然后为比较结构中的 num 的排序创建自己的比较谓词。

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

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

于 2012-04-23T20:43:34.413 回答
1 
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());
于 2012-04-23T20:45:49.623 回答
1

这将用于超级计算机？

在这种情况下，您可能需要研究并行排序算法。这仅对对大型数据集进行排序有意义，但如果你需要它，那将是巨大的胜利。

于 2012-04-23T21:54:29.637 回答
0

您可能会发现这是一本有趣的读物。我会从 STL 的排序开始，然后如果可以的话，我会尝试改进它。我不确定你是否可以在这台超级计算机上访问 C++11 编译器（如 gcc4.7），但我建议 std::sort 与 std::futures 和 std::threads 会让你很关于以可维护的方式并行化问题的一些方法。

这是另一个将 std::sort 与 qsort 进行比较的问题。

最后，还有Dobb 博士的这篇文章，比较了并行算法的性能。

于 2012-04-23T22:45:08.943 回答