Conceptualisation d'une mesure de performance

Version imprimable

06/10/2011, 13h56
minnesota

Conceptualisation d'une mesure de performance

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.
06/10/2011, 15h32
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 :
https://chart.googleapis.com/chart?c...[|1;1000|] pour la distribution uniforme ;
https://chart.googleapis.com/chart?cht=tx&chl=(v_n) pour la distribution d'une de tes applis (https://chart.googleapis.com/chart?cht=tx&chl=v_n étant le n-ième nombre retourné par celle-ci) ;

https://chart.googleapis.com/chart?c...8u_n-v_n\%29^k
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,
06/10/2011, 15h49
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.
06/10/2011, 21h27
minnesota

Salut,

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

Citation:

Envoyé par prgasp77

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) ?

Citation:

Envoyé par Nebulix

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" :aie: 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.
07/10/2011, 01h17
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 https://chart.googleapis.com/chart?c...=\+\frac{\pi}4. 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 https://chart.googleapis.com/chart?c...hl=\frac{\pi}4 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 ;)
08/10/2011, 09h33
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.
09/10/2011, 15h30
minnesota

Salut,

Citation:

Envoyé par prgasp77

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 :oops:
09/10/2011, 15h55
prgasp77

Citation:

Envoyé par minnesota

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

Mouarf !
Mais il ne devrait pas y avoir de division par zéro. Le rapport à calculer est celui entre le nombre de points à l'intérieur et le nombre de points totaux. Par contre, cent nombres risque d'être un peu faible pour l'interprétation des résultats. Mille par applications me semble plus respectable.
09/10/2011, 22h36
minnesota

:aie:

Ah ben je me suis fié à ce que tu as écrit précédemment, mais effectivement, le rapport des surfaces aurait dû me mettre la puce à l'oreille qu'il y avait une incohérence dans ton message. Bon cela dit, malgré une petite sieste, ça ne va toujours pas mieux. Ah oui, pour les calculs j'utilise l'utilitaire Unix BC que je découvre et les calculs risquent d'être terriblement lents.

Dans tous les cas, je rectifie le tir dès que possible et je te tiens au courant.

Merci tout plein.
10/10/2011, 10h43
prgasp77

Mea culpa :oops:
Mais pourquoi les calculs seraient-ils lents ? Pour 10 000 nombres on a 5 000 points soit 10 000 carrés, 5 000 additions et 5 000 comparaisons. Le tout sur des nombres entiers.

Cdlt,
11/10/2011, 19h19
minnesota

re,
pour savoir si un point est dans le cercle, j'étais arrivé à cette formule : (x²+y²)-65534²<0

Comme c'est un script, pour chaque calcul et itération, je fais appel à bc

Code:

echo ^(^(%x%^^2+%y%^^2^)^-65534^^2 ^^^^^^^< 0^) ^| %bc%

du coup ça prend bien une demi-seconde par évaluation.

Écris un petit programme en C/caml/lisp (pas java) ... qui retourne 0 si c'est dans le cercle et 1 sinon ;)

Edit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
let radius = 65534/2 

let is_in_circle (x,y) =
  let square x = (float x) **  2. in
  let squared_radius = square radius
  and squared_x = square (x-radius)
  and squared_y = square (y-radius) in
  let squared_hypot = squared_x +. squared_y in
  squared_hypot < squared_radius

let get_coordinates () =
  try (int_of_string Sys.argv.(1) , int_of_string Sys.argv.(2)) with
    _ -> exit 2

let main () =
  let point = get_coordinates () in
   exit (
      if is_in_circle point
      then 0
      else 1
   )

let _ =
  main ()

à compiler avec ocamlopt -o tp tp.ml et utiliser ./tp 564 846 && echo IN || echo OUT

12/10/2011, 23h07
minnesota

Merci pour le retour.

Aussi, pour les tests, j'étais parti à la base sur une centaine de nombres, le délai d'exécution n'était pas gênant. Mais sur dix mille ça craints. En fait, c'est l'antivirus qui ralentit tout, car à chaque itération et redirection, j'ai une nouvelle instance de l'interprétateur et de l'exécutable, et il filtre tout, d'où la latence. Donc oui, tu as raison, je vais faire un petit programme dédié, une fois autorisé par l'antivirus et en mémoire, ça ira plus vite. Par contre, je ne connais pas caml et je n'ai rien pour compiler dans cet environnement, alors j'espère que tu n'y verras pas d'inconvénients que je me contente du c++, j'y lirai aussi directement la table. Par contre, ça va être chaud, le dernier code que j'ai écrit doit tellement dater que je m'en souviens même plus :?

