Mélanger un tableau sans sort
Je suis à la recherche d'une discussion sur le forum ici qui expliquait pourquoi il ne faut pas utiliser sort pour mélanger un tableau mais après 30 minutes je ne l'ai pas trouvée.
Dans mes archives, j'ai juste retrouvé le code à utiliser à la place :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function melange(tableau)
{
let i, j, element;
i = tableau["length"];
while (i > 1) {
j = Math.floor(Math.random() * i--);
element = tableau[i];
tableau[i] = tableau[j];
tableau[j] = element;
}
return tableau;
} |
et j'ai aussi le code qui permet de faire la comparaison et où on voit que le mélange avec "sort" n'est pas du tout équilibré :
Code:
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
| <script>
function melange_DECONSEILLE(tableau)
{
return tableau.sort(e => 0.5 - Math.random());
}
function melange_PAS_RAPIDE(tableau)
{
var i;
var j;
var index;
var tableau2;
index = {};
tableau2 = [];
i = tableau.length;
while (--i>=0) {
while (index[j = Math.floor(Math.random()*tableau.length)]===true) {}
index[j]=true;
tableau2[i]=tableau[j];
}
return tableau2;
}
function melange_ACCEPTABLE(tableau)
{
var i;
var j;
var tableau2;
tableau2 = [];
i = tableau.length;
while (--i >= 0) {
tableau2[i] = tableau[j = Math.floor(Math.random()*(i+1))];
tableau.splice(j,1);
}
return tableau2;
}
function melange_TROP_BIEN(tableau)
{
let i, j, element;
i = tableau["length"];
while (i > 1) {
j = Math.floor(Math.random() * i--);
element = tableau[i];
tableau[i] = tableau[j];
tableau[j] = element;
}
return tableau;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
// comparaison des méthodes
function test(fonction_melange)
{
let tableau;
let valeurs = ["A", "B", "C"];
console.time(fonction_melange);
let verification = {};
let i = 100000 * fact(valeurs["length"]);
while (--i >= 0) {
tableau = window[fonction_melange]([...valeurs]);
verification[tableau] = !(tableau in verification) ? 1 : verification[tableau] + 1;
}
console.timeEnd(fonction_melange);
affiche_resultat(verification);
}
function affiche_resultat(verification)
{
let cles = [];
let somme = 0;
for (const cle in verification) {
cles.push(cle);
somme += verification[cle];
}
let moyenne = Math.floor(somme / cles.length);
cles.sort();
cles.forEach(cle => {
let diff = verification[cle] - moyenne;
console.log(cle + " : " + verification[cle] + " (" + diff + ", " + (diff / moyenne * 100).toFixed(1) + " %)");
});
console.log("=== moyenne : " + moyenne + " ===");
}
function fact(nbr)
{
// Si nbr = 0 la factorielle retournera 1
if (nbr === 0) {
return 1;
}
// appelez à nouveau la procédure récursive
return nbr * fact(nbr - 1);
}
test("melange_DECONSEILLE"); // mélange déséquilibré
test("melange_PAS_RAPIDE"); // performances : risquées, toutes les combinaisons possibles : oui, probabilités identiques : oui.
test("melange_ACCEPTABLE"); // performances : moyennes, toutes les combinaisons possibles : oui, probabilités identiques : oui.
test("melange_TROP_BIEN"); // performances : bien, toutes les combinaisons possibles : oui, probabilités identiques : oui.
</script> |
Donc si quelqu'un sait comment retrouver cette discussion, ça permettrai de rendre à César ce qui lui appartient.
Ou alors si vous savez expliquer pourquoi l'utilisation de sort produit cela, lancez vous ;)
