Параллельная сортировка по радиусу с виртуальной памятью и комбинированием записи

Question

Я пытаюсь реализовать вариант параллельной сортировки по основанию, описанный в http://arxiv.org/pdf/1008.2849v2.pdf (Алгоритм 2), но моя реализация на C++ (для 4 цифр в базе 10) содержит ошибку, которую я Я не могу найти.

В целях отладки я не использую параллелизм, но код все равно должен сортироваться правильно.

Например, линия 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

Я посмотрел на документ, который вы связали. Вы не сделали никаких ошибок, ни одной, которую я могу видеть. На самом деле, по моей оценке, вы исправили ошибку в алгоритме.

Я написал алгоритм и столкнулся с той же проблемой, что и вы. Изучив Алгоритм 2, я либо ужасно неправильно понял, как он должен работать, либо он ошибочен. Есть, по крайней мере, пара проблем с алгоритмом, особенно вращающихся вокруг outputIndices, а также histogram2,

Глядя на алгоритм, конечный индекс элемента определяется сортировкой, хранящейся в outputIndices, (давайте пока проигнорируем гистограмму). Если у вас был начальный массив чисел {0100, 0103, 0102, 0101} Сумма префикса равна 4. Алгоритм не указывает, что я могу определить, что результат отстает на 1. При этом, чтобы алгоритм работал так, как он задумал, он должен быть запаздывающим, поэтому перемещение на. Теперь префиксные суммы 0, 4, 4..., Алгоритм не использует MSD в качестве индекса в outputIndices массив, он использует "MSD - 1"; Таким образом, принимая 1 в качестве индекса в массиве, начальный индекс для первого элемента без гистограммы равен 4! За пределами массива с первой попытки. outputIndices построен с MSD, имеет смысл для доступа к нему MSD.

Кроме того, даже если вы настроите алгоритм, чтобы правильно использовать MSD в outputIndices, это все еще не будет сортировать правильно. С вашими начальными входами (поменялись местами) {4598, 4612}они останутся в таком порядке. Они отсортированы (локально), как если бы они были двухзначными числами. Если вы увеличите его, чтобы другие числа не начинались с 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;
            }
        }
    }
}

Для расширяемости, вероятно, имеет смысл создать вспомогательную функцию, которая выполняет локальную сортировку. Вы должны быть в состоянии расширить его, чтобы обрабатывать любое количество цифр таким образом.