具有虚拟内存和写入组合的并行基数排序

Question

我正在尝试实现 http://arxiv.org/pdf/1008.2849v2.pdf（算法 2）中描述的并行基数排序的变体，但我的 C++ 实现（以 10 为基数的 4 位数字）包含一个我无法实现的错误定位。

出于调试目的，我没有使用并行机制，但代码应该仍能正确排序。

例如，arr.at(i) = item 行在下面

中访问其范围之外的索引

std::vector<int> v = {4612, 4598};
radix_sort2(v);

我的实现如下

#include <set>
#include <array>
#include <vector>

void radix_sort2(std::vector<int>& arr) {
    std::array<std::set<int>, 10> buckets3;

    for (const int item : arr) {
        int d = item / 1000;
        buckets3.at(d).insert(item);
    }

    //Prefix sum
    std::array<int, 10> outputIndices;
    outputIndices.at(0) = 0;
    for (int i = 1; i < 10; ++i) {
        outputIndices.at(i) = outputIndices.at(i - 1) +
            buckets3.at(i - 1).size();
    }

    for (const auto& bucket3 : buckets3) {
        std::array<std::set<int>, 10> buckets0, buckets1;
        std::array<int, 10> histogram2 = {};

        for (const int item : bucket3) {
            int d = item % 10;
            buckets0.at(d).insert(item);
        }
        for (const auto& bucket0 : buckets0) {
            for (const int item : bucket0) {
                int d = (item / 10) % 10;
                buckets1.at(d).insert(item);

                int d2 = (item / 100) % 10;
                ++histogram2.at(d2);
            }
        }

        for (const auto& bucket1 : buckets1) {
            for (const int item : bucket1) {
                int d = (item / 100) % 10;
                int i = outputIndices.at(d) + histogram2.at(d);
                ++histogram2.at(d);
                arr.at(i) = item;
            }
        }
    }
}

谁能发现我的错误？

Answer 1

我查看了您链接的论文。你没有犯任何错误，none 我看得出来。事实上，据我估计，你纠正了算法中的一个错误。

我写出了算法，结果遇到了和你完全一样的问题。在回顾了算法 2 之后，要么我严重误解了它应该如何工作，要么它有缺陷。该算法至少存在一些问题，特别是围绕 outputIndices 和 histogram2.

看算法，item的最终索引是由outputIndices中存储的计数排序决定的。（让我们暂时忽略直方图）。如果你有一个数字的初始数组 {0100, 0103, 0102, 0101} ，那么它的前缀和就是 4。该算法没有任何迹象表明我可以确定将结果滞后 1。话虽如此，为了使算法按照他们预期的方式工作，它确实必须滞后，所以，继续。现在，前缀和为 0, 4, 4...。该算法不使用 MSD 作为 outputIndices 数组的索引，它使用 "MSD - 1"；因此，将 1 作为数组的索引，没有直方图的第一项的 starting 索引是 4！第一次尝试在数组之外。 outputIndices 是用 MSD 构建的，它被 MSD 访问是有意义的。

此外，即使您调整算法以正确地将 MSD 用于 outputIndices，它仍然无法正确排序。使用您的初始输入（交换）{4598, 4612}，它们将保持该顺序。它们被（本地）排序，就好像它们是 2 位数字一样。如果将它增加到其他数字不是以 4 开头，它们将在全局范围内排序，但本地排序永远不会完成。根据这篇论文，目标是使用直方图来做到这一点，但我没有看到这种情况发生。

最终，我假设，您想要的是一种按照描述的方式工作的算法。我修改了算法，与论文的总体目标保持一致，即使用 MSD 进行全局排序，其余数字通过反向 LSD。我认为这些更改不会对您并行化函数的愿望产生任何影响。

void radix_sort2(std::vector<int>& arr)
{
    std::array<std::vector<int>, 10> buckets3;

    for (const int item : arr)
    {
        int d = item / 1000;
        buckets3.at(d).push_back(item);
    }

    //Prefix sum
    std::array<int, 10> outputIndices;
    outputIndices.at(0) = 0;

    for (int i = 1; i < 10; ++i)
    {
        outputIndices.at(i) = outputIndices.at(i - 1) + buckets3.at(i - 1).size();
    }

    for (const auto& bucket3 : buckets3)
    {       
        if (bucket3.size() <= 0)
            continue;

        std::array<std::vector<int>, 10> buckets0, buckets1, buckets2;

        for (const int item : bucket3)
            buckets0.at(item % 10).push_back(item);

        for (const auto& bucket0 : buckets0)
            for (const int item : bucket0)
                buckets1.at((item / 10) % 10).push_back(item);

        for (const auto& bucket1 : buckets1)
            for (const int item : bucket1)
                buckets2.at((item / 100) % 10).push_back(item);

        int count = 0;

        for (const auto& bucket2 : buckets2)
        {
            for (const int item : bucket2)
            {
                int d = (item / 1000) % 10;
                int i = outputIndices.at(d) + count;
                ++count;
                arr.at(i) = item;
            }
        }
    }
}

为了可扩展性，创建一个执行本地排序的辅助函数可能是有意义的。您应该能够扩展它以通过这种方式处理任意数量的数字。

具有虚拟内存和写入组合的并行基数排序

Parallel radix sort with virtual memory and write-combining

sorting

algorithm

caching

radix-sort