Spaces:
Runtime error
Runtime error
File size: 2,778 Bytes
be11144 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/generate.h>
#include <thrust/sequence.h>
#include <thrust/sort.h>
#include <thrust/gather.h>
#include <thrust/random.h>
#include <iostream>
// This example shows how to perform a lexicographical sort on multiple keys.
//
// http://en.wikipedia.org/wiki/Lexicographical_order
template <typename KeyVector, typename PermutationVector>
void update_permutation(KeyVector& keys, PermutationVector& permutation)
{
// temporary storage for keys
KeyVector temp(keys.size());
// permute the keys with the current reordering
thrust::gather(permutation.begin(), permutation.end(), keys.begin(), temp.begin());
// stable_sort the permuted keys and update the permutation
thrust::stable_sort_by_key(temp.begin(), temp.end(), permutation.begin());
}
template <typename KeyVector, typename PermutationVector>
void apply_permutation(KeyVector& keys, PermutationVector& permutation)
{
// copy keys to temporary vector
KeyVector temp(keys.begin(), keys.end());
// permute the keys
thrust::gather(permutation.begin(), permutation.end(), temp.begin(), keys.begin());
}
thrust::host_vector<int> random_vector(size_t N)
{
thrust::host_vector<int> vec(N);
static thrust::default_random_engine rng;
static thrust::uniform_int_distribution<int> dist(0, 9);
for (size_t i = 0; i < N; i++)
vec[i] = dist(rng);
return vec;
}
int main(void)
{
size_t N = 20;
// generate three arrays of random values
thrust::device_vector<int> upper = random_vector(N);
thrust::device_vector<int> middle = random_vector(N);
thrust::device_vector<int> lower = random_vector(N);
std::cout << "Unsorted Keys" << std::endl;
for(size_t i = 0; i < N; i++)
{
std::cout << "(" << upper[i] << "," << middle[i] << "," << lower[i] << ")" << std::endl;
}
// initialize permutation to [0, 1, 2, ... ,N-1]
thrust::device_vector<int> permutation(N);
thrust::sequence(permutation.begin(), permutation.end());
// sort from least significant key to most significant keys
update_permutation(lower, permutation);
update_permutation(middle, permutation);
update_permutation(upper, permutation);
// Note: keys have not been modified
// Note: permutation now maps unsorted keys to sorted order
// permute the key arrays by the final permuation
apply_permutation(lower, permutation);
apply_permutation(middle, permutation);
apply_permutation(upper, permutation);
std::cout << "Sorted Keys" << std::endl;
for(size_t i = 0; i < N; i++)
{
std::cout << "(" << upper[i] << "," << middle[i] << "," << lower[i] << ")" << std::endl;
}
return 0;
}
|