Определение количества появлений ключей и позиций первых появлений ключей с помощью CUDA Thrust

Question

Скажем, у меня есть вектор ключей

thrust::device_vector<int> keys(10); 
keys[0] = 51; // -----> 
keys[1] = 51; 
keys[2] = 72; // -----> 
keys[3] = 72; 
keys[4] = 72; 
keys[5] = 103; //-----> 
keys[6] = 103; 
keys[7] = 504; // ------> 
keys[8] = 504 
keys[9] = 504 ; 

Я уже знал заранее, что в этом векторе есть 4 различных значений ключей.Я хочу заполнить два массива устройств pidx[4] и pnum[4].

1. Массив pidx дает мне первую позицию каждого отдельного ключа в векторе ключей, а именно позиции, отмеченные ----> в фрагменте кода выше.Итак, в этом примере у меня должно быть pidx[4] = {0, 2, 5, 7}.

2. Массив pnum дает мне количество вхождений каждого ключа.Итак, в этом примере у меня должно быть pnum[4] = {2, 3, 2, 3}.

Как выполнить вышеуказанную операцию с CUDA Thrust?

Answer 1

Это не оптимальное решение, но я не могу найти лучший способ.

// Use `unique` to grab the distinct values
thrust::device_vector<int> values(4);
thrust::unique_copy( keys.begin(), keys.end(), values.begin() );

// For each of the values use `count` to get the frequencies
for ( int i = 4; i != 0; --i )
    pnum[i] = thrust::count( keys.begin(), keys.end(), values[i] );

// Use prefix sum to get the indices
thrust::exclusive_scan( pnum.begin(), pnum.end(), pidx.begin() );

Answer 2

Ваш вопрос касается двух разных проблем:

1. Нахождение количества вхождений элементов внутри вектора;
2. Нахождение позиции первого вхождения для каждого ключа.

Мне кажется, что два вышеуказанных пункта не распознаются ни в одном из других предоставленных ответов.

Задача № 1 составляет при построении гистограммы последовательности,см. https://code.google.com/p/thrust/source/browse/examples/histogram.cu. Классическое решение этой проблемы - сначала отсортировать ключи по thrust::sort, а затем выполнить thrust::reduce_by_key, чтобы вычислить количество вхождений.Это было уже распознано в Подсчет вхождений чисел в массиве cuda и Количество вхождений тяги .

Задача № 2 - это приложение thrust::unique_by_key и thrust::sequence.

Вот полностью обработанный пример:

#include <thrust/device_vector.h>
#include <thrust/reduce.h>
#include <thrust/random.h>
#include <thrust/sort.h>

/********/
/* MAIN */
/********/
int main()
{
    /**************************/
    /* SETTING UP THE PROBLEM */
    /**************************/

    const int N = 20;           // --- Number of elements

    // --- Random uniform integer distribution between 0 and 4
    thrust::default_random_engine rng;
    thrust::uniform_int_distribution<int> dist(0, 4);

    // --- Keys allocation and initialization
    thrust::device_vector<int> d_keys(N);
    for (size_t i = 0; i < d_keys.size(); i++) d_keys[i] = dist(rng);

    /****************/
    /* THE APPROACH */
    /****************/

    thrust::device_vector<int> d_values(N, 1);
    thrust::sort(d_keys.begin(), d_keys.end());

    thrust::reduce_by_key(d_keys.begin(), d_keys.end(), thrust::constant_iterator<int>(1), d_keys.begin(), d_values.begin());

    printf("Keys\n");
    for (int i=0; i<N; i++) std::cout << d_keys[i] << " " << d_values[i] << "\n";
    printf("\n");

    return 0;
} 

Answer 3

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

   float keys[] = {51,51,72,72,72,103,103,504,504,504};      
   int N = sizeof(keys) / sizeof(int);

   array input(N, 1, keys);
   array values, pidx, locations;
   // unique elements in a vector and their indicies 
   setunique(values, pidx, locations, input);

   // # of unique elements
   int n_unique = pidx.elements();
   array pnum = zeros(n_unique); // empty array

   gfor(array i, n_unique) // parallel for loop
      // count the # of occurrences for each key
      pnum(i) = sum(locations == i);

   print(pidx);           
   print(pnum);

вывод:

pidx = 0,0000 2,0000 5,0000 7,0000

pnum = 2,0000 3,0000 2,0000 3.0000

Answer 4

Это решение предполагает, что ваш список ключей уже отсортирован. Если это не так, просто добавьте еще один шаг в начале, чтобы отсортировать список.

// generate a list of indices to correspond with the key array
thrust::device_vector<int> values(numKeys);
thrust::sequence(values.begin(), values.end());

// perform an inclusive scan to determine the minimum index for each unique key
thrust::equal_to<int> binaryPred;
thrust::minimum<int> binaryOp;
thrust::inclusive_scan_by_key(keys.begin(), keys.end(), values.begin(), values.begin(), binaryPred, binaryOp);

// find the unique indices
thrust::unique(values.begin(), values.end());