查找鍵出現的第一按鍵出現的通過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; 
}