Fisher-yates KO en vba

[patricktoulon]

1 si pour toi c'est une discussion de sourd c'est simple tu clique ailleurs déjà
2 quand tu dis que c'est moins le chaos dans le seconde partie là encore tu te trompe puisque c'est toujours rnd qui décide
3 après les temps que tu annonce ne correspondent pas en terme de pourcentage a ce que j'ai moi sur 50 000 items
a savoir en moyenne les temps d’exécution diminue de 40 à 50% dans les méthode1 et 2 par rapport a la FY

dans ce topic qui n'est pas une question( je crains fort que tu n'es pas compris ça) je met juste en lumière certaine choses prétendument effectives avec FY qui ne le sont pas avec VBA a cause justement du calculateur logique RND

votre dernière réaction n'avait aucune valeur ajoutée.

on croit rêver j'ai même montré les benchs pour appuyer mes dires
4 IA dont 2 pro m'ont confirmé ces constats ,non bsalv est meilleur que tout le monde

pour info ce que j'avance je l'ai testé dans tout les sens avant d'en parler
après tu fait bien ce que tu veux ça te regarde si tu préfère FY va y
mais évite de monter sur tes grand chevaux avec moi tu gagnera pas avec des phrases du genre" parler à un sourd "
ou "aucune valeur ajouté"
il faut dégonfler le melon là
j’apprécie moyennement
mes constats ayant été couchés sur la page je clos le sujet
Patrick

 

[bsalv]

je commence avec des choses qu'on est d'accord

Bon, 10.000 tirages aleatoires avec 50 éléments. la lignes rouge, methode1 et 2 avaient besoin de 170-180 msec donc 17-18 microseconde et FY 519 millisec, donc 52 microsec, 295% en plus comparé avec les TS oubien pour les TS votre 40-50% en moins (ici donc 35%) comparé avec FY.
C'est un peu plus que j'avais supposé, parce que FY fait 2 fois plus de boucles. Si on cumule les différents étapes, alors FY sera le double des 2 autres méthodes. Aucune discussion, FY est >=2 fois plus lent pour le tirage et en total environ 2 fois plus lent. (on n'aura pas besoin de la ligne "fin compter" par exemple)

MAIS, la feuille "Blad3"), 100 tirages aleatoire de 50 éléments dans les colonnes. Les cellules oranges sont encore à leur position originale, Comptez le nombre de ces cellules sur une ligne dans la colonne CX. En moyenne 2 serait normal et on voit cela pour les 25 premières lignes, mais je dis que la 2ième moitié les lignes 26-50 ne sont pas bonnes, c'est une catastrophe, votre point 2 dans la réaction précédente.
L'objectif de ce poste était un tirage aléatoire de X éléments, bon, on a passé du temps pour savoir le procès le plus vite, okay, méthode 1 et 2 sont 2 fois plus vite, mais elles ne sont pas du tout des tirages aléatoires, elles ne sont pas fiables et cela n'a rien à voir avec RND, oui, RND n'est pas sans 100% random, mais c'est parce que vous ne faites que la moitié des boucles et si vous ne voyez/comprenez pas cette erreur, alors ce n'est plus nécessaire de discuter.
Au revoir, je quite cette discussion

 

[patricktoulon]

519 millisec, donc 52 microsec

ben déjà là non on est pas d'accord
c'est seconde/ millisecondes/microseconde/nanoseconde
dont 519 ms=519000µs et pas 52
quand aux items qui pourraient être a leur place c'est le principe du hasard ca tombe comme ca tombe
mais avant revoit ta table de conversion
1sec=1000 millisecondes

1000 000 microsecondes​

1000 000 000 nanosecondes​

​

pour le chaox​

la boucle commence à lbound​

exemple sur 50​

1 echange 2 a 50​

2echange=3 à 50​

3 echange=4 à 50​

etc.etc..jusqu'a moitié​

alors oui il est possible par exemple au 23 echange avec 24 a 50et cet item etait avant le 23 donc oui il es possible qu'il revienne a saplace​

il est possible aussi que certains au final ne soit jamais choisi​

mais c'est le principe du hasard justement​

il est possible aussi que certains revienne justement a leur place originale​

​

 

[laurent950]

Bonsoir @patricktoulon

Je pense que tu peux gagner du temps en typant tes variables et tableaux en Long plutôt qu'en Variant.
Dans ton post #1, tu devrais voir une nette amélioration du chrono en appliquant cela.

 

[patricktoulon]

