Retourner aux forums || Retourner au forum
Programmation.c++ : Calculer le taux de modification
Posté par phoenix (Jabber id, page perso, ) le 09 février 2010J'ai deux versions de mon logiciel et je cherche à obtenir le taux de similitude entre ces deux versions.
Cette information est là plus à titre d'amusement. Cela fait plus d'un an que je modifie le logiciel (par rapport à la dernière version sortie) et j'ai l'impression d'avoir réécris quasiment l'intégralité de l'application et j'aurais voulu vérifier ce point par des chiffres.
Apparemment il existe la distance de Levenshtein : http://fr.wikipedia.org/wiki/Distance_de_Levenshtein pour comparer deux chaines de caractères.
Si j'ai bien compris :
(le nombre de caractère - la distance) / le nombre de caractère
devrait donner le taux de similitude.
Mais ici, mon but est de comparer deux dossier (où les fichiers on pu être renommé, les dossiers on pu être renommé, ...) et un renommage de fichier ne constitue pas une réécriture complète du fichier.
Bref, connaissez-vous un logiciel qui me permettrait d'obtenir le taux de similitude (ou de différence) entre deux dossier (ou entre deux version d'un logiciel). Si cela peut aider le logiciel est géré sur SubVersion.
Comme cela je pourrais sortir une annonce du style, voici une nouvelle version qui est si tardif car 95% du logiciel a été réécrite (en sachant derrière si c'est vrai ou uniquement un impression).
Merci d'avance
> Lire le message (15 commentaires, moyenne: 1,9).
diif
un diff recursive te dira ce que a été changé
ensuite tu comptes les changements dans le diff
le nombre de + (ajout)
le nombre de - (retrait)
divisé par le total de ligne de code
-
[^]Re: diif
Posté par phoenix (Jabber id, page perso, ) le 10/02/2010 à 11:28. (lien). Évalué à 1.Le problème de cette méthode c'est qu'elle ne prend pas en compte le changement de nom d'un dossier (Au pire tu considère que tous les fichiers on été modifié alors que tu as juste renommé le dossier).
-
[^]Re: diif
Posté par NeoX () le 10/02/2010 à 11:45. (lien). Évalué à 1.et puisque tu utilises SVN
tu as fait un man svn ?
je ne crois pas, car sinon tu aurais vu une commande qui t'interesse...
svn diff
par exemple :
svn diff -r 3000:3500
qui t'indiquerait les changements entre le commit 3000 et 3500
de la tu dois pouvoir compter les changements et faire une division par rapport à la taille totale du projet.
plus d'infgos dans le SVN Book
http://svnbook.red-bean.com/en/1.5/svn-book.html
et plus particulierement
http://svnbook.red-bean.com/en/1.5/svn-book.html#svn.ref.svn(...)-
[^]Re: diif
Posté par Fred () le 10/02/2010 à 14:34. (lien). Évalué à 4.Non : je viens de vérifier, si un fichier a été renommé dans la révision 106, alors avec svn diff -r 105:107 je vois un fichier avec l'ancien nom supprimé, et un fichier avec le nouveau nom ajouté. Avec --no-diff-deleted, je vois uniquement un ajout de fichier (on va dire que ça divise par deux l'erreur commise, mais si il y a eu de vraies suppressions à prendre en compte, ça va les zapper :-/).
-
[^]Re: diif
Posté par phoenix (Jabber id, page perso, ) le 10/02/2010 à 16:35. (lien). Évalué à 1.J'ai le même résultat sur les fichiers renommé, ou même les dossiers renommé.
-
-
-
Utilise gzip, luke !
Cet article, que j'avais lu dans un numéro de Pour La Science de il y a longtemps :
http://interstices.info/jcms/c_21828/classer-musiques-langue(...)
t'explique l'utilisation d'un compresseur pour détecter plus ou moins automatiquement les séquences similaires. Regarde plus précisément le premier paragraphe "Compression de données" après l'intro.
Pour résumer : tu as un répertoire A contenant la version 1 et B contenant la version 2.
soit la fonction c(Rep) = len(gzip(tar(Rep) qui te donne la longueur du fichier Rep.tar.gz (ou bzip2, si tu préfères).
alors on définit la distance de similitude entre A et B :
d(A, B) = 1 – {c(A) + c(B) – c(AB)} / min{c(A),c(B)}
elle vaut 0 quand A = B et 1 quand A est complètement différent de B.
J'avais déjà testé cette méthode fut un temps et elle m'avait donné de bons résultats...
Mes deux euros...
-
[^]Re: Utilise gzip, luke !
Posté par aedrin () le 10/02/2010 à 12:56. (lien). Évalué à 2.Pour c(AB), il faut bien sûr comprendre la longueur de la compression des deux répertoires concaténés, et donc dans notre cas :
c(AB) = len(gzip(cat{tar(A),tar(B)}))
rapide efficace et pas cher-
[^]Re: Utilise gzip, luke !
Posté par phoenix (Jabber id, page perso, ) le 10/02/2010 à 15:39. (lien). Évalué à 1.Je doute de l'efficacité :'(
Je viens de faire :
C(A)
C(B)
C(AB)
et
C(AA)
TAR(AA) correspond bien à environ TAR(A) + TAR(A)
TAR(AB) correspond bien à environ TAR(A) + TAR(B)
Une fois compressé, C(AB) >>> C(A) et C(AA) >>> C(A)
En faite le calcul me donne d = 0,97 (soit proche de 1) pour C(AB) et plus pour C(AA).
Le plus étrange c'est ceci (bzip2 ou gzip ne sont peut-être pas assez efficace, comme on en parle ci-dessous) :
tar -c trunk/* > trunk.tar
tar -c v0.8.1/* > v0.8.1.tar
tar -c trunk/* v0.8.1/* > common.tar
tar -c trunk/* trunk/* > common2.tar
puis je bzip2 chaque fichier :
1043899 fév 10 15:31 common2.tar.bz2
975668 fév 10 15:26 common.tar.bz2
521470 fév 10 15:26 trunk.tar.bz2
465741 fév 10 15:25 v0.8.1.tar.bz2
Le fichier common2 est plus gros que common pourtant tout les fichiers sont en double ... alors que common contient A et B
PS : Le TAR d'un dossier (comme par exemple trunk) non compressé fait 4,3 Mo-
[^]Re: Utilise gzip, luke !
Posté par phoenix (Jabber id, page perso, ) le 10/02/2010 à 15:58. (lien). Évalué à 2.Par contre l'utilisation de p7zip change la donne :
468800 fév 10 15:52 common2.tar.7z
547562 fév 10 15:53 common.tar.7z
468164 fév 10 15:53 trunk.tar.7z
413518 fév 10 15:53 v0.8.1.tar.7z
Soit donc
d(A,A) = 0.001
d(A,B) = 0.192
Si je comprend bien mes programmes on 19% de différence (ou autrement, j'ai réécris 19% de mon application)-
[^]Re: Utilise gzip, luke !
Posté par phoenix (Jabber id, page perso, ) le 10/02/2010 à 17:30. (lien). Évalué à 1.A priori, j'ai une asymptote à .7430750703
Quand je prend deux programme complétement différent mais tous les deux écris en C++ et Qt, c'est le nombre que je trouve, et c'est le plus grand nombre que j'ai réussi à obtenir.
Cela doit venir de la redondance des mots clé du language et de la spécificité à Qt (utilisation des QHash, ...)
Est-ce que cela veut dire que je peux faire une règle de trois et ajuster mon pourcentage de 19% à 26% ? (de toute facon c'est approximatif).
A moins que la courbe n'est vraiment pas linéaire (même pas entre 0.001 et 0.7430) et donc je ne peux pas vraiment estimer mon pourcentage de différence mais juste une distance (qui est moins parlant).-
[^]Re: Utilise gzip, luke !
Posté par aedrin () le 10/02/2010 à 18:45. (lien). Évalué à 1.Je me suis trompé dans la formule : il faut diviser par max{c(A),c(B)} et non pas par le min...
donc dans ton cas ça donne d(A,B) = 0.286
recommence tes autres tests pour voir si tu as une nouvelle "asymptote" pour deux programmes c++/qt quelconques...
sinon, effectivement, d(A,B) vaut 1 pour deux flux A et B totalement décorrélés.
Là, A et B ont une prédominance de [a-zA-Z], de blancs, tabulation, fins de ligne et signes de ponctuation et autres opérateurs. Et en plus, on retrouve forcément les mots-clés du c++ et les définitions de qt, de la STL, et de la libc.
Forcément, ils ont une corrélation intrinsèque.
Après, te dire si la courbe est linéaire, je n'en sais fouchtre rien... tout ça ne reste qu'une estimation des distances dans une certaine unité (restons bien vague). Au moins ça te donne un outil, à toi de voir si ça t'es utile ou pas.-
[^]Re: Utilise gzip, luke !
Posté par phoenix (Jabber id, page perso, ) le 10/02/2010 à 21:29. (lien). Évalué à 1.C'est un peu mieux : L'asymptote est alors aux alentoures de 0.9894065342 ce qui est déjà plus proche de 1.
-
-
-
-
-
-
[^]Re: Utilise gzip, luke !
Posté par Fred () le 10/02/2010 à 14:40. (lien). Évalué à 3.Si les séquences communes (typiquement, une fonction déplacée d'un fichier à l'autre) sont "loin" les unes des autres (>32ko, d'après [1]), elles ne seront pas détectées, si ? Et donc, cela veut dire que si le .tar des sources fait >16ko, on risque de passer à côté de recoupements... Or, 16ko de sources, ce n'est pas grand'chose...
Ceci dit, c'est éblouissant de simplicité et d'élégance :-)
[1] http://www.gzip.org/algorithm.txt-
[^]Re: Utilise gzip, luke !
Posté par aedrin () le 10/02/2010 à 15:21. (lien). Évalué à 1.ben dans ce cas, utilise bzip2, qui utilise des blocs d'un maximum de 900 ko. C'est pas encore la taille des sources du noyau mais on s'en approche.
http://en.wikipedia.org/wiki/Bzip2
sinon, effectivement l'intérêt de la méthode c'est qu'elle fait deux lignes de code et qu'elle approxime assez bien une véritable distance pour peu que l'algorithme de compression soit efficace sur les objets traités (pour un répertoire de sources, va faire ton marché sur http://mattmahoney.net/dc/text.html )
-
git
Je viens de faire un commit sous git, et l'outil m'a donné la ligne suivante :
2 files changed, 380 insertions(+), 419 deletions(-)
rewrite file.c (62%)
J'ai repensé à ce thread. Je ne sais pas d'où git sors ce chiffre, mais c'est peut etre interressant de creuser dans cette direction.
En tout cas, une solution serait d'utiliser git :)
Revenir en haut de page || Retourner aux forums || Retourner au forum
Cette page a été générée par Templeet en 0.08s (dont 0.0056 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Faire un don !
Cette discussion est archivée, il n'est plus possible de laisser des commentaires.
Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.