Fisher-yates KO en vba

Boostez vos compétences Excel avec notre communauté !

Rejoignez Excel Downloads, le rendez-vous des passionnés où l'entraide fait la force. Apprenez, échangez, progressez – et tout ça gratuitement ! 👉 Inscrivez-vous maintenant !

Vous êtes un beau parleur et vous dites n'importe quoi. Je vous démontre clairement que vos tirages ne sont qu'une arnaque et, très frustré, je vous demande un exemple : 10 noms, Nom_01 à Nom_10 dans la colonne A, puis vous effectuez 10 tirages aléatoires en utilisant votre « méthode 1 » avec ses 5 étoiles dans les colonnes B et K. Donc, pas de discours commercial tiède, pas de bêtises, juste un résultat concret.
Demander à tourner la page parce qu'on ne peut pas gérer une situation pareille, il faut juste avoir le courage de le faire, c'est de la pure lâcheté.
Je demande un exemple clair, pas des bulles de savon qui éclatent facilement.
 
Je vais vous simplifier votre tâche au maximum. Vous trouverez ci-joint la « méthode de bricolage n° 1 » et la méthode de Fisher-Yates, avec la répartition des nombres dans les colonnes B à K. Une "HEAT MAP" du total a été créée à l'aide de MFC.

Alors, les écarts sont-ils bien visibles ? Je vous prie d'éviter tout discours commercial sur la "RND", et je vous prie de vous excuser.
Vous avez surtout fait des histoires sans rien prouver.
dégonfle le melon
j'ai ouvert ce topic , si la tournure ne te plait pas tu peux toujours zapper
Je devrais quitter la discussion car vous la compliquez inutilement et vous y croyez encore vous-même, c'est le monde à l'envers.

PS.il faut encore pousser le bouton "macro", autrement le fichier était trop grand
 

Pièces jointes

Dernière édition:
demo4.gif

demo4.gif

et pour le problème de la borne haute qui ne sort quasiment jamais avec mon astuce du "+0.999999..."
deux subs de test simple
VB:
Option Explicit

Sub testBorne()
    Dim borne&, count&, i&, x&, itest&
    borne = 50
    For itest = 1 To 200
        For i = 1 To 100
            x = Int(Rnd * borne)
            If x = 50 Then count = count + 1
        Next
    Next
    MsgBox "avec 200 test, " & borne & " est sorti " & count & " fois sur " & 100 & " tirages"
End Sub

Sub testBorne2()
    Dim borne&, count&, i&, x&, itest&
    borne = 50
    For itest = 1 To 200
        For i = 1 To 100
            x = Int(Rnd * (borne + 0.999999))
            If x = 50 Then count = count + 1
        Next
    Next
    MsgBox "avec 200 test, " & borne & " est sorti " & count & " fois sur " & 100 & " tirages"
End Sub
avec la sub 1
1770795976189.png


et la sub 2
1770796043924.png

donc sur 200*100 soit 20 000 tirages
la sub 1 me sort 0 fois(quasiment tout le temps )
la sub 2 me le sort entre 350 et 450 fois

c'est qui le sourd maintenant
 
Bonjour à tous,

Si je peux me permettre le problème n'est pas tant sur VBA.Rnd et ses flows mais sur la boucle qui s'arrête à mi-parcours. C'est de là que vient le mauvais mélange. Sur 10 éléments ça ne se "voit pas" mais sur des arrays plus importantes c'est évident, cf. fichiers de BsAlv et test de Rheeem.
Je ne comprends pas pourquoi la discussion est centrée sur les milisecondes et non sur l'algoritmique en elle-meme.
 
Salut Saboh12617,

Je m'excuse si j'ai employé un langage un peu cru par le passé, c'est donc ma dernière intervention.

Et cher Patrick, va jouer dans le bac à sable pendant que les adultes ont des conversations sérieuses…