Bonsoir laurent certainement que le typage va y faire quelque chose
le but de ce topic c'est de montrer que le probabilisme unifome prétendu par fisher-yates et nul et non avenue en vba
et j'ai découverts aussi le fait que rnd a tendance a éliminer le plus souvent la borne haute de son tirage

 

[Saboh12617]

Bonjour à tous,

Si je peux me permettre, la remarque de BsAlv sur le problème du parcours jusqu'à n/2 en Fisher-Yates like est justifiée. Cette astuce ne permet pas de mélanger correctement le tableau, surtout dans la partie "non parcourue".

Une petite explication :

Il y a un risque pour les éléments dan [n/2..n] de ne jamais être parcourus, si les éléments dans [1..n/2] ne leurs tombent pas dessus. Pour la méthode 1, qui va tirer pour [1..n/2] un élément dans [1..n], on a

Notons P(k) la probabilité pour qu'un élément k dans [1..n] soit choisi. P(k) = 1/n. Donc la probabilité de non pick k est Pn(k) = 1 - 1/n.

Maintenant, si on répète t fois, on obtient

Pn(k),t = (1- 1/n)^t.

Puisque l'on parcourt t = n/2 fois le tableau, on a

Pn(k) = (1- 1/n)^(n/2)

Le risque de ne pas avoir permuté l'élément k après le parcourt.

Pour n grand, on peut passer par la limite sachant que lim[n->+inf] (1+x/n)^n = e^x.

On a lim Pn(k) -> e^(-1/2) = 0,606 = 60 % des éléments de la seconde moitié du tableau ne seront jamais permutés.

Sachant que ce risque ne s'applique qu'à la moitié non parcourue de l'array (les n/2 premiers items étant étudiés directement par la boucle), on a un risque que globalement

1/2 * 60% = 30% du tableau ne soit pas permuté (en ignorant la contribution en O(1/n) que les éléments de [1..n/2] ne soient pas permutés (retombent sur eux-memes)).

Ce qui corrobore l'observation de @bsalv :

"Mais (!!!) il y a ca. 15.000 éléments (30%) qui sont encore à leur position originale, tous à partir de la position 25.000, parce qu'on n'a traité que la moitié des élements."

La méthode 2 améliore cela mais même si l’on restreint la recherche de b au suffixe dynamique [a..n-1], il reste le problème qu'à l’itération a on ne fait pas de tirage "sans remise globale" : on peut retomber plusieurs fois sur le même indice à travers les itérations, et donc skipper autant de permutations.

Donc oui, mon avis personnel c'est que sur de petites array cela est sans doute négligeable, et en effet en VBA on cherche souvent la perf. en réduisant la longueur des boucles, mais bon on ne peut pas trop tricher avec les lois mathématiques surtout sur de grands nombres.

Perso pour les mélanges simples j'aime bien utiliser une méthode assez similaire dans l'idée de la découpe : je coupe l'array en 2 et je vais mapper à chaque item de l'array1 un item de l'array2, que je retire de la pioche. Ainsi je force une permutation totale. Cependant bien entendu on n'est pas du tout sur un mélange aléatoire, mais bon c'est suffisant pour pas mal d'applications "simples". C'est d'ailleurs un peu le problème de la méthode 2, même si l'on réduit la taille de la pioche au fur et à mesure, on peut retomber plusieurs fois sur le même élément et en skipper un autre.

Je peux me tromper, je suis loin d'être expert en probabilités, mais je pense qu'il serait utile d'indiquer ce "30% de risque de non-permutation sur gros volumes" à côté de l'algo 1.

 

[Rheeem]

Voila mon test sur le nombres déplacement pour chaque éléments , on constate que les deux algos proposés font un mélange partiel vu le nombre d'éléments ignorés 15000 pour la pemiere et 12000 la seconde :
l'idéal il ne devrait avoir qu'un seul déplacement pour chaque élément,

Mélange 1
Dép	éléments
0	15199
1	22661
2	9523
3	2220
4	352
5	42
6	2
7	1

Mélange 2
Dép	éléments
0	12566
1	27270
2	8119
3	1726
4	284
5	33
6	1
7	1
 
 FY
Dép	éléments
0	0
1	24999
2	12570
3	6086
4	3207
5	1597
6	752
7	393
8	205
9	106
10	46
11	19
12	9
13	5
14	3
15	2
16	0
17	1

 

[bsalv]

je dois réagir sur lepoint que je ne sais pas la différence entre nano-, micro- et millesecondes !!!!

