Spaces:
Runtime error
Runtime error
File size: 4,736 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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
#include <thrust/detail/config.h>
#if THRUST_CPP_DIALECT >= 2011
#include <thrust/random.h>
#include <thrust/sequence.h>
#include <thrust/shuffle.h>
#include <thrust/sort.h>
#include <unittest/unittest.h>
#include <map>
template <typename Vector>
void TestShuffleSimple() {
Vector data(5);
data[0] = 0;
data[1] = 1;
data[2] = 2;
data[3] = 3;
data[4] = 4;
Vector shuffled(data.begin(), data.end());
thrust::default_random_engine g(2);
thrust::shuffle(shuffled.begin(), shuffled.end(), g);
thrust::sort(shuffled.begin(), shuffled.end());
// Check all of our data is present
// This only tests for strange conditions like duplicated elements
ASSERT_EQUAL(shuffled, data);
}
DECLARE_VECTOR_UNITTEST(TestShuffleSimple);
template <typename Vector>
void TestShuffleCopySimple() {
Vector data(5);
data[0] = 0;
data[1] = 1;
data[2] = 2;
data[3] = 3;
data[4] = 4;
Vector shuffled(5);
thrust::default_random_engine g(2);
thrust::shuffle_copy(data.begin(), data.end(), shuffled.begin(), g);
g.seed(2);
thrust::shuffle(data.begin(), data.end(), g);
ASSERT_EQUAL(shuffled, data);
}
DECLARE_VECTOR_UNITTEST(TestShuffleCopySimple);
template <typename T>
void TestHostDeviceIdentical(size_t m) {
thrust::host_vector<T> host_result(m);
thrust::host_vector<T> device_result(m);
thrust::sequence(host_result.begin(), host_result.end(), 0llu);
thrust::sequence(device_result.begin(), device_result.end(), 0llu);
thrust::default_random_engine host_g(183);
thrust::default_random_engine device_g(183);
thrust::shuffle(host_result.begin(), host_result.end(), host_g);
thrust::shuffle(device_result.begin(), device_result.end(), device_g);
ASSERT_EQUAL(device_result, host_result);
}
DECLARE_VARIABLE_UNITTEST(TestHostDeviceIdentical);
// Individual input keys should be permuted to output locations with uniform
// probability. Perform chi-squared test with confidence 99.9%.
template <typename Vector>
void TestShuffleKeyPosition() {
typedef typename Vector::value_type T;
size_t m = 20;
size_t num_samples = 100;
thrust::host_vector<size_t> index_sum(m, 0);
thrust::host_vector<T> sequence(m);
thrust::sequence(sequence.begin(), sequence.end(), T(0));
for (size_t i = 0; i < num_samples; i++) {
Vector shuffled(sequence.begin(), sequence.end());
thrust::default_random_engine g(i);
thrust::shuffle(shuffled.begin(), shuffled.end(), g);
thrust::host_vector<T> tmp(shuffled.begin(), shuffled.end());
for (auto j = 0ull; j < m; j++) {
index_sum[tmp[j]] += j;
}
}
double expected_average_position = static_cast<double>(m - 1) / 2;
double chi_squared = 0.0;
for (auto j = 0ull; j < m; j++) {
double average_position = static_cast<double>(index_sum[j]) / num_samples;
chi_squared += std::pow(expected_average_position - average_position, 2) /
expected_average_position;
}
// Tabulated chi-squared critical value for m-1=19 degrees of freedom
// and 99.9% confidence
double confidence_threshold = 43.82;
ASSERT_LESS(chi_squared, confidence_threshold);
}
DECLARE_INTEGRAL_VECTOR_UNITTEST(TestShuffleKeyPosition);
struct vector_compare {
template <typename VectorT>
bool operator()(const VectorT& a, const VectorT& b) const {
for (auto i = 0ull; i < a.size(); i++) {
if (a[i] < b[i]) return true;
if (a[i] > b[i]) return false;
}
return false;
}
};
// Brute force check permutations are uniformly distributed on small input
// Uses a chi-squared test indicating 99% confidence the output is uniformly
// random
template <typename Vector>
void TestShuffleUniformPermutation() {
typedef typename Vector::value_type T;
size_t m = 5;
size_t num_samples = 1000;
size_t total_permutations = 1 * 2 * 3 * 4 * 5;
std::map<thrust::host_vector<T>, size_t, vector_compare> permutation_counts;
Vector sequence(m);
thrust::sequence(sequence.begin(), sequence.end(), T(0));
thrust::default_random_engine g(17);
for (auto i = 0ull; i < num_samples; i++) {
thrust::shuffle(sequence.begin(), sequence.end(), g);
thrust::host_vector<T> tmp(sequence.begin(), sequence.end());
permutation_counts[tmp]++;
}
ASSERT_EQUAL(permutation_counts.size(), total_permutations);
double chi_squared = 0.0;
double expected_count = static_cast<double>(num_samples) / total_permutations;
for (auto kv : permutation_counts) {
chi_squared += std::pow(expected_count - kv.second, 2) / expected_count;
}
// Tabulated chi-squared critical value for 119 degrees of freedom (5! - 1)
// and 99% confidence
double confidence_threshold = 157.8;
ASSERT_LESS(chi_squared, confidence_threshold);
}
DECLARE_VECTOR_UNITTEST(TestShuffleUniformPermutation);
#endif
|