Bon ben voilà le résultat, par contre, je ne sais pas l'interpréter.

Citation:

>call scoremc newtable.txt
7451/10694
score mc newtable.txt = 0.0886523

>call scoremc a1.txt
683/982
score mc a1.txt = 0.0898788

>call scoremc a2.txt
681/992
score mc a2.txt = 0.0989062

>call scoremc a3.txt
671/985
score mc a3.txt = 0.10418

>pause
Appuyez sur une touche pour continuer...

le code source :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <iomanip> #include <fstream> #include <sstream> #include <string> #include <cmath> using namespace std; int main (int argc, char *argv[]){ string str; ifstream infile; unsigned long int x=0, y=0, in=0, tt=0, m=65534; bool flag=true; infile.open (argv[1]); while(!infile.eof()) { getline(infile,str); istringstream iss(str); if (flag){ iss >> x; } else { iss >> y; } flag^=true; if (sqrt(pow(x-m/2.0,2.0)+pow(y-m/2.0,2.0)) <= m/2.0) ++in; ++tt; cout<<in<<"/"<<tt<<"\r"<<flush; } cout<<endl; cout<<"score mc "<<argv[1]<<" = "<<abs(((in*1.0)/tt)-((4*atan(1))/4.0))<<endl; infile.close(); return 0; }

12/10/2011, 23h31
prgasp77

C++ c'est le MAL ! Non gros délire ... oui, idéalement, ton programme à intérêt à lire directement dans la table. Tiens moi au courant ton problème est particulièrement intéressant ;).
12/10/2011, 23h32
minnesota

Ben c'est fait :mouarf:
13/10/2011, 01h24
prgasp77

Messages croisés :)

Citation:

Envoyé par minnesota

>call scoremc newtable.txt
7451/10694
score mc newtable.txt = 0.0886523

Donc ça, c'est notre MC de référence. Il peut t'être utile pour comparer l'ensemble de tes applis par rapport à un autre générateur.

Citation:

Envoyé par minnesota

>call scoremc a1.txt
683/982
score mc a1.txt = 0.0898788

Si on s'est bien compris, il s'agit là du MC pour ta table moins les données générées par l'appli a1. Ce nombre est le plus proche du MC de référence, on en déduit donc que a1 n'apporte pas grand chose.

Citation:

Envoyé par minnesota

>call scoremc a3.txt
671/985
score mc a3.txt = 0.10418

Au contraire ici, le score est très différent du MC de référence. L'appli a3 apporte donc beaucoup à l'efficacité de ton générateur global (car si on l'enlève, rien ne va plus).
13/10/2011, 17h10
minnesota

Citation:

Envoyé par prgasp77

Si on s'est bien compris, il s'agit là du MC pour ta table moins les données générées par l'appli a1.

Ah ben non :mouarf:

sinon après la modification, voilà ce que j'obtiens :aie:

Citation:

a1.txt+a2.txt+a3.txt+table.txt -> suppression des doublons (newtable.txt)
1 fichier(s) copié(s).
score full newtable
7451/10694
score mc newtable.txt = 0.0886523

a2.txt+a3.txt+table.txt -> suppression des doublons (newtable.txt)
1 fichier(s) copié(s).
score full newtable-a1
6986/10013
score mc newtable.txt = 0.0877052

a1.txt+a3.txt+table.txt -> suppression des doublons (newtable.txt)
1 fichier(s) copié(s).
score full newtable-a2
6979/10006
score mc newtable.txt = 0.0879167

a1.txt+a2.txt+table.txt -> suppression des doublons (newtable.txt)
1 fichier(s) copié(s).
score full newtable-a3
7003/10036
score mc newtable.txt = 0.0876102

Appuyez sur une touche pour continuer...
17/10/2011, 14h33
minnesota

Je vais continuer en ce sens. Merci beaucoup. Je pense que c'est résolu ;)

Juste une question au passage, pour info personnelle, est-ce qu'il y a une méthode similaire pour une table qui serait un dictionnaire.
17/10/2011, 16h00
prgasp77

Comment ça un dictionnaire ?
17/10/2011, 20h42
minnesota

Ici on était partie que sur des nombres aléatoires, mais est-ce qu'il y a un équivalent du MC pour une table qui contiendrait des lignes du genre "e3ab1m62c" ou de vrais mots de la vie quotidienne (dico).
18/10/2011, 01h09
prgasp77

Rien de préfait à ma connaissance. Mais on doit pouvoir adapter. Une lettre étant un symbole, elle peut être quantifiée ;)
18/10/2011, 16h58
minnesota

OK ça marche. Merci pour tout. ;)