on fait 1.000.000 tirages aléatoires avec Fisher-Yates avec 50 éléments, on doit faire 49 (=n-1) boucles internes. La durée totale était 61.9 sec (Benchmark) ou 69 sec (0.069 *1000, avec timer, donc comparable) dont 51.8 sec étaient pour le tirage senso stricto. 51.8 sec / 1.000.000 = 51.8 microseconde dû à FY
Même truc pour méthode 1 : 1.000.000 tirage aléatoires, mais on ne fait que 25 (n/2) boucles internes. La durée totale était 20.1 sec (Benchmark) ou 27 sec (0.027 *1000, avec timer, donc comparable) dont 10.7 sec étaient pour le tirage senso stricto. 10.7 sec / 1.000.000 = 10.7 microseconde dû à méthode 1.

Donc si on ne regarde que la partie "tirage" pour un tirage unique et 50 éléments il y a une différence de 51.8-10.7 = 41.1 microseconde, peanuts, mais à mon avis FY fait tous les boucles nécessaire et méthode 1, c'est simplement une violation du terme "tirage aléatoire". C'est vrai que "RND" est pseudo-aléatoire, mais l'erreur qu'on fait ici est infiniment plus grand

 

[patricktoulon]

re
non je répète
si tu me dit 51.8 secondes ce n'est n'est 51.8microsecondes
tableau exprimé en centième

donc 51.8 secondes ca fait 5 1800 000 microsecondes

en fait la ou vous trompez dans l'annalyse de ma méthode et surtout la2 c'est que vous croyez que je melange que la moitié
et ce n'est pas ça du tout
j’intervertis l'index de boucle avec la totalité pour la 1 et pour la 2 c'es index de boucle a ubound qui peut être selectionnée
et même si rnd choisi 1 2 3 4 10 fois le même ce ne sera jamais la même valeur puis qu'elle a été changée dans le rnd précédent
Alors oui peut être est ce moins uniforme je sais pas c'est rnd qui décide finalement

et surtout de même que FY d'ailleurs
cela dis si vous tesez la methode 2 en enlevant le "/2(pour les puristes)" vous verrez que je suis quand même plus rapide que FY
de beaucoup moins certes

 

[patricktoulon]

juste pour info si je fait l'ensemble du tableau avec la methode2
comparaison avec FY

test melange2 avec 50000; items
IDnr  Name              Count  Sum of tics  Percentage  Time sum
0      fin de melange2      1      131 846     100,00%     13 ms
      TOTAL                 1      131 846     100,00%     13 ms

Total time recorded: 13 ms

test Fisher-yates avec 50000; items
IDnr  Name                          Count  Sum of tics  Percentage  Time sum
0      fin de melange fisher-yates      1      155 825     100,00%     16 ms
      TOTAL                             1      155 825     100,00%     16 ms

Total time recorded: 16 ms

ça veut dire 16 000 microsecondes

 

[Saboh12617]

Sans vouloir insister je pense que la conclusion de @bsalv est correcte :

"c'est simplement une violation du terme "tirage aléatoire". C'est vrai que "RND" est pseudo-aléatoire, mais l'erreur qu'on fait ici est infiniment plus grand"

Les codes proposés permettent bien d'effectuer des permutations sur une array mais ils sont trop "lazy" pour respecter les règles de tirage aléatoire, c'est ce que constatent @bsalv et @Rheeem sur de gros volumes.

• " en fait la ou vous trompez dans l'annalyse de ma méthode et surtout la2 c'est que vous croyez que je melange que la moitié
  et ce n'est pas ça du tout"

C'est bien ce que font les 2 codes, on s'arrète à pivot = Int(UBound(t) / 2) donc la moitié.

• "la methode 2 en enlevant le "/2(pour les puristes)""

Oui certes on va jusqu'au bout en utilisant For a = 1 To tl – 1 cependant il y a encore 2 légers problèmes. Dans le choix des bornes : b = a + (Rnd * (tl - 1 - a))
Cela n'est pas correct, il faut utiliser b = a + [B][U]Int[/U][/B](Rnd * (tl - a + 1)) car sans Int on passe par la conversion interne VBA qui peut arrondir au supérieur. Enfin c'est une supposition car je pense que c'est un oubli, tu l'avais mis dans la méthode 1.

Et ensuite dans le swap il faut échanger t(a, 1) plutôt que t(a + 1, 1) car sinon on va toujours skip le premier élément. Ce qui donne :

For a = 1 To tl - 1
    b = a + Int(Rnd * (tl - a + 1))
    memo = t(a, 1)
    t(a, 1) = t(b, 1)
    t(b, 1) = memo
Next

On retombe sur FY, et d'ailleurs les temps de traitement sont identiques dans ton dernier test à 3 ms près, puisqu'on fait le même traitement.