키의 발생 수와

Question

추력 CUDA하여 키의 첫번째 발생의 위치를 ​​찾기 내가 키

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

그것은 문제의 그와 같은 특별한 기능을 가지고있다

귀하의 질문은 약 2입니다 다른 문제 :

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; 
} 

: 여기

는 완전히 일 예이다