Finding the number of occurrences of keys and the positions of first occurrences of keys by CUDA Thrust

Question

Say I have a vector of keys

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 ; 

I already know before hand that there are 4 distinct key values in this vector. I want to populate the two device arrays pidx[4] and pnum[4].

1. The pidx array gives me the first position of each distinct key in the keys vector, namely the positions marked with ----> in the code snippet above. So, in this example, I should have pidx[4] = {0, 2, 5, 7}.

2. The pnum array gives me the number of occurrences of each key. So, in this example, I should have pnum[4] = {2, 3, 2, 3} .

How would one perform the above operation with CUDA Thrust?

Answer 1

This is not the optimal solution, but I can't figure out a better way.

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