Fisher-yates KO en vba

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.

Cliquez pour agrandir...

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

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

519 millisec, donc 52 microsec

Cliquez pour agrandir...

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

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.

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

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.

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,

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

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

juste pour info si je fait l'ensemble du tableau avec la methode2
comparaison avec FY
ça veut dire 16 000 microsecondes

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"

Cliquez pour agrandir...

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 :
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.

bon, je suis obligé de me défendre une autre fois. 😡
La différence entre nano-, micro-, milli- et secondes, cela est d'un niveau "débutant" qu'on peut lire dans des livres comme "Maths for dummies".
Je n'ai pas fait une erreur contre cela ! Comme formation d'ingénieur, je connais bien cela !
Ce sujet n'a jamais tenu ses promesses. Les méthodes 1 et 2 ne sont pas des tirages aléatoires, puisqu'elles ne couvrent que la moitié du champ, et sont donc beaucoup plus rapides, mais comme souvent, la vitesse est un inconvénient. Par conséquent, ces deux méthodes seront désormais ignorées.
L'advantage de ce topic est que j'ai appris l'outil incroyable "Benchmark" pour chronomètres plusieurs phases, c'est ce que j'ai fait dans le PJ.
Bon, il restait que la méthode Fisher-Yates à utiliser, la référence pour ce genre de problèmes.
Les feuilles "Blad1", "Blad2" et le graphique (les 2 axes sont logarithmes) montrent les temps pour réaliser tout avec 3 temps principales dans la macro "M_FY" :

• "End READ" = le temps pour lire les données originales
• "fin inner loop" = le temps pour le tirage Fisher-Yates
• "Fin Write" = le temps pour coller la matrice dans la feuille

Les colonnes "A:F" de "blad1", c'est le report du "Benchmark" et en colonne F les temps en ns, us, ms et s. La colonne C "Count" montre le nombre de fois qu'on a cumulé, c'est le nombre de loops qu'on a fait (ici 100). Donc, en colonne G, il faut diviser la colonne F avec la colonne C.
La macro "Test_FY" lance le "benchmark" et puis lance 100 fois la macro "M_FY" avec un certain nombre pour le tirage (normallement 50). A certains lignes de les macros sont des jalons pour le benchmark et comme ça, on est capable de cumuler 100 fois les parties "READ", "Fisher-Yates" et "Write". Les autres jalons sont à ignorer, ils sont trop petits.

Bon, normallement on a quoi, 5 à 100 éléments dans le tirage. Le tableau de la feuille "Blad2" montre les temps du "Benchmark"et on y voit que FY fait cela en 12 à 66 microsecondes. Si on veut utiliser les 2 autres méthodes (qu'on ne peut pas appeler "tirage aléatoire") on gagne quelque microsecondes, mais la partie "FY" dans le total "READ + Tirage + WRITE" est maximal 5%, donc à ignorer. Oubliez ces méthodes, catastrophe totale !

Et puis, on a les tirages avec des nombres plus élevés. Bon, Patrick Toulon faisait le teste avec 50.000 éléments en 15 millisecondes, chez moi, c'était 20 millisecondes, donc comparable (22% du total) et en total "READ+Tirage+Write" = 91 ms. Même ici, ces les méthodes 1&2 sont 2.5 fois plus vite, alors on gagne 12 millisecondes et le total serait 80 ms. C'est une blaque si on veut faire cela ... !

Résumé : Fisher-Yates est encore la référence, je n'ai pas fait une erreur au niveau nano/micro/milli et on a perdu beaucoup de temps avec ce topic !!!

on a pas perdu du temps
j'ai dis seulement que concernant le probabilisme d'uniformité est un mensonge avec FY pas l'algo lui même qui reste une évidence mais du au fait que l'on utilise RND
d'autre part test 100 000 fois on se rend compte aussi que rnd a tendance a éliminer la borne haute
et que ajouter 0.9999999 a la borne permet une tirage plus fréquent
mais ça vous l'avez pas écouté vous vous êtes braqués sur la théorie que je défend

et oui même si le benchmark n'est par parfait il a le mérite de nous donner une idée étape par étape d'ans un algo des chose a améliorer et encore ce n'est pas la meilleure version il y en a eu une autre plus puissante qui donne des migraines mais très efficace et plus près de la vérité

Je ne peux exprimer, sans diffamer, mon incrédulité face à votre déni obstiné des failles flagrantes de votre raisonnement. Regardez les résultats dans l'image ci-dessous. À droite, l'exercice FY avec 100 000 tirages, parfaitement répartis ; à gauche, les méthodes 1 et 2 : quel désordre !

Alors, prouvez vos dires avec des données concrètes, ou cessez cette plaisanterie.🤢🤮

Alors, prouvez vos dires avec des données concrètes, ou cessez cette plaisanterie

Cliquez pour agrandir...

je me répète une dernière fois ; dégonfle le melon
j'ai ouvert ce topic , si la tournure ne te plait pas tu peux toujours zapper
j'ai monté suffisamment de nombreux tests je crois
pour moi sans légende ni explication tes tableaux ne veulent rien dire et tout à la fois
après c'est pas grave j'ai voulu montrer deux constats en faisant abstraction d'une méthode ou d'une autre
et grâce a tes interventions ç'est passé sous silence

je demande la cloture de ce topic