I have an array of int which serves as keys in my application. This is already sorted. I want to assign each unique key a unique index starting from 0. How would I do that in cuda using thrust?
int* sorted_keys = {1, 1, 1, 13, 13, 13, 13, 13, 19, 19, 20}
// Some thrust operation to get a new array as
index_for_sorted_keys = {0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3}
Each segment can be of any arbitrary length.
There are probably many ways to do it. One possible way: thrust::adjacent_difference() with a binary op that produces 0 when the values are the same and 1 in any other case, followed by a prefix sum.
Here is a worked example:
$ cat t1537.cu
#include <thrust/adjacent_difference.h>
#include <thrust/scan.h>
#include <thrust/device_vector.h>
#include <iostream>
#include <thrust/copy.h>
using namespace thrust::placeholders;
int main(){
int sorted_keys[] = {1, 1, 1, 13, 13, 13, 13, 13, 19, 19, 20};
int ds = sizeof(sorted_keys)/sizeof(sorted_keys[0]);
thrust::device_vector<int> d_sk(sorted_keys, sorted_keys+ds);
thrust::device_vector<int> d_r(d_sk.size());
thrust::adjacent_difference(d_sk.begin(), d_sk.end(), d_r.begin(), !(_1==_2));
d_r[0] = 0;
thrust::inclusive_scan(d_r.begin(), d_r.end(), d_r.begin());
thrust::copy(d_r.begin(), d_r.end(), std::ostream_iterator<int>(std::cout, ","));
std::cout << std::endl;
return 0;
}
$ nvcc -o t1537 t1537.cu
$ ./t1537
0,0,0,1,1,1,1,1,2,2,3,
$