Le problème de la borne supérieure n'en est pas un non-problème, regarde la série jointe « Demo2 ». Je supposais que je dois tirer des valeurs parmi 100 éléments pour le premier, et je le fais un million de fois. Le résultat se trouve dans les colonnes A et B. Cela me semble être un résultat statistiquement normal. On peut même en faire une droite de régression, R² = peanuts. Cliquez plusieurs fois sur le bouton « macro ».
1770800600630.png


S'il te plaît, cher Patrick, arrêtez ! Vous vous ridiculisez. À mon avis, vous n'avez pas été en mesure de prouver aucun de vos points.
 

Pièces jointes

Dernière édition:
Mr Bsalv ;et ce sera ma dernière intervention
vous vous excusez et ensuite vous m'envoyez dans le bac à sable
si vous avez du pâté dans les yeux et que vous n'avez pas compris ce que j'ai voulu démontrer
je le redis c'est quand même moi qui ai ouvert ce topic et c'est vous qui devrez m'en dégager!!!?
pour qui vous prenez vous ?perso quand une discussion me lasse pour une raison ou une autre je zappe j'insiste pas
et surtout avec le manque de respect dont vous faites preuve
je prends note de votre comportement
 
et surtout je le redis si la semie boucle vous génère un melange non uniforme(si tant est que l'on puisse exprimer cela comme ça)
ce n'est pas elle la responsable mais bien RND
principe 1
demie boucle --> index boucle interverti avec rnd fois la totale
principe 2
demie boucle -->index boucle interverti avec rnd*les restants apres l'index de boucle (l'inverse du FY)puisque lui boucle a reculons

donc si ce n'est pas uniforme c'est bien le RND qui est responsable

maintenant je vous l'acorde Fy boucle sur la totalité donc oui forcement les valeurs(pas les index) vont changer même plusieurs fois
de même que si je fait 36 fois le tour
c'est en ca que FY que le principe de FY qui soit disant garantie l'uniformité est trompeur par qu'il lui faut boucler sur la totalité
du au fait que rnd va tirer x fois le même index et en délaisser d'autres

je précise que j'ai testé aussi en JS sur une page html le calculateur Random.floor( voir plus puissant encore le crypto.getRandomValues) est beaucoup plus puissant qu'en VBA
même si là aussi on constate des index choisi ou délaissé de façon récurrente mais moins

et je le constate aussi avec ma fonction RNDX perso qui consiste a stocker une matrice d'index dans une collection et qu'a chaque tours l'index tiré est supprimé ce qui fait que la base de tirage n'est jamais la même
sur un tirage en semie boucle j'ai une dispersion plus importante mais en temps je reviens à 14 ms comme la FY
forcément ma fonction vba consomme
DONC C EST BIEN LE CALCULATEUR RND qui délaisse de facon récurrentes et c'est pour ça qu'il ne sont pas deplacé
 
Bonjour à tous,

Si je peux me permettre le problème n'est pas tant sur VBA.Rnd et ses flows mais sur la boucle qui s'arrête à mi-parcours. C'est de là que vient le mauvais mélange. Sur 10 éléments ça ne se "voit pas" mais sur des arrays plus importantes c'est évident, cf. fichiers de BsAlv et test de Rheeem.
Je ne comprends pas pourquoi la discussion est centrée sur les milisecondes et non sur l'algoritmique en elle-meme.
parce que c'est le nerf de la guerre tout simplement, un algo qui fait ce qu'on lui demande mais qui plombe l'uc c'est pas un bon algo
 
Si je peux me permettre le problème n'est pas tant sur VBA.Rnd et ses flows mais sur la boucle qui s'arrête à mi-parcours. C'est de là que vient le mauvais mélange.

En effet avec une boucle qui s’exécute qu'à moitié il faut que les indices pointent sur deux sections différents pour couvrir l’ensemble des éléments ex : pair/impaire c'est une méthode adéquate :
Code:
 pivot = tl \ 2
  For a = 1 To tl Step 2
        b = Int(Rnd * pivot) * 2 + 2
