38 #ifndef MUSTER_RANDOM_H
39 #define MUSTER_RANDOM_H
42 #include <tr1/unordered_map>
62 template <
class OutputIterator,
class Random>
63 void algorithm_r(
size_t numElements,
size_t sample_size, OutputIterator out, Random& random) {
65 size_t remaining = numElements;
66 size_t m = sample_size;
69 if ((
size_t)random(remaining) < m) {
96 template <
class OutputIterator,
class Random>
97 void fast_sample(
size_t numElements,
size_t sample_size, OutputIterator out, Random& random) {
99 std::tr1::unordered_map<size_t, size_t> swaps;
101 for (
size_t s = 0; s < sample_size; s++) {
102 size_t remaining = numElements - s;
103 size_t pick = random(remaining);
105 *out = swaps.count(pick) ? swaps[pick] : pick;
109 size_t last = remaining - 1;
110 swaps[pick] = swaps.count(last) ? swaps[last] : last;
121 gettimeofday(&time, 0);
122 return time.tv_sec * time.tv_usec;
127 #endif // MUSTER_RANDOM_H
long get_time_seed()
Returns a seed for random number generators based on the product of sec and usec from gettimeofday()...
void algorithm_r(size_t numElements, size_t sample_size, OutputIterator out, Random &random)
This is Knuth's algorithm R for taking a sample of numElements numbers.
void fast_sample(size_t numElements, size_t sample_size, OutputIterator out, Random &random)
This is a fast algorithm for random sampling that scales with the number of elements sampled (sample_...