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
|
#pragma once
#include "fast.h"
#include "entropy.h"
#include <util/generic/utility.h>
#include <util/system/yassert.h>
// some kind of https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm
template <typename TRandIter, typename TRandIterEnd>
inline void Shuffle(TRandIter begin, TRandIterEnd end) {
Y_ASSERT(begin <= end);
static_assert(sizeof(end - begin) <= sizeof(size_t), "fixme");
static_assert(sizeof(TReallyFastRng32::RandMax()) <= sizeof(size_t), "fixme");
if ((size_t)(end - begin) < (size_t)TReallyFastRng32::RandMax()) {
Shuffle(begin, end, TReallyFastRng32(Seed()));
} else {
Shuffle(begin, end, TFastRng64(Seed()));
}
}
template <typename TRandIter, typename TRandIterEnd, typename TRandGen>
inline void Shuffle(TRandIter begin, TRandIterEnd end, TRandGen&& gen) {
Y_ASSERT(begin <= end);
const size_t sz = end - begin;
for (size_t i = 1; i < sz; ++i) {
DoSwap(*(begin + i), *(begin + gen.Uniform(i + 1)));
}
}
// Fills first size elements of array with equiprobably randomly
// chosen elements of array with no replacement
template <typename TRandIter, typename TRandIterEnd>
inline void PartialShuffle(TRandIter begin, TRandIterEnd end, size_t size) {
Y_ASSERT(begin <= end);
static_assert(sizeof(end - begin) <= sizeof(size_t), "fixme");
static_assert(sizeof(TReallyFastRng32::RandMax()) <= sizeof(size_t), "fixme");
if ((size_t)(end - begin) < (size_t)TReallyFastRng32::RandMax()) {
PartialShuffle(begin, end, size, TReallyFastRng32(Seed()));
} else {
PartialShuffle(begin, end, size, TFastRng64(Seed()));
}
}
template <typename TRandIter, typename TRandIterEnd, typename TRandGen>
inline void PartialShuffle(TRandIter begin, TRandIterEnd end, size_t size, TRandGen&& gen) {
Y_ASSERT(begin <= end);
const size_t totalSize = end - begin;
Y_ASSERT(size <= totalSize); // Size of shuffled part should be less than or equal to the size of container
if (totalSize == 0) {
return;
}
size = Min(size, totalSize - 1);
for (size_t i = 0; i < size; ++i) {
DoSwap(*(begin + i), *(begin + gen.Uniform(i, totalSize)));
}
}
template <typename TRange>
inline void ShuffleRange(TRange& range) {
auto b = range.begin();
Shuffle(b, range.end());
}
template <typename TRange, typename TRandGen>
inline void ShuffleRange(TRange& range, TRandGen&& gen) {
auto b = range.begin();
Shuffle(b, range.end(), gen);
}
|