...
Mais cela ne réglera pas le problème des collisions de Rnd donc il reste des éléments qui ne seront pas échangés .
un autre approche simple entrelacement permet la génération des positions uniques mais d'une manière pseudo-aléatoire
Code:
    pivot = tl \ 2
    rd = Int(Rnd * pivot) + pivot
    For j = 1 To pivot
        a = (((j * 101 + rd) Mod pivot) * 2) + 1
        b = ((j * 97) Mod pivot) * 2 + 2
        memo = t(a, 1)
        t(a, 1) = t(b, 1)
        t(b, 1) = memo
    Next

Cette méthode ne fonctionne qu'avec les tableau de taille paire car pour tiré les positons de a et b il faut un nombre éléments équivalent pour les deux moitis
 
re
bonjour @rheem la en fait tu fait une interversion entre deux coté pivot c'est valable aussi mais on a en fait la serie a l'envers avec le chaos sur les deux coté du pivot
autrement dit de 123456 tu arrive 645312 par exemple
la seule solution que j'ai pour l'instant c'est ma fonction perso RNDX qui travail avec une collection a la quelle je supprime la valeur sélectionné a chaque tour autrement il ne peut pas choisir la même valeur 2 fois mais on perd le gain de temps de la semie boucle je travail sur un pool /poolsize avec un tableau c'est prometteur en test pour l'instant
 
et surtout je le redis si la semie boucle vous génère un melange non uniforme(si tant est que l'on puisse exprimer cela comme ça)
ce n'est pas elle la responsable mais bien RND
Salut,
voici une fonction vba qui génère un nombre aléatoire en utilisant des API windows cryptographiques :
VB:
Option Explicit

'==========================
'  Déclarations API
'==========================
#If VBA7 Then
    Private Declare PtrSafe Function CryptAcquireContext Lib "advapi32.dll" _
        Alias "CryptAcquireContextA" (ByRef phProv As LongPtr, _
        ByVal pszContainer As String, ByVal pszProvider As String, _
        ByVal dwProvType As Long, ByVal dwFlags As Long) As Long

    Private Declare PtrSafe Function CryptGenRandom Lib "advapi32.dll" _
        (ByVal hProv As LongPtr, ByVal dwLen As Long, ByRef pbBuffer As Byte) As Long

    Private Declare PtrSafe Function CryptReleaseContext Lib "advapi32.dll" _
        (ByVal hProv As LongPtr, ByVal dwFlags As Long) As Long

    Private m_hProv As LongPtr
#Else
    Private Declare Function CryptAcquireContext Lib "advapi32.dll" _
        Alias "CryptAcquireContextA" (ByRef phProv As Long, _
        ByVal pszContainer As String, ByVal pszProvider As String, _
        ByVal dwProvType As Long, ByVal dwFlags As Long) As Long

    Private Declare Function CryptGenRandom Lib "advapi32.dll" _
        (ByVal hProv As Long, ByVal dwLen As Long, ByRef pbBuffer As Byte) As Long

    Private Declare Function CryptReleaseContext Lib "advapi32.dll" _
        (ByVal hProv As Long, ByVal dwFlags As Long) As Long

    Private m_hProv As Long
#End If

'==========================
'  Initialisation / libération   
'==========================
Public Sub CryptoInit()
    If m_hProv <> 0 Then Exit Sub
    ' PROV_RSA_FULL = 1, CRYPT_VERIFYCONTEXT = &HF0000000
    If CryptAcquireContext(m_hProv, vbNullString, vbNullString, 1, &HF0000000) = 0 Then
        Err.Raise vbObjectError + 1, "CryptoInit", "CryptAcquireContext a échoué."
    End If
End Sub

Public Sub CryptoFree()  'pas obligatoire (fait à la fermeture d'Excel)
    If m_hProv <> 0 Then
        CryptReleaseContext m_hProv, 0
        m_hProv = 0
    End If
End Sub

'==========================
'  Générateurs
'==========================
Private Function CryptoRandom64() As Double
    Dim b(7) As Byte
    Dim d As Double
    If m_hProv = 0 Then CryptoInit
    CryptGenRandom m_hProv, 8, b(0)
    d = b(0) _
        + b(1) * 256# _
        + b(2) * 65536# _
        + b(3) * 16777216# _
        + b(4) * 4294967296# _
        + b(5) * 1099511627776# _
        + b(6) * 281474976710656# _
        + b(7) * 7.20575940379279E+16
    CryptoRandom64 = d
