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