thrust::sort_by_key: как сохранить результат в отдельном массиве?

Question

Я в настоящее время сортирую значения по ключу следующим образом

thrust::sort_by_key(thrust::device_ptr<int>(keys), 
                    thrust::device_ptr<int>(keys + numKeys),
                    thrust::device_ptr<int>(values);

который сортирует массив значений по ключам.

Есть ли способ оставить массив "values" нетронутым и вместо этого сохранить результат сортировки "values" в отдельный массив?

Заранее спасибо.

Answer 1

Нет прямого способа сделать то, что вы просите. У вас есть два варианта функционально достичь одного и того же.

Первый - сделать копию массива значений перед вызовом, предоставив вам отсортированную и несортированную версию исходных данных. Итак, ваш пример становится

thrust::device_vector<int> values_sorted(thrust::device_ptr<int>(values),
                                     thrust::device_ptr<int>(values + numKeys));

thrust::sort_by_key(thrust::device_ptr<int>(keys), 
                    thrust::device_ptr<int>(keys + numKeys),
                    values_sorted.begin());

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

typedef thrust::device_vector<int>::iterator iit;

thrust::device_vector<int> index(thrust::make_counting_iterator(int(0)),
                                 thrust::make_counting_iterator(int(numKeys));    

thrust::sort_by_key(thrust::device_ptr<int>(keys), 
                    thrust::device_ptr<int>(keys + numKeys),
                    index.begin());


thrust::permutation_iterator<iit,iit> perm(thrust::device_ptr<int>(values),
                                           index.begin());

Сейчас perm вернусь values в keys отсортированный порядок index без изменения порядка исходных данных.

[стандартный отказ от ответственности: весь код написан в браузере, никогда не компилируется и не тестируется. Использовать на свой страх и риск]