Discussion :

[minnesota]

Salut tout le monde.

J'aurais besoin de votre aide, car je bute sur un problème et je ne sais pas comment l'aborder.
Dans les faits, j'ai 3 algorithmes codés chacun dans une "appli" console, ou plutôt j'ai les applis, pour l'instant 3 mais il y en 7 autres de prévus. Les algorithmes peuvent être de natures différentes ou associés à des facteurs de correction, et ils ne font rien d'autre que donner des nombres aléatoires, enfin pseudo aléatoires, ou précalculer, compris entre 0 et 65534 tout au plus. À côté de cela, j'ai une table que je remplis avec les nombres donnés par les applis, 1000 par appli. Mon but est de mesurer la performance de chaque appli, sur la rapidité, ça c'est facile à mesurer, mais aussi sur sa capacité à ne jamais donner un nombre déjà présent dans la table ou par une autre appli au cours d'une même session. Je procède à 9 sessions au total, et à la fin je choisis l'appli que j'estime être la plus efficace. Mais voilà, j'arrive pas à conceptualiser tout ça et c'est là que j'ai besoin de vous.

Merci.

[prgasp77]

Bonjour,
au final ton problème n'est-il pas de comparer (quantitativement) deux distributions discrètes : celle obtenue par l'exécution d'une appli et la distribution uniforme (chaque entier tombant 2^10-24 fois sur 2^16-2) ?

Si tel est effectivement le cas, malgré la granularité de ton problème (un nombre ne peut pas tomber 2^(-6) fois), je pense que mesurer l'efficacité de tes applis par une norme de cette différence peut être efficace.

Concrètement, je verrais :
pour la distribution uniforme ;
pour la distribution d'une de tes applis ( étant le n-ième nombre retourné par celle-ci) ;


est alors la norme-k de la différence (k pouvant être infini, la somme se transformant en sup, tout ça tout ça...). Et suivant le k, ça peut être une bonne mesure ... je pense.

C'est assez rapide à coder, ça peut se faire sous excel, dis moi ce que tu en penses/obtient.

Cordialement,

[Nebulix]

Je ne comprends pas très bien tes critères et je crains que toi non plus. Par exemple, un tirage parfaitement aléatoire peut très bien donner deux fois le même nombre.
Si tu arrives à les préciser pour que je comprenne, tu te seras bien rendu service.

[minnesota]

Salut,

Déjà, merci beaucoup à vous deux d'avoir répondu à mon appel.

au final ton problème n'est-il pas de comparer (quantitativement) deux distributions discrètes : celle obtenue par l'exécution d'une appli et la distribution uniforme (chaque entier tombant 2^10-24 fois sur 2^16-2) ?

Par exemple, un tirage parfaitement aléatoire peut très bien donner deux fois le même nombre.
Si tu arrives à les préciser pour que je comprenne, tu te seras bien rendu service.

Concrètement, rien ne garantit que la distribution soit uniforme ou que les tirages soient parfaitement aléatoires. Par exemple, j'ai une appli qui ne donne jamais le même nombre dans une même session. J'en ai même une autre qui "triche" et qui regarde le contenu de la table avant de donner ses résultats, etc. Le calcul de la vitesse permet de pondérer la performance des applications qui semblent à première vue efficaces.

Pour cette première partie et à chaque session, je me suis attribué comme objectif de donner une note (en % ?) à chaque appli en fonction "de son aptitude" à donner des nombres qui ne figurent ni dans la table ni dans les 2000 fourni par les 2 autres applis. Et c'est là que je bloque. Effectivement, il semble possible de faire des comparaisons deux à deux, mais j'ai peur que ça devienne une usine à gaz une fois que le nombre d'applis porté à 10, sans oublier la table.

Pour info, la deuxième partie que j'envisage, c'est de donner un temps limite aux applis pour fournir leurs nombres, et pour la notation, je pense utiliser la même approche que précédemment.

Encore merci.

[prgasp77]

Salut,
j'ai relu ton premier post, et il y a des subtilités qui m'avaient échappé au premier abord. Mes excuses.

J'ai peut être une idée, le test de « Monté Carlo » modifié par mes soins. Considérons la table comme une simple suite de nombres (triés par ordre chronologique de génération, si on lance toutes les applis en même temps). On va faire un calcul de performance pour chaque application et une dernière pour fournir la référence.

On va donc appliquer l'opérateur MC à la table, entière pour la référence, et diminuée des nombres provenant de l'appli A pour le calcul de la performance de A.

Le principe de l'opérateur MC est de considérer les nombres deux à deux (dans l'ordre établi − cela n'est pas gênant car idéalement deux nombres consécutifs sont issus de tirages indépendants) comme des points dans le carré centré en (65534/2 ; 65534/2). Pour chaque point, on teste s'ils sont dans ou hors du cercle inscrit audit carré. On compte les points en question. Finalement, la probabilité qu'un point soit dans le cercle est le rapport des surfaces, soit . Une fois la table modifiée parcourue, on calcule le rapport entre le nombre de points dans le cercle et le nombre de points en dehors. La différence de cette valeur avec est le score que fournit MC. Pour calculer quel est l'apport de notre appli A à la table des données, on soustrait à ce score celui obtenu pour la table complète.


Qu'en penses-tu ?


Nota : pour la différence avec pi/4, utiliser une valeur absolue

[minnesota]

Merci beaucoup pour ta réponse.

Avant toute chose, sachez que je n'ai aucune notion des "patterns" algorithmique, et pour ainsi dire je ne connais de Monte-Carlo que la "ville" du même nom, et encore j'y suis jamais allé.

Cela dit, je pense avoir compris ce que tu dis prgasp77, que je vais tenter de mettre en application ce week-end et je te dirais ce qu'il en est. Je vais aussi faire une table réduite et limiter les nombres possibles à 100 par exemple pour que ça soit plus parlant et facile à appréhender.

Encore merci.

[minnesota]

Salut,

Pour calculer quel est l'apport de notre appli A à la table des données, on soustrait à ce score celui obtenu pour la table complète

J'ai rencontré un problème.
En effet, j'ai une appli dont tous les points se retrouvent dans le cercle, ce qui pose un problème de division par 0 lors du calcul du rapport. En même temps, je suis bien enrhumé, du coup, pas facile d'y réfléchir