Использовать тягу, чтобы найти элемент в группах

Question

У меня есть два вектора int для ключей и значений, их размер около 500K.

Ключевые слова уже отсортированы. И примерно 10 тыс. Групп.

Значение неотрицательное (означает полезное) или -2 (означает не использовать), в каждой группе должно быть одно или нулевое неотрицательные значения, а остальное - -2.

key: 0 0 0 0 1 2 2 3 3 3 3 
value:-2 -2 1 -2 3 -2 -2 -2 -2 -2 0 

Третья пара группы 0 [0 1] полезно. Для группы 1 мы получаем пару [1 3]. Значения группы 2 равны -2, поэтому мы ничего не получаем. А для группы 3 результат [3 0].

Итак, вопрос в том, как я могу сделать это с помощью тяги или куды?

Вот две идеи.

Первый: Получите количество каждой группы по алгоритму гистограммы. Таким образом, барьер каждой группы может быть вычислен. Управлять thrust::find_if на каждой группе, чтобы получить полезный элемент.

Второй один: Использование thrust::transform добавить 2 для каждого значения и теперь все значения неотрицательны, а ноль означает бесполезно. Используйте thrust::reduce_by_key, чтобы получить сокращение для каждой группы, а затем вычтите 2 для каждого выходного значения.

Я думаю, что должны быть какие-то другие методы, которые достигнут гораздо большей производительности, чем предыдущие два.

Производительность методов:

У меня есть тест Второй выше метод и метод дает @Robert Crovella, то есть. reduce_by_key и remove_if метод. Размер векторов 2691028, векторы состоят из 100001 групп. Вот их среднее время:

reduce_by_key: 1204ms 
remove_if: 192ms 

Сверху результата мы видим, что метод remove_if выполняется намного быстрее. А также метод «remove_if» прост в реализации и потребляет гораздо меньше памяти gpu.

Вкратце, метод @Robert Crovella очень хорош.

Answer 1

Я хотел бы использовать thrust::zip_iterator к zip the key and values pairs together, а затем я сделал бы thrust::remove_if операцию на молнии значений, которые будут требовать определения функтора, что указывало бы, чтобы удалить каждую пару, для которой значение является отрицательным (или любым другим тестом, который вы хотите.)

Вот обработанный пример:

$ cat t1009.cu 
#include <thrust/remove.h> 
#include <thrust/device_vector.h> 
#include <thrust/iterator/zip_iterator.h> 
#include <thrust/copy.h> 

struct remove_func 
{ 
    template <typename T> 
    __host__ __device__ 
    bool operator()(T &t){ 
    return (thrust::get<1>(t) < 0); // could change to other kinds of tests 
    } 
}; 

int main(){ 

    int keys[] = {0,0,0,0,1,2,2,3,3,3,3}; 
    int vals[] = {-2,-2,1,-2,3,-2,-2,-2,-2,-2,0}; 
    size_t dsize = sizeof(keys)/sizeof(int); 

    thrust::device_vector<int>dkeys(keys, keys+dsize); 
    thrust::device_vector<int>dvals(vals, vals+dsize); 
    auto zr = thrust::make_zip_iterator(thrust::make_tuple(dkeys.begin(), dvals.begin())); 

    size_t rsize = thrust::remove_if(zr, zr+dsize, remove_func()) - zr; 

    thrust::copy_n(dkeys.begin(), rsize, std::ostream_iterator<int>(std::cout, ",")); 
    std::cout << std::endl; 
    thrust::copy_n(dvals.begin(), rsize, std::ostream_iterator<int>(std::cout, ",")); 
    std::cout << std::endl; 
    return 0; 
} 
$ nvcc -std=c++11 -o t1009 t1009.cu 
$ ./t1009 
0,1,3, 
1,3,0, 
$