Discussion :

[CetTer]

Bonjour,

Mon problème est le suivant : j'ai besoin de générer un ensemble de N nombres entiers aléatoires distincts, compris entre deux bornes (1 et high), afin de sélectionner des lignes dans des grands fichiers et comparer les sous-ensembles entre eux.

A priori la fonction numpy.random.randint est faite pour ce type d'opération, mais elle ne permet pas de générer des nombres aléatoires uniques. Sur un ensemble de test d'environ 50 valeurs comprises entre 1 et 250 j'obtiens régulièrement de l'ordre de 2 à 4 répétitions.

J'ai suivi une autre approche lue sur Stackoveflow : générer une séquence d'entiers via "numpy.arange", la trier de manière aléatoire via "numpy.random.shuffle", et la tronquer finalement jusqu'à la taille désirée.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
a = numpy.arange(1, high+1)
numpy.random.shuffle(a)
a=a[:size]

Les valeurs obtenues sont bien distinctes. Cependant en testant les deux méthodes avec un ensemble de 50 valeurs comprises entre 1 et 250, j'observe que les valeurs proches des bornes (2 et 249) semblent régulièrement mieux représentées avec la première méthode que dans la seconde. Au moins une des deux méthode intoduite un déterminisme dans la distribution des données générées. Dans mon cas cela peut introduire un biais, car la qualité des données présentes dans le fichier tend à diminuer au fur et à mesure que l'on avance dans sa lecture.
Je sais qu'il est difficile de générer de l'aléatoire en informatique, et que j'utilise les deux méthodes de manière naïve, mais auriez-vous une idée d'approche possible pour rendre compte de la différence de distribution entre ces deux méthodes ?

[wiztricks]

Salut,

j'observe que les valeurs proches des bornes (2 et 249) semblent régulièrement mieux représentées avec la première méthode que dans la seconde.

Sur quelques tirages, c'est peut être le hasard...
Pourquoi ne pas écrire quelques lignes de code qui font 10000 tirages, incrémente l’occurrence de chacun des 50 premiers éléments tirés puis regarde comment çà se distribue?

- W

[CetTer]

Bonjour,

J'ai essayé de procéder ainsi via ce script :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
import numpy
import matplotlib.pyplot as plt
 
 
max = 10000
loop = 10000
size = 1000
 
count_1 = numpy.zeros(max+1)
count_2 = numpy.zeros(max+1)
 
 
for i in range(1, loop+1):
	#print(i)
	array_1 = numpy.random.randint(1, max+1, size)
	for nb in array_1:
		#print(nb)
		count_1[nb]=count_1[nb]+1
	tmp_seq = numpy.arange(1, max+1)
	numpy.random.shuffle(tmp_seq)
	array_2 = tmp_seq[:size]
	for nb in array_2:
		#print(nb)
		count_2[nb]=count_2[nb]+1
 
 
for nb in range(1, max+1):
		#print(nb)
	count_1[nb]=count_1[nb]/loop
	count_2[nb]=count_2[nb]/loop
 
count_1=count_1[1:]
count_2=count_2[1:]
 
print("matrice1")
 
print("moyenne="+str(numpy.mean(count_1)))
print("ecart-type ="+str(numpy.std(count_1)))
print("min = "+str(numpy.min(count_1)))
print("minvalue = "+str(numpy.argmin(count_1)))
print("max = "+str(numpy.max(count_1)))
print("maxvalue = "+str(numpy.argmax(count_1)))
print("amplitude = "+str(numpy.max(count_1)-numpy.min(count_1)))
 
print("matrice2")
 
print("moyenne="+str(numpy.mean(count_2)))
print("ecart-type ="+str(numpy.std(count_2)))
print("min = "+str(numpy.min(count_2)))
print("minvalue = "+str(numpy.argmin(count_2)))
print("max = "+str(numpy.max(count_2)))
print("maxvalue = "+str(numpy.argmax(count_2)))
print("amplitude = "+str(numpy.max(count_2)-numpy.min(count_2)))

Les variables globales contiennent en fait les paramères du programme :

max : la borne maximale des tirages

size : la taille d'un tirage

loop : le nombre de tirages

J'effectue deux fois quatre opérations pour étalonner et comparer les deux approches :

1 Générer 50 valeurs entre 1 et 250, avec 1000 tirages
2 Générer 50 valeurs entre 1 et 250, avec 10000 tirages

3 Générer 1000 valeurs entre 1 et 10000, avec 1000 tirages
4 Générer 1000 valeurs entre 1 et 10000, avec 10000 tirages


Le tableau count_1 a comme dimension la taille du subset à produire, et contient, pour chaque position, les fréquences d'apparition de cet indice dans les tirages, avec la méthode numpy.random.randint

