patricktoulon
XLDnaute Barbatruc
Expérience pratique : Pourquoi “Fisher-Yates” n’est pas toujours la meilleure option en VBA
Bonjour à tous,
cette question est venue sur le forum diverse fois (tirage loto ,creation d'equipes, match,etc...)
a savoir faire un tirage au sort dans un array ,une plage ,etc...
Je voulais partager une expérience concrète sur le mélange de tableaux en VBA, avec benchs et analyses détaillées,
qui, à mon avis, casse un mythe persistant autour de Fisher-Yates.
Contexte
On sait tous que l’algorithme de Fisher-Yates est présenté comme la référence absolue pour mélanger un tableau,
Et surtout!! avec la promesse que chaque élément a exactement la même chance d’être tiré.
Mais… cette promesse repose sur deux conditions essentielles :
- un générateur pseudo-aléatoire uniforme parfait
- un langage capable de gérer correctement les opérations bitwise et les overflows (C/C++ par exemple)
Or en VBA, on utilise généralement Rnd :
- pas uniformément parfait
- état interne caché et corrélé
- relativement lent
Donc, dans pratique en VBA , la garantie théorique n’est plus respectée.
Les algorithmes testés
Jai comparé trois méthodes pour mélanger des tableaux :
Méthode 1 : Mélange partiel de 1 à pivot central avec ( Rnd sur tout le tableau)
calcul de l'index de l'items interverti avec l'index de boucle: b = Rnd * (tl - 1) + 1
Méthode 2 : Mélange partiel de 1 à pivot central avec ( Rnd sur la section restante)
calcul de l'index de l'items interverti avec l'index de boucle : b = a + (Rnd * (tl - 1 - a))
Méthode 3 :le fisher-yates
Code:
Fisher-Yates classique
For i = UBound(arr) To LBound(arr) + 1 Step -1
j = Int((i - LBound(arr) + 1) * Rnd + LBound(arr))
'ici on swicth arr(i) et arr(j)
Next3 Résultats mesurés Algorithme / Temps
nb:il peut arriver quelques fois ou c'est la méthode 1 qui l'emporte
Sur 40 éléments
- Mélange1 23 µs
- Mélange2 24 µs
- Fisher-Yates 28 µs
- Mélange1 7,68 ms
- Mélange2 6,56 ms
- Fisher-Yates 15 ms
Analyse: et performance
Les méthodes 1 et 2
sont environ 2 fois plus rapides que Fisher-Yates sur 50 000 items ou un tableau plus petit ême 40 items
La méthode 2 est légèrement plus rapide que la méthode 1, malgré un calcul "Aparament !! plus lourd”.
Explication :
la réduction de la plage de tirage (tl - 1 - a) diminue le coût interne de Rnd et la conversion implicite en Long dans VBA.
et on atteint jamais plus qu'un calcul fois la plage de donnée entière / 2
Qualité du mélange
Pour un usage pratique dans Excel (jeux, désordre visuel, tirages simples), mélanger la moitié du tableau suffit à casser l’ordre.
La Méthode Fisher-Yates:
n’apporte aucun avantage perceptible ici, et sa “garantie mathématique d'uniformité ” n’est pas respectée à cause de Rnd.
Limites des portages C++
Les techniques bitwise comme XorShift fonctionnent en C/C++ mais sont fragiles en VBA : overflow, type signé, zéro état → générateur mort.
Essayer de remplacer Rnd par XorShift ou autres PRNG bas niveau ne vaut pas le coup dans Excel.
Conclusion:
au final
Fisher-Yates :
référence théorique :mais dans les faits en vba avec Rnd il ne respecte pas sa ganrantie d'uniformité
en VBA avec Rnd = surdimensionné, plus lent
Méthode 2 (pivot + section restante)
Plus rapide, fiable et suffisante pour “foutre le chaos” dans un tableau de lbound à ubound
et se rapprocher au plus près (mais même marge de duplicité de tirage que fisher-yates) d'un pseudo tirage uniforme
Moralité :
En VBA, privilégiez la pragmatique et le chrono, pas les dogmes théoriques.
une , 1/2 boucle + Rnd restreint fait le même job que Fisher-Yates… mais beaucoup plus vite.
a partir de gros volumes: temps /2 et c'est exponentiel en montant dans le volume de donnée a mélanger
les petites sub qui m'ont permis de vérifier tout ça
la méthode 1
VB:
Sub algomelange()
'patricktoulon
Dim t, a&, b, memo, pivot&, tl
Dim bench As New cBenchmark
Randomize
ReDim t(1 To counttableau, 1 To 1)
tl = UBound(t)
pivot = Int(UBound(t) / 2)
'on compte que l'algo
Debug.Print "test melange avec " & counttableau & "; items"
bench.Start
For a = 0 To pivot + 1
b = Rnd * (tl - 1) + 1
memo = t(a + 1, 1)
t(a + 1, 1) = t(b, 1)
t(b, 1) = memo
Next
bench.TrackByName " fin de melange"
Cells(1, "b").Resize(UBound(t)) = t
End Subla méthode 2
VB:
Sub algomelange2()
'patricktoulon
Dim t, a&, b, memo, pivot&, tl
Dim bench As New cBenchmark
Randomize
ReDim t(1 To counttableau, 1 To 1)
tl = UBound(t)
'on compte que l'algo
Debug.Print "test melange2 avec " & counttableau & "; items"
bench.Start
For a = 1 To tl / 2
b = a + (Rnd * (tl - 1 - a))
memo = t(a + 1, 1)
t(a + 1, 1) = t(b, 1)
t(b, 1) = memo
Next
bench.TrackByName " fin de melange2"
Cells(1, "b").Resize(UBound(t)) = t
End Subla méthode Fisher-Yates
VB:
Sub FisherYatesShuffle()
' Mélange un tableau 1D en place avec l'algorithme de Fisher-Yates
Dim i As Long, j As Long
Dim temp As Variant
Dim arr
Dim bench As New cBenchmark
ReDim arr(1 To counttableau, 1 To 1)
Debug.Print "test Fisher-yates avec " & counttableau & "; items"
bench.Start
Randomize ' Initialise le générateur de nombres aléatoires
For i = UBound(arr) To LBound(arr) + 1 Step -1
j = Int((i - LBound(arr) + 1) * Rnd + LBound(arr)) ' indice aléatoire entre LBound et i
' échange arr(i) et arr(j)
temp = arr(i, 1)
arr(i, 1) = arr(j, 1)
arr(j, 1) = temp
Next i
bench.TrackByName " fin de melange fisher-yates"
Cells(1, "c").Resize(UBound(arr)) = arr
End Subles resultats du bench pour 40 items
Code:
test melange avec 40; items
IDnr Name Count Sum of tics Percentage Time sum
0 fin de melange 1 229 100,00% 23 us
TOTAL 1 229 100,00% 23 us
Total time recorded: 23 us
test melange2 avec 40; items
IDnr Name Count Sum of tics Percentage Time sum
0 fin de melange2 1 242 100,00% 24 us
TOTAL 1 242 100,00% 24 us
Total time recorded: 24 us
test Fisher-yates avec 40; items
IDnr Name Count Sum of tics Percentage Time sum
0 fin de melange fisher-yates 1 278 100,00% 28 us
TOTAL 1 278 100,00% 28 us
Total time recorded: 28 usles résultats du bench pour 50 000 items
Code:
test melange avec 50000; items
IDnr Name Count Sum of tics Percentage Time sum
0 fin de melange 1 65 283 100,00% 6,53 ms
TOTAL 1 65 283 100,00% 6,53 ms
Total time recorded: 6,53 ms
test melange2 avec 50000; items
IDnr Name Count Sum of tics Percentage Time sum
0 fin de melange2 1 67 101 100,00% 6,71 ms
TOTAL 1 67 101 100,00% 6,71 ms
Total time recorded: 6,71 ms
test Fisher-yates avec 50000; items
IDnr Name Count Sum of tics Percentage Time sum
0 fin de melange fisher-yates 1 127 201 100,00% 13 ms
TOTAL 1 127 201 100,00% 13 ms
Total time recorded: 13 msJe dépose un fichier ici si vous voulez tester le module classe benchmark est inclut
Pardon de casser le le mythe 🤣 🤣
Patrick