input:
BC
BD
BC
BC
BD
CD
output:
BC 3
BD 2
CD 1
if I use char type as key it is available.But seems Thrust does not support string as a key.
#include <thrust/device_vector.h>
#include <thrust/iterator/constant_iterator.h>
#include <thrust/reduce.h>
#include <string>
int main(void)
{
std::string data = "aaabbbbbcddeeeeeeeeeff";
size_t N = data.size();
thrust::device_vector<char> input(data.begin(), data.end());
thrust::device_vector<char> output(N);
thrust::device_vector<int> lengths(N);
size_t num_runs =
thrust::reduce_by_key(input.begin(), input.end(),
thrust::constant_iterator<int>(1),
output.begin(),
lengths.begin()
).first - output.begin();
return 0;
}
How to implement it using Thrust?
With apologies to @AngryLettuce, here are 2 possible approaches:
Method 1:
char item for each character in your key.sort the keys to bring like keys together. It appears that what you want is really just a count of each key type, regardless of where it appears in the sequence. To facilitate this with reduce_by_key, it's necessary to first group like keys together. Otherwise, reduce_by_key will treat like keys that are separated by different intervening keys as distinct key sequences. It's evident from your desired input and output that this is not what you want.reduce_by_key on the sorted keys, to count like keys.Step 2 requires (for this method) a functor to sort keys, and step 3 requires a functor to identify the meaning of "equal" keys, which reduce_by_key needs.
Method 2:
create two separate char device_vector(s), one to hold the first letter of each key, the other to hold the second letter of each key. We will then use zip_iterator throughout the remainder of the code to treat these two vectors as a unified "key" vector.
sort the zipped key vector. In this situation, thrust knows how to sort a zipped vector of basic types, and requires no separate sorting functor
perform reduce_by_key on the zipped (and sorted) key vector. This once again requires no separate equality functor. Thrust knows how to determine equality of zipped vectors of basic types.
This second method, in addition to not requiring any functor definitions, probably would also be faster, as zip_iterator tends to improve data access as compared to the AoS (array of structures) present in the first method.
Here's a worked example demonstrating both methods:
$ cat t1004.cu
#include <thrust/device_vector.h>
#include <thrust/sort.h>
#include <thrust/reduce.h>
#include <thrust/iterator/constant_iterator.h>
#include <iostream>
#include <thrust/iterator/zip_iterator.h>
struct key {
char k1;
char k2;
};
struct sort_functor{
__host__ __device__ bool operator()(key &k1, key &k2){
if (k1.k1 < k2.k1) return true;
if (k1.k1 > k2.k1) return false;
if (k1.k2 < k2.k2) return true;
return false;}
};
struct equal_key{
__host__ __device__ bool operator()(key k1, key k2){
if ((k1.k1 == k2.k1)&&(k1.k2 == k2.k2)) return true;
return false;}
};
int main(){
key data[] = {{'B','C'},{'B','D'},{'B','C'},{'B','C'},{'B','D'},{'C','D'}};;
size_t dsize = sizeof(data)/sizeof(key);
//method 1
thrust::device_vector<key> keys(data, data+dsize);
thrust::device_vector<key> keys_out(dsize);
thrust::device_vector<int> lengths(dsize);
thrust::sort(keys.begin(), keys.end(), sort_functor());
int rsize = thrust::reduce_by_key(keys.begin(), keys.end(), thrust::constant_iterator<int>(1), keys_out.begin(), lengths.begin(),equal_key()).first - keys_out.begin();
std::cout << "Method1:" << std::endl;
for (int i = 0; i < rsize; i++){
key temp = keys_out[i];
int len = lengths[i];
std::cout << " " << temp.k1 << temp.k2 << " " << len << std::endl;}
//method 2
//get the key data into 2 separate vectors.
//there are more efficient ways to do this
//but this is not the crux of your question
thrust::device_vector<char> k1;
thrust::device_vector<char> k2;
for (int i = 0; i < dsize; i++){
k1.push_back(data[i].k1);
k2.push_back(data[i].k2);}
thrust::sort(thrust::make_zip_iterator(thrust::make_tuple(k1.begin(), k2.begin())), thrust::make_zip_iterator(thrust::make_tuple(k1.end(), k2.end())));
thrust::device_vector<char> k1r(dsize);
thrust::device_vector<char> k2r(dsize);
rsize = thrust::reduce_by_key(thrust::make_zip_iterator(thrust::make_tuple(k1.begin(), k2.begin())), thrust::make_zip_iterator(thrust::make_tuple(k1.end(), k2.end())), thrust::constant_iterator<int>(1), thrust::make_zip_iterator(thrust::make_tuple(k1r.begin(), k2r.begin())), lengths.begin()).first - thrust::make_zip_iterator(thrust::make_tuple(k1r.begin(),k2r.begin()));
std::cout << "Method2:" << std::endl;
for (int i = 0; i < rsize; i++){
char c1 = k1r[i];
char c2 = k2r[i];
int len = lengths[i];
std::cout << " " << c1 << c2 << " " << len << std::endl;}
return 0;
}
$ nvcc -o t1004 t1004.cu
$ ./t1004
Method1:
BC 3
BD 2
CD 1
Method2:
BC 3
BD 2
CD 1
$
Here's an improved version of method 2. You should be able to use a string/char array directly, and this version can also be fairly easily modified to accommodate a key length from 2 to 10 characters. This method uses a strided range iterator to pull the individual key characters directly from the data array:
$ cat t1004.cu
#include <thrust/device_vector.h>
#include <thrust/sort.h>
#include <thrust/reduce.h>
#include <thrust/iterator/constant_iterator.h>
#include <iostream>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/permutation_iterator.h>
template <typename Iterator>
class strided_range
{
public:
typedef typename thrust::iterator_difference<Iterator>::type difference_type;
struct stride_functor : public thrust::unary_function<difference_type,difference_type>
{
difference_type stride;
stride_functor(difference_type stride)
: stride(stride) {}
__host__ __device__
difference_type operator()(const difference_type& i) const
{
return stride * i;
}
};
typedef typename thrust::counting_iterator<difference_type> CountingIterator;
typedef typename thrust::transform_iterator<stride_functor, CountingIterator> TransformIterator;
typedef typename thrust::permutation_iterator<Iterator,TransformIterator> PermutationIterator;
// type of the strided_range iterator
typedef PermutationIterator iterator;
// construct strided_range for the range [first,last)
strided_range(Iterator first, Iterator last, difference_type stride)
: first(first), last(last), stride(stride) {}
iterator begin(void) const
{
return PermutationIterator(first, TransformIterator(CountingIterator(0), stride_functor(stride)));
}
iterator end(void) const
{
return begin() + ((last - first) + (stride - 1)) / stride;
}
protected:
Iterator first;
Iterator last;
difference_type stride;
};
typedef thrust::device_vector<char>::iterator cIterator;
int main(){
//method 2
//get the key data into separate vectors, one per character in key.
#define KEYLEN 2
const char data[] = "BCBDBCBCBDCD";
size_t dsize = sizeof(data)/sizeof(char);
size_t numkeys = dsize/KEYLEN;
thrust::device_vector<char> keys(data, data+dsize);
strided_range<cIterator> *str_k[KEYLEN];
for (int i = 0; i < KEYLEN; i++)
str_k[i] = new strided_range<cIterator>(keys.begin()+i, keys.end(), KEYLEN);
//modify this line also if KEYLEN changes (max 10)
auto my_z = thrust::make_zip_iterator(thrust::make_tuple((*str_k[0]).begin(), (*str_k[1]).begin()));
thrust::sort(my_z, my_z+numkeys);
thrust::device_vector<char> kr[KEYLEN];
for (int i = 0; i < KEYLEN; i++)
kr[i].resize(numkeys);
//modify this line also if KEYLEN changes (max 10)
auto my_zr = thrust::make_zip_iterator(thrust::make_tuple(kr[0].begin(), kr[1].begin()));
thrust::device_vector<int> lengths(numkeys);
size_t rsize = thrust::reduce_by_key(my_z, my_z + numkeys, thrust::constant_iterator<int>(1), my_zr, lengths.begin()).first - my_zr;
std::cout << "Method2:" << std::endl;
for (int i = 0; i < rsize; i++){
std::cout << " ";
for (int j = 0; j < KEYLEN; j++){
char c = kr[j][i];
std::cout << c; }
int len = lengths[i];
std::cout <<" " << len << std::endl;}
return 0;
}
$ nvcc -std=c++11 t1004.cu -o t1004
$ ./t1004
Method2:
BC 3
BD 2
CD 1
$