Le tableau count_2 contient les mêmes résultats pour" range + shuffle + la troncature"

Je calcule pour chaque test y :
-la plus faible fréquence
-l'indice le moins fréquent
-la plus forte fréquence
-l'indice le plus fréquent
-l'amplitude (différence entre la plus grande fréquence et la plus faible fréquence)

Mais aussi :
-la moyenne des fréquences d'un entier dans les tirages
-l'écart-type des fréquences pour avoir une idée de la distribution par rapport à la moyenne

Le résultat est le suivant :

max	size	loop	méthode	moyenne	écart-type	plus faible fréquence[br]	valeur moins fréquente[br]	plus forte fréquence	valeur la plus fréquente	amplitude
250	50	1000	numpy	0.2	0.0142464030548	0.164	108[br]	0.24	42	0.076
250	50	1000	range + shuffle + truncate	0.2	0.013300225562	0.165	105	0.241	148	0.076
250	50	10000	numpy	0.2	0.0044664527312	0.1887	206	0.2105	154	0.0218
250	50	10000	range + shuffle + truncate	0.2	0.00404272185538	0.1889	170	0.2119	170	0.23
10000	1000	1000	numpy	0.1	0.00984313974299	0.062	8909	0.138	321	0.076
10000	1000	1000	range + shuffle + truncate	0.1	0.00949116431214	0.069	8489	0.139	7990	0.07
10000	1000	10000	numpy	0.1	0.00316757351927[br]	0.0852[br]	5190	0.1117	566	0.0265
10000	1000	10000	range + shuffle + truncate	0.1	0.00303091009434	0.0872	9873	0.1121	5252	0.0249

On constate que :
-la moyenne des fréquences correspond en fait au rapport taille du tirage/borne_supérieure du tirage
-dans tous les cas de figures, l'approche "range + shuffle + troncature" donne un tableau ayant un écart-type plus petit que randomint. Cela signifie qu'elle donne systématiquement une meilleure distribution, même si l'écart est petit
-plus on fait d'itérations, moins ce gain est important
-les amplitudes (intervalle entre la plus faible fréquente et la plus forte fréquence d'un entiers dans les tirages) diminuent sensiblement en fonction du nombre de tirage.

On observe aussi que la valeur la plus fréquente est toujours à gauche de la médiane avec randint, à droite avec shuffle + la troncature...

Cela tend quand-même à montrer que l'approche combinant range, shuffle et la troncature donne systématiquement une meilleure distribution que randint. L'une des deux approches parît bien "plus aléatoire que l'autre", il y a comme un problème (intéressant)...
Pour l'anecdote, j'ai fait un second essai en intervertissant l'ordre d'exécution des deux algorithmes dans la boucle qui montre la même tendance.
Mais il faudrait effectuer ce benchmark sur d'autres plateformes matérielles pour généraliser cette conclusion.

[tyrtamos]

Bonjour,

Juste une suggestion.

Il existe des générateurs de nombres pseudo-aléatoires qui sont meilleurs, au point d'être reconnu en cryptographie. Par exemple l'algorithme de "Blum Blum Shub" (https://fr.wikipedia.org/wiki/Blum_Blum_Shub). On trouve sur Internet des codes Python avec cet algorithme. J'ai même travaillé un peu cette question (en amateur, donc sans garantie!): http://python.jpvweb.com/python/mesr...id=genalea_bbs. Il manque juste un test du khi2 pour vérifier la qualité du code.

Il y a d'autres générateurs de même niveau comme Fortuna (https://fr.wikipedia.org/wiki/Fortuna_(cryptographie)).

[wiztricks]

Salut,

-la moyenne des fréquences correspond en fait au rapport taille du tirage/borne_supérieure du tirage

Tirer 50 parmi 250 va donner la même probabilité que tirer 1 parmi 5.
La différence étant que le nombre de tirages pour obtenir la probabilité calculée de 1/5 sera bien plus important.

Vous pourriez vous amuser à trouver une valeur approchée de ce nombre de tirages pour 1 parmi 5, 2 parmi 10, 3 parmi 15, 4 parmi 20, ....
note: on doit aussi pouvoir calculer le nombre de tirages minimum pour que la fréquence d'apparition de chaque nombre à epsilon de la probabilité calculée. Mais on sort de la programmation pour aller dans le domaine des statistiques.

Ceci dit, si on sort une fréquence assez bonne pour un grand nombre de tirages, çà veut dire aussi que ces fréquences seront bien plus éloignées de 1/5 après 10%, 30%, ... de tirages.

Tout çà pour dire qu'il est difficile en l'état de savoir si ce que vous constatez est "normal" (il faut plus de tirages pour que çà converge à un epsilon donnée) ou si cela traduit un biais dans l'algo. qui se cache derrière "random".

- W