-
Notifications
You must be signed in to change notification settings - Fork 16
/
random.txt
351 lines (312 loc) · 23.8 KB
/
random.txt
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
RANDOM
HEADER ==> #<boost/random.hpp>
GENERAL ==> #Il y a deux concepts :
# - les random number generator, RAND_GEN, génèrent une
# suite de seeds de manière pseudo-aléatoire ou
# aléatoire entre un min() et un max()
# - les random number distributions, qui génère des
# nombres aléatoires en fonction de cette seed, mais
# selon une répartition donnée (uniforme ou non),
# dans un range donné (RAND_DST)
#Chacun de ces deux concepts n'est pas lié à une seule
#classe parent, mais toutes les classes d'un même
#concept ont des membres requis et en commun.
#Les deux doivent être unis avec un VARIATE_GENERATOR,
#fonctor générant à chaque operator() un nombre
#aléatoire selon les RAND_GEN_PA et RAND_DST donnés.
CONSEIL ==> #Essayer d'instantier aussi peu que possibles les
#RAND_DST et RAND_GEN_PA, car coûteuse instantiation.
variate_generator #Fonctor unissant un RAND_DST et un RAND_GEN_PA pour
<RAND_GEN_PA_TYPE, #produire simplement des nombre aléatoires en fonction
RAND_DST_TYPE> #de la distribution RAND_DST et du générateur
#RAND_GEN_PA. Il prend leurs types en template.
VARIATE_GENERATOR #Instantie un VARIATE_GENERATOR, lié au générateur
(RAND_GEN_PA_VAR, #RAND_GEN_PA et à la distribution RAND_DST.
RAND_DST_VAR)
VARIATE_GENERATOR() #Renvoie le prochain nombre aléatoire de
#VARIATE_GENERATOR.
VARIATE_GENERATOR.
engine() #Renvoie RAND_GEN_PA
VARIATE_GENERATOR.
distribution() #Renvoie RAND_DST
VARIATE_GENERATOR.min() #Invoque RAND_DST.min()
VARIATE_GENERATOR.max() #Invoque RAND_DST.max()
/=+===============================+=\
/ : : \
)==: PSEUDO-RANDOM GENERATORS :==(
\ :_______________________________: /
\=+===============================+=/
UniformRandomNumber #Désigne toute classe T générant une suite de nombres
Generator #aléatoires selon une distribution uniforme.
#Appelé RAND_GEN dans ma doc.
#Requirements :
# - les fonctions ont une time complexity constante
T::result_type #Est LessThanComparable.
#std::numeric_limits<T::result_type>::is_specialized
#est true
T() #Operator() : renvoie un nombre aléatoire compris entre
#T.min() <= Nombre <= T.max(), de type T::result_type.
#Il s'agit de < T.max() si T::result_type n'est pas un
#entier.
T.min() #Renvoient un T::result_type. T.min() <= T.max().
T.max() #Une fois T instantiés, renvoient toujours la même chose
Pseudo Random Number #Refinement d'UniformRandomNumberGenerator, pour un
Generator #générateur pseudo-aléatoire.
#Requirements :
# - CopyConstructible et Assignable.
# - EqualityComparable (compare la seed)
# - Streamable (<< et >> sauvegardant le state de la
# seed)
T([ARGS]) #Instantie et effectue un seed(ARGS).
T.seed(...) #Modifie la seed de T, en fonction des ARGS.
RAND_GEN_PA ==> #Désigne des classes de boost::rand modelant le
#concept de Pseudo Random Number Generator :
rand_gen_pa::result_type#Typedef vers le type renvoyé par le générateur.
RAND_GEN_PA([ARGS]) #Instantie un RAND_GEN_PA, en faisant ensuite un
#seed(ARGS). ARGS est par défaut 1.
RAND_GEN_PA.seed(INT_VL)#Modifie la seed de RAND_GEN_PA, en fonction de INT_VAL.
#On peut par exemple utiliser std::time(0). La seed
#générée n'est pas égale à INT_VAL.
RAND_GEN_PA.seed #Même chose, mais utilise la suite d'INT_VAL compris
(INPT_ITVR1, INPT_ITVR2)#dans le range. INPT_ITVR1 doit être une VAR, pas une
#VAL temporaire. Le range doit être très grand, sinon
#ça bugue. Je ne vois personnellement pas l'intérêt.
OSTREAM << RAND_GEN_PA #Enregistre la seed de RAND_GEN_PA dans OSTREAM.
ISTREAM >> RAND_GEN_PA #Restaure la seed enregistrée dans ISTREAM vers
#RAND_GEN_PA
RAND_GEN_PA
== RAND_GEN_PA2
RAND_GEN_PA
!= RAND_GEN_PA2 #Teste si les deux RAND_GEN_PA ont la même seed.
LISTE DES RAND_GEN_PA #La voici.
==> # - longueur de cycle : plus grande suite de nombres
# générés possibles avant de recommencer un cycle
# pseudo-aléatoire identique
# - mémoire : nombre de sizeof(INT_VAL) octets requis
# pour le calcul
# - vitesse relative : le plus faible est le plus lent.
# 100% est 10 fois plus rapide que 10%, etc.
#En général :
# - mt19937 est un bon compromis entre les trois
# critères.
# - rand48 si rapidité + mémory compte
# - les lagged_fibonacci* si seule la longueur du cycle
# compte, et pas la mémoire ni la rapidité.
# - les ranlux* si la longueur du cycle et la mémoire
# compte, mais pas la rapidité
+------------------------------+----------------+----------+---------+
| CLASSE | CYCLE LENGTH | MEMORY | VITESSE |
+------------------------------+----------------+----------+---------+
taus88 # 2^88 | 3 | 100% |
rand48 # 2^48 | 2 | 64% |
+------------------------------+----------------+----------+---------+
mt11213b # 2^11213 | 352 | 100% |
mt19937 # 2^19937 | 625 | 93% |
mt19937_64 # 2^19937 | 625 | 38% |
+------------------------------+----------------+----------+---------+
lagged_fibonacci607 # 2^32000 | 1214 | 60% |
lagged_fibonacci1279 # 2^67000 | 2558 | 60% |
lagged_fibonacci2281 # 2^120000 | 4562 | 60% |
lagged_fibonacci3217 # 2^170000 | 6434 | 60% |
lagged_fibonacci4423 # 2^230000 | 8846 | 60% |
lagged_fibonacci9689 # 2^510000 | 19378 | 60% |
lagged_fibonacci19937 # 2^1050000 | 39874 | 60% |
lagged_fibonacci23209 # 2^1200000 | 46418 | 60% |
lagged_fibonacci44497 # 2^2300000 | 88994 | 60% |
+------------------------------+----------------+----------+---------+
ranlux3 # 10^171 | 24 | 5% |
ranlux4 # 10^171 | 24 | 3% |
ranlux64_3 # 10^171 | 48 | 5% |
ranlux64_4 # 10^171 | 48 | 3% |
ranlux3_01 # 10^171 | 24 | 5% |
ranlux4_01 # 10^171 | 24 | 3% |
ranlux64_3_01 # 10^171 | 48 | 5% |
ranlux64_4_01 # 10^171 | 48 | 3% |
ranlux24 # 10^171 | 24 | 5% |
ranlux48 # 10^171 | 24 | 3% |
+------------------------------+----------------+----------+---------+
kreutzer1986 # ? | 257 | 37% |
knuth_b # ? | 1028 | 12% |
minstd_rand0 # 2^31 | 1 | 16% |
minstd_rand # 2^31 | 1 | 16% |
ecuyer1988 # 2^61 | 2 | 7% |
hellekalek1995 # 2^31 | 1 | 2% |
+------------------------------+----------------+----------+---------+
/=+===============================+=\
/ : : \
)==: RANDOM GENERATORS :==(
\ :_______________________________: /
\=+===============================+=/
HEADER ==> #<boost/nondet_random.hpp>
random_device #RAND_GEN aléatoire, et non pseudo-aléatoire.
#N'est pas portable sous Windows. De plus, je suis
#obligé de compiler /usr/share/doc/libboost1.42-dev/
#examples/random_device.cpp avec pour que ça fonctionne.
#Cette classe semble bizarre, avec par exemple entropy()
#qui renvoie toujours 10 ("return 10")...
#Est noncopiable.
#Aux membres de RAND_GEN déjà cités s'ajoute :
RANDOM_DEVICE([CHEMIN]) #Instantiation : il n'y a pas de seed, mais une source
#d'aléatoirité CHEMIN, qui dépend de l'implémentation.
#Sous Linux, c'est /dev/urandom par défaut.
RANDOM_DEVICE.entropy() #Renvoie l'entropie de l'aléatoirité (10 pour moi)
/=+===============================+=\
/ : : \
)==: DISTRIBUTIONS :==(
\ :_______________________________: /
\=+===============================+=/
RANDOM DISTRIBUTION
CONCEPT ==> #Requirements :
# - Streamable, comme Pseudo Random Uniform Gen Concept
T::result_type #
T.reset() #Remet à 0 la seed de T. Ne renvoie rien. Complexité
#constante.
T(UNIFRANDNUMBGENERATOR)#Operator(). Renvoie un nombre aléatoire T::RESULT_TYPE
#selon UNIFORMRANDOMNUMBERGENERATOR et une fonction
#de distribution de T. Complexité constante.
RAND_DST ==> #Toutes les RAND_DST s'instantient avec un template
#prenant, selon la distribution, un ou deux WVAL. Ils
#désignent :
# - si un seul : le result_type et l'input_type.
# - si deux : le premier est le result_type, le second
# l'input_type et le type des arguments du
# constructor.
#Ils modèlent RandomDistributionConcept, mais ajoute
#aussi les membres suivants :
rand_dst<...>::
input_type #
rand_dst<...>::
result_type #
RAND_DST(PARAM_TYPE) #Instantie RAND_DST avec un PARAM_TYPE (de son type)
RAND_DST.min() #Renvoie le nombre minimum/maximum de la distribution
RAND_DST.max() #associée.
RAND_DST.param() #Renvoie le PARAM_TYPE de RAND_DST
rand_dst<..>::param_type#Comme RAND_DST, mais ne contient que les paramètres
#d'instantiation : utile donc pour instantier un
#RAND_DST avec des paramètres existants, de manière
#légère.
#Absent de uniform_01.
#A les mêmes fonctions que rand_dst<...> correspondant,
#dont constructors, sauf :
# - min() et max() si présents
# - typedefs
# - operator()
# - reset()
...::param_type::
distribution_type #Typedef depuis rand_dst<...>.
EXPLICATION DES #Les distributions commençant par uniform_* répartissent
DISTRIBUTIONS ==> #de manière uniforme entre un min et un max :
# - smallint est comme int, mais plus rapide, et il
# faut être sûr que le max peut être atteint par le
# RAND_GEN sous-jacent
# - int produit des int
# - 01 et real produisent des double. Le min et max de
# 01 est 0 et 1.
#Les autres ne répartissent pas de manière uniforme.
#Certains produisent des int, d'autre des double. Voir
#la feuille scannée random.jpg pour plus d'explications.
#Pour ce qui est des cas où quelques unes peuvent se
#produire :
# - triangle_distribution : 50% de chance de tomber
# entre n1 et n2, 50% entre n2 et n3, avec une
# répartition uniforme pour les deux.
# - bernoulli_distribution : jouer à pile ou face avec
# une probabilité de p de tomber sur face
# - normal_distribution : loi normale.
# - binomial_distribution : lancer n fois une pièce
# avec une probabilité de p de tomber sur face, et
# compter le total de face.
# - poisson_distribution : comme binomial, sauf que la
# probabilité p diffère (et est aléatoire) à chaque
# lancer
# - geometric_distribution : nombre de lancer de pile
# ou face avec une probabilité de p de tomber sur
# face à chaque fois, avant de tomber sur face.
#Chaque RAND_DST a des getters renvoyant les constructor
#arguments.
LISTE DES RAND_DST ==> #Voici :
+------------------------+-------------------+------------------+---------------+--------------+--------+
| CLASSE | TEMPLATE |CONSTRUCTOR ARGS. | GETTERS | REMARQUES | VITESSE|
+------------------------+-------------------+------------------+---------------+--------------+--------+
uniform_smallint # <[int]> | min = 0, max = 9 | a(), b() | | 90% |
uniform_int # <[int]> | min=0, max=max_T | a(), b() | | 80% |
uniform_01 # <[double]> | aucun | | | 100% |
uniform_real # <[double]> | min = 0, max = 1 | a(), b() | | 91% |
+------------------------+-------------------+------------------+---------------+--------------+--------+
triangle_distribution # <[double]> | n1 = 0, n2 = 0.5,| a(), b(), c() | | 75% |
| | n3 = 1 | | | |
+------------------------+-------------------+------------------+---------------+--------------+--------+
bernoulli_distribution # <[double]> | p = 0.5 | p() | input_type : | 100% |
| | | | int ; result_| |
| | | | type : bool | |
+------------------------+-------------------+------------------+---------------+--------------+--------+
normal_distribution # <[double]> | μ = 0, σ = 1 | mean(),sigma()| | 44% |
cauchy_distribution # <[double]> | μ = 0, σ = 1 |median(),sigma,| | 46% |
| | | a(), b() | | |
poisson_distribution # <[int[, double]]> | μ = 1 | mean() | | 66% |
binomial_distribution # <[int[, double]]> | n = 1, p = 0.5 | t(), p() | input_type : | 70% |
| | | | int ; n est | |
| | | | du type du | |
| | | | 1er argument | |
| | | | du template | |
+------------------------+-------------------+------------------+---------------+--------------+--------+
geometric_distribution # <[int[, double]]> | p = 0.5 | p() | | 47% |
exponential_distribution# <[double]> | λ = 1 | lambda() | | 53% |
lognormal_distribution # <[double]> | μ = 0, σ = 1 | m(), s() | | 31% |
gamma_distribution # <[double]> | α = 1, β = 1 | alpha(),beta()| | 11% |
+------------------------+-------------------+------------------+---------------+--------------+--------+
Attention :
- absent de la version packagée Ubuntu, mais présent dans headers sources
- namespace boost::random
- à noter que ces CLASSFK existent également :
- DISCRETE_DISTRIBUTION.probabilities() renvoie le premier range sous forme de STD::VECTOR
- PIECEWISE_*_DISTRIBUTION.densities() et interval() renvoient le premier et second range sous forme de STD::VECTOR
+------------------------+-------------------+------------------+----------------------------------------------------+--------+
discrete_distribution # <[int[, double]]> | T2_ITVR, | Pour un x = ITVR[i], où n est la somme est *ITVR : | |
| | T2_ITVR2 | produit un i, avec une probabilité de x/n | |
| | | Ex : { 1, 4, 5 } -> 10% de 0, 40% de 1, 50% de 2 | |
| | | 0,1,2 est l'index range ; et 1,4,5 le weight range | |
| +------------------+----------------------------------------------------+ |
| | RANGE | RANGE possible | |
| +------------------+----------------------------------------------------+ |
| | SIZE_T_VAL, | PREDIC prend un DOUBLE_VAL et renvoit un DOUBLE_VAL| |
| | DOUBLE_VAL1, | Comme ci-dessus, mais : | |
| | DOUBLE_VAL2, | - l'index range est 0,...,n (où n est SIZE_T_VAL)| |
| | PREDIC | - le weight range est le produit de l'application| |
| | | de PREDIC sur le range D1 + n/2,...,D2 - n/2, | |
| | | ce range étant divisé en n élements. | |
| +------------------+----------------------------------------------------+ |
piecewise_linear_ # <[double]> | T_ITVR, T_ITVR2, | Comme discrete_distribution, sauf que : | |
distribution | | T_ITVR3 | - le premier range est l'index range (doit être | |
| +------------------+ croissant) | |
| | RANGE, RANGE2 | - le second range est le weight range (doit être | |
| +------------------+ de même taille) | |
| | SIZE_T_VAL, | Contrairement à discrete_distribution, est continu | |
| | T_VAL1, T_VAL2, | -> une valeur entre deux indexs aura la moyenne de | |
| | PREDIC | deux weights contigus | |
| | | Ex : { 0, 1, 10 } et { 0, 1, 0 } : 50% de 0 à 1, | |
| | | et 50% de 1 à 10 | |
| +------------------+----------------------------------------------------+ |
piecewise_constant_ #<[double[,double]]>| ARGS... | Comme piecewise_linear_distribution (mêmes | |
distribution | | | arguments), sauf que : | |
| | | - le type du weight range est T2 | |
| | | - une valeur entre deux indexs aura non la | |
| | | moyenne, mais la weight du premier index | |
+------------------------+-------------------+------------------+----------------------------------------------------+--------+
A FAIRE ==>
+------------------------+-------------------+------------------+---------------+--------------+--------+
| CLASSE | TEMPLATE |CONSTRUCTOR ARGS. | GETTERS | REMARQUES | VITESSE|
+------------------------+-------------------+------------------+---------------+--------------+--------+
chi squared_distribution# <[double]> | = 1 | n() | | 10% |
fisher_f_distribution # <[double]> | = 1, = 1 | m(), n() | | 5% |
student_t_distribution # <[double]> | = 1 | n() | | 9% |
weibull_distribution # <[double]> | = 1, = 1 | a(), b() | | 25% |
extreme value_ # <[double]> | = 1, = 1 | a(), b() | | 37% |
distribution | | | | | |
uniform_on_sphere_ # <[double[, std:: | = 2 | dim() | | 11% |
distribution | vector<double>]> | | | | |
negative_binominial_ # <[int[, double]]> | = 1, = 0.5 | k(), p() | | 9% |
distribution | | | | | |
+------------------------+-------------------+------------------+---------------+--------------+--------+