11 #include "Randomness.hpp"
25 template<
typename InputIterator,
typename ResultType>
26 static std::unique_ptr<std::vector<ResultType>>
sampleWithoutReplacement(InputIterator first, InputIterator last,
size_t sizeOfSample);
33 template<
typename RandomAccessIterator,
typename ResultType>
34 static std::unique_ptr<std::vector<ResultType>>
sampleWithoutReplacementFast(RandomAccessIterator first, RandomAccessIterator last,
size_t sizeOfSample);
41 template<
typename InputIterator,
typename ResultType>
42 static std::unique_ptr<std::vector<ResultType>>
sampleWithReplacement(InputIterator first, InputIterator last, std::vector<double> & weights,
size_t sizeOfSample);
49 template<
typename InputIterator,
typename ResultType>
50 static std::unique_ptr<std::vector<ResultType>>
sampleWithReplacement(InputIterator first, InputIterator last,
size_t sizeOfSet,
size_t sizeOfSample);
53 template<
typename InputIterator,
typename ResultType>
56 std::unique_ptr<std::vector<ResultType>> buckets(
new std::vector<ResultType>(sizeOfSample));
57 std::mt19937 * gen = Randomness::getMT19937();
58 std::uniform_real_distribution<double> sampleDice(0, 1);
59 std::uniform_int_distribution<size_t> bucketDice(0, sizeOfSample-1);
62 size_t numberOfElements = 0;
63 for(
auto it = buckets->begin(); it != buckets->end() && first != last; ++it)
70 if(sizeOfSample > numberOfElements)
71 return std::unique_ptr<std::vector<ResultType>>(
new std::vector<ResultType>(buckets->begin(), buckets->begin()+numberOfElements));
74 size_t index = sizeOfSample+1;
77 if(sampleDice(*gen) <
double(sizeOfSample)/
double(index))
78 (*buckets)[bucketDice(*gen)] = *first;
86 template<
typename RandomAccessIterator,
typename ResultType>
89 unsigned long long n = last-first;
92 return std::unique_ptr<std::vector<ResultType>>(
new std::vector<ResultType>(first, last));
94 std::mt19937 * gen = Randomness::getMT19937();
95 std::uniform_real_distribution<double> sampleDice(0, n-1);
96 std::set<size_t> selected;
97 std::vector<size_t> indices;
98 indices.reserve(sizeOfSample);
99 while(selected.size() < sizeOfSample)
101 size_t element = sampleDice(*gen);
102 if(selected.count(element) == 0)
104 selected.insert(element);
105 indices.push_back(element);
109 std::unique_ptr<std::vector<ResultType>> buckets(
new std::vector<ResultType>());
110 buckets->reserve(sizeOfSample);
112 for(
auto it = indices.begin(); it != indices.end(); ++it)
113 buckets->push_back(*(first + *it));
118 template<
typename InputIterator,
typename ResultType>
119 std::unique_ptr<std::vector<ResultType>>
Sampling::sampleWithReplacement(InputIterator first, InputIterator last, std::vector<double> & weights,
size_t sizeOfSample)
121 std::mt19937 * gen = Randomness::getMT19937();
122 std::discrete_distribution<size_t> d(weights.begin(), weights.end());
125 std::multimap<size_t, size_t> samples;
126 for(
size_t i = 0; i < sizeOfSample; ++i)
127 samples.insert(std::pair<size_t,size_t>(d(*gen), i));
130 std::unique_ptr<std::vector<ResultType>> buckets(
new std::vector<ResultType>(sizeOfSample));
132 for(
auto it = first; it != last; ++it)
134 auto buck = samples.equal_range(index);
135 for(
auto itbuck = buck.first; itbuck != buck.second; ++itbuck)
136 (*buckets)[itbuck->second] = *it;
143 template<
typename InputIterator,
typename ResultType>
144 std::unique_ptr<std::vector<ResultType>>
Sampling::sampleWithReplacement(InputIterator first, InputIterator last,
size_t sizeOfSet,
size_t sizeOfSample)
146 std::mt19937 * gen = Randomness::getMT19937();
147 std::uniform_int_distribution<size_t> d(0, sizeOfSet-1);
150 std::multimap<size_t, size_t> samples;
151 for(
size_t i = 0; i < sizeOfSample; ++i)
152 samples.insert(std::pair<size_t,size_t>(d(*gen), i));
155 std::unique_ptr<std::vector<ResultType>> buckets(
new std::vector<ResultType>(sizeOfSample));
157 for(
auto it = first; it != last; ++it)
159 auto buck = samples.equal_range(index);
160 for(
auto itbuck = buck.first; itbuck != buck.second; ++itbuck)
161 (*buckets)[itbuck->second] = *it;