Быстрый взлом на сортировку: я делаю это правильно?

Question

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

__global__ void noSort(int *inarr, char *outarr, int size)
{
    int idx = threadIdx.x + blockIdx.x * blockDim.x;
    if (idx < size) 
            outarr[inarr[idx]] = 1;
}

Затем на стороне хоста я просто печатаю индексы массива, где outarr[i] == 1.Теперь, фактически, вышеприведенное можно использовать для сортировки целочисленного списка, и это тоже может быть быстрее, чем алгоритмы, которые на самом деле сортируют.

Это законно?

Answer 1

Ваш пример, по сути, является специализированной сортирующей подсчет для входных данных с уникальными ключами (т.е. без дубликатов).Чтобы сделать код правильной подсчетной сортировкой, вы можете заменить присвоение outarr[inarr[idx]] = 1 на atomicAdd(inarr + idx, 1), чтобы подсчитать дублирующиеся ключи.Однако, несмотря на то, что атомарные операции довольно дороги, у вас все еще есть проблема, заключающаяся в том, что сложность метода пропорциональна наибольшему значению на входе.К счастью, radix sort решает обе эти проблемы.

Radix sort можно рассматривать как обобщение сортировки подсчета, которая рассматривает только B битов ввода за раз.Так как целые числа B битов могут принимать значения только в диапазоне [0,2^B), мы можем не смотреть на весь диапазон значений.

Теперь, прежде чем вы начнете выполнять сортировку по основанию в CUDA, я должен предупредить васчто он был широко изучен и чрезвычайно быстро реализации легко доступны.Фактически, библиотека Thrust автоматически применяет сортировку по радиусу, когда это возможно.

Answer 2

Я вижу, что вы здесь делаете, но я думаю, что это полезно только в особых случаях.Например, что, если элемент inarr имеет чрезвычайно большое значение?Это потребовало бы, чтобы outarr имел как минимум столько же элементов, чтобы справиться с этим.А как насчет повторяющихся чисел?

Предположим, вы начали с массива с уникальными небольшими значениями внутри, это интересный способ сортировки.В общем, мне кажется, что он будет использовать огромные объемы памяти для выполнения чего-то, что уже хорошо обрабатывается такими алгоритмами, как параллельная сортировка слиянием.Чтение выходного массива также будет очень дорогим процессом (особенно, если во входном массиве есть большие значения), так как в итоге вы получите очень разреженный массив.