Нахождение количества вхождений ключей и позиции первых вхождений ключей от CUDA Упорного

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

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

// 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()); 

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

Ваш вопрос о двух различные проблемы:

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

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

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

Проблема №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; 
}