Как сортировать ключи с меньшей точностью с помощью библиотеки Thrust

Question

У меня есть набор целочисленных значений, и я хочу отсортировать их с помощью Thrust. Есть ли возможность использовать только некоторые старшие / младшие биты в этой сортировке. Если возможно, я не хочу использовать пользовательский компаратор, потому что он меняет используемый алгоритм с радикальной сортировки на сортировку слиянием и значительно увеличивает истекшее время.

Я думаю, что когда все числа имеют одно и то же значение в бите, этот бит пропускается при сортировке, поэтому возможно ли использовать наименьшее возможное число бит и надеюсь, что этого будет достаточно. (то есть: для 5 бит, используя char с 8 битами и устанавливая верхние 3 бита в 0)

Пример:

sort<4, 0>(myvector.begin(), myvector.end())
sort<4, 1>(myvector.begin(), myvector.end())

сортировка, используя только 4 бита, высокий или низкий.

Нечто похожее на http://www.moderngpu.com/sort/mgpusort.html

Answer 1

Интерфейс Thrust абстрагирует детали реализации алгоритма, такие как тот факт, что одна из текущих стратегий сортировки является радикальной сортировкой. Из-за возможности того, что базовая реализация сортировки может измениться от версии к версии, от бэкенда до бэкенда или даже от вызова к вызову, пользователь не сможет сообщить количество бит для сортировки.

К счастью, такая явная информация обычно не нужна. При необходимости текущая реализация сортировки Thrust будет проверять ключи сортировки и опускать лишние вычисления среди обнуленных битов.

Answer 2

Как насчет использования transformer_iterator? Вот краткий пример (сортировка по первым битам), и вы можете написать собственную унарную функцию для ваших целей.

#include <iostream>
#include <thrust/device_vector.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/sort.h>

using namespace std;
struct and_func : public thrust::unary_function<int,int>
{
    __host__ __device__
        int operator()(int x)
        {
            return 8&x;
        }
};
int main()
{
    thrust::device_vector<int> d_vec(4);
    d_vec[0] = 10;
    d_vec[1] = 8;
    d_vec[2] = 12;
    d_vec[3] = 1;
    thrust::sort_by_key(thrust::make_transform_iterator(d_vec.begin(), and_func()),
                 thrust::make_transform_iterator(d_vec.end(), and_func()),
                 d_vec.begin());
    for (int i = 0; i < 4; i++)
        cout<<d_vec[i]<<" ";
    cout<<"\n"<<endl;
    return 0;
}