End Function

Public Function CryptoRnd() As Double
    Dim r As Double
    ' 2^64 - 1 ≈ 1.84467440737096E+19
    r = CryptoRandom64() / 1.84467440737096E+19
    ' Sécurité : ne jamais renvoyer exactement 1
    If r >= 1# Then r = 0.999999999999999#
    CryptoRnd = r
End Function

'==========================
'  Shuffle Fisher–Yates
'==========================
Public Sub ShuffleArray(ByRef arr As Variant)
    Dim i As Long, j As Long
    Dim tmp As Variant
    Dim lo As Long, hi As Long

    lo = LBound(arr)
    hi = UBound(arr)

    For i = hi To lo + 1 Step -1
        j = lo + Int(CryptoRnd() * (i - lo + 1))
        tmp = arr(i)
        arr(i) = arr(j)
        arr(j) = tmp
    Next i
End Sub

Public Sub TestShuffle()
    Dim t
    Dim i As Long
    t = Array("A", "B", "C", "D", "E", "F")
    ShuffleArray t
    For i = LBound(t) To UBound(t)
        Debug.Print t(i)
    Next i
End Sub

🎯 CryptoRnd vs Rnd : les avantages et inconvénients​

🟢 CryptoRnd (basé sur CryptGenRandom / API Windows)​

✔ Avantages​

  • Aléatoire cryptographiquement sûr → impossible à prédire, même en analysant des millions de tirages.→ utilisé par Windows pour générer des clés, des tokens, etc.
  • Uniformité parfaite → pas de biais, pas de patterns, pas de corrélation.
  • Indépendant de l’état interne de VBA → pas affecté par Randomize, ni par l’heure, ni par les appels précédents.
  • Idéal pour :
    • tirages sensibles
    • sécurité
    • simulations sérieuses
    • shuffles où l’uniformité est importante
    • benchmarks statistiques

❌ Inconvénients​

  • Beaucoup plus lent que Rnd → même optimisé, il reste 20× à 100× plus lent que Rnd.
  • Dépend de Windows → nécessite l’API advapi32.dll → ne fonctionne pas sur Mac (mais tu es sous Windows, donc OK).
  • Plus complexe à coder → déclarations API, gestion du provider, etc.

🟢 Rnd (générateur pseudo‑aléatoire de VBA)​

✔ Avantages​

  • Très rapide → idéal pour des millions de tirages.
  • Simple à utiliser → Rnd, Randomize, et c’est parti.
  • Toujours disponible → aucune dépendance externe.
  • Idéal pour :
    • jeux simples
    • animations
    • tirages non critiques
    • tests rapides
    • simulations où la sécurité n’a aucune importance

❌ Inconvénients​

  • Pas cryptographiquement sûr → prévisible si on connaît la graine.→ patterns visibles dans les grands volumes.
  • Uniformité imparfaite → biais légers mais mesurables dans les shuffles.
  • Dépend de l’état interne → deux appels successifs peuvent être corrélés.→ Randomize peut réinitialiser la séquence.
Et alors pour l'uniformité quelles différences ?

À N = 10, même en faisant 100 000 tirages, on ne verra aucune différence visible entre Rnd et CryptoRnd. Et c’est parfaitement normal.
Voici pourquoi, et surtout dans quels cas la différence devient réelle.

🎯 Pourquoi on ne voit aucune différence d’uniformité entre Rnd et CryptoRnd​

✔ 1. N = 10 est trop petit​

Avec seulement 10 positions, même un générateur médiocre donne une distribution qui semble uniforme.
Pour voir une différence, il faut :
  • un grand N (100, 500, 1000…)
  • un grand nombre de tirages (100 000, 1 000 000…)
Sinon, les écarts statistiques sont noyés dans le bruit.

✔ 2. Rnd est “assez bon” pour des petits tirages​

Rnd n’est pas cryptographique, mais il reste un bon PRNG linéaire pour :
  • des petits tableaux
  • des shuffles simples
  • des simulations basiques
Il n’a pas de biais énorme sur 10 éléments.

✔ 3. Corrélation​

Les vrais défauts de Rnd sont :
  • corrélations entre tirages successifs
  • faible entropie sur les bits de poids faible
  • période limitée
  • prédictibilité totale

🎯 Quand la différence devient visible ?​

Voici les cas où Rnd commence à montrer ses limites :

✔ 1. Grand N (≥ 100)​

Le shuffle Fisher–Yates dépend fortement de la qualité du RNG. Avec Rnd, on verra :
  • des patterns diagonaux
  • des zones plus denses
  • des biais légers mais mesurables
Avec CryptoRnd, la heatmap devient parfaitement uniforme.

✔ 2. Très grand nombre de tirages (≥ 1 million)​

Rnd commence à montrer :
  • des cycles
  • des répétitions
  • des corrélations entre tirages successifs
CryptoRnd reste parfaitement uniforme.

✔ 3. Tests statistiques sérieux (χ², Kolmogorov–Smirnov, Diehard)​

Là, Rnd se fait démonter. CryptoRnd passe haut la main.

✔ 4. Sécurité, cryptographie, tirages sensibles​

Rnd est prédictible. Si on connait 2 tirages, on peut prédire les suivants.

CryptoRnd est imprévisible, même avec un supercalculateur.

==============================================================

Nullosse et Roger Murdock (Kareem Abdul-Jabbar)
 
@nullosse
merci pour le message que, pour tous les mortels (=tout le monde sauf Patrick Toulon) et les applications, "RND" suffit et est rapide.
Bon, cela dit ...
Je l'ai déjà dit, un tirage est composé de 3 actions :
- lire les noms
- faire le tirage
- coller le résultat.
Pour nos applications, le nombre d'éléments est normallement < 100. Avec ce nombre, en utilisant FY, son temps est environ 1% du total, environ 100 us des 15 ms. Donc, si on sait diviser le temps de FY par 2 en utilisant une méthode fiable, alors on gagne quoi, peanuts ?
Mais alors, il faut traiter tous les éléments et certainement pas la moitié. Voici mon "Fisher_Yates" et je ne sais pas encore le prouver, mais si on prend toujours l'intervalle complèt, cela a l'air de fonctionner plus vite.

Enrichi (BBcode):
Sub M_Fisher_Yates()
     Dim Arr, N1 As Long, N2 As Long, i1 As Long, i2 As Long, SWAP
     Dim Bench As New cBenchmark
     Bench.Start                             'start chrono
     Randomize                               'utiliser SEED
     Bench.TrackByName "debut"               'premier jalon  '
     Arr = Range("Sample").Value2            'lire les données pour le tirage
     N1 = LBound(Arr)                        'lowerbound
     N2 = UBound(Arr)                        'upperbound
     Bench.TrackByName "end READ"            '2ième jalon
     For i1 = N1 To N2                       'boucler tous les éléments
          i2 = Int(N1 + Rnd * (N2 - N1 + 1))    'élément aléatoire
          If i1 <> i2 Then                   'échange nécessaire ?
               SWAP = Arr(i2, 1)             'mémoriser cet élément
               Arr(i2, 1) = Arr(i1, 1)       'échanger les 2
               Arr(i1, 1) = SWAP             'coller l'élément en mémoire
          End If
     Next
     Bench.TrackByName "fin Fisher_Yates"      '3ième jalon
     Range("Sample").offset(, 1).Value2 = Arr     'coller resultat juste à côté
     DoEvents
     Bench.TrackByName "fin WRITE"           '4ième jalon
     Bench.Report                            'créer rapport
End Sub
 

Pièces jointes

Dernière édition:
la seule solution que j'ai pour l'instant c'est ma fonction perso RNDX qui travail avec une collection a la quelle je supprime la valeur sélectionné a chaque tour autrement il ne peut pas choisir la même valeur 2 fois mais on perd le gain de temps de la semie boucle je travail sur un pool /poolsize avec un tableau c'est prometteur en test pour l'instant

Si on dispose d'un Rnd qui génère des positions uniques alors la question ne se pose plus on peut s'en passer de mélange et appliquer les indices directement dans le code, l utilisation de collection est un peut lourde si on doient vefiier l'existence d'un élément et çà a se complique au fur et à mesure l'opération avance et le nombre d'éléments disponibles diminue,,

On peut utiliser la methode FY+Rnd pour générer des indices uniques c'est plus rapide qu'une collection

Code:
Function FYRnd(Optional ByVal InitMax As Long = 0) As Long
Static t() As Long
Static Count As Long
 
    If InitMax > 0 Then
        ReDim t(0 To InitMax)
        Count = InitMax
        Exit Function
    ElseIf Count < 1 Then
        Exit Function
    End If
    
    Dim NewV As Long, V As Long
    NewV = Int(Count * Rnd + 1)
 
    FYRnd = t(NewV)
    If FYRnd = 0 Then: FYRnd = NewV
    V = t(Count)
    If V = 0 Then: V = Count
    t(NewV) = V
    Count = Count - 1
End Function

exemple
Code:
Sub TestFYRnd()
    Dim nBr As Long, t, i As Long
    nBr = 10000
    FYRnd nBr 'initialization
    ReDim t(1 To nBr, 1 To 1)
    For i = 1 To nBr
       t(i, 1) = FYRnd 'indices uniques
    Next
    Range("A1").Resize(nBr) = t

End Sub
 
re
Bonjour @rheem
oui je l'ai fait aussi avec une variable tablo avec un poolsize qui est shunté après sélection mais sur une boucle entière je double le temps
et j'ai découvert aussi que le swap se faisait mieux dans une boucle a reculons du au fait que rnd va prioriser les petits nombre en premier
donc la dessus fisher-yates a raison
avec ma rndX version tableau mon mélange est légèrement mieux (grâce au pushPool que je fait )que fy mais sur une boucle entière je perds en temps d’exécution donc j'élimine cette piste

pour tester mes dires j'ai fait un FY avec boucle en avant
et c'est vrai que le résultat est tout a fait différent
c'est là que l'on se rend bien compte que RND a bien une structure sélective quasi régulière qui se répète tout les x selon la grandeur du tableau
 
Cessez de propager ces discours alarmistes et ces théories du complot.
Voir PJ contenant les contributions modifiées de @Rheeem et @Nullose.
remarques :
  • la manière de boucler Fisher-Yates ascendant/descendant n'a aucune importance
  • la manière de choisir ce chiffre aléatoir (le reste de l'intervalle ou l'intervalle entier) pour faire l'échange n'a aucune importance
  • la manière FY (adapté) est 2 fois plus vite que la méthode "Rheeem" et 3-4 fois plus vite que la méthode "Crypto"
On constate souvent que, dans ce genre de situations, la « force brute » est plus rapide qu'une stratégie plus réfléchie.

RND (après un "randomize") suffit largement pour ce genre de problèmes comme @nullose l'a très bien décrit.
Tous les autres hypothèses ont aucune valeur.

Pour adapter le nombre dans le sample, adapter le paramètre "nombre" dans la module2 en haut et puis lancez la macro "M_Adapter_Sample"
Pour avoir un estimat plus stable du temps "FY", la macro fait 1.000 tirages consécutifs

PS. Benchmark ne crée pas un nouveau report si il a fait le dernier moins qu'une seconde avant le nouveau, donc si vous ne voyez pas un nouveau report dans les colonnes A:G, attendez un petit moment entre 2 lancements consécutifs.
 

Pièces jointes

Dernière édition:
- Navigue sans publicité
- Accède à Cléa, notre assistante IA experte Excel... et pas que...
- Profite de fonctionnalités exclusives
Ton soutien permet à Excel Downloads de rester 100% gratuit et de continuer à rassembler les passionnés d'Excel.
Je deviens Supporter XLD
Retour