Comment mesure t-on l'efficacité d'un algorithme ?
Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 43

Comment mesure t-on l'efficacité d'un algorithme ?



  1. #1
    anthony_unac

    Comment mesure t-on l'efficacité d'un algorithme ?


    ------

    Bonjour,

    Je viens de créer un algorithme permettant d'effectuer le produit de deux entiers naturels.
    Comment puis je mesurer son efficacité par rapport à tous ceux (et il y en a des masses) qui existent déjà ?

    Je pensais partir sur le principe de compter le nombre d'opérations élémentaires qu'il faille faire pour aboutir au résultat.
    Mettons deux entiers et , on aboutit au résultat en additionnant chiffres et en multipliant chiffres.
    Les valeurs de et permettant alors de quantifier l'efficacité de l'algorithme.

    Cordialement
    Anthony

    -----

  2. #2
    erik

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Salut,

    Il faut que tu détermines le nombre d'opération d'opérations nécessaire en fonction du nombre de chiffres des deux nombres que tu multiplies.

    Par exemple pour multiplier deux nombres de n et m chiffres (comme on l'apprend à l'école) il faut nXm opérations.
    En général il n'est pas possible de déterminer le nombre exacte d'opérations, suivant le problème envisagé on s'intéresse alors au nombre d'opérations nécessaire dans le pire des cas ou au nombre moyen d'opérations nécessaire.

    Une intro à lire : http://www.enseignement.polytechniqu...w-poly009.html

  3. #3
    invite4ef352d8

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Bonjour !


    en général oui, on s'intéresse au "nombres d'opération élèmentaire" nécessaire. et plus précisement à la facon donc ce nombre croit avec la taille des donnée (en ignorant le plus souvent les constantes multiplicative qui ne sont pas toujours pertinente puisque le temps nécessaire à effectué une opération élémentaire dépend fortement de la machine qu'on utilise


    par exemple, pour la multiplication de deux entier A et B, on va dire que "l'opération elementaire" c'est le fait d'additioner ou de multiplier deux entier (au niveau de l'ordinateur, les nombres A et B seront le plus souvent stocké en binaire, et donc "chiffre" sera en fait un 0 ou un 1 et additioner ou multiplicer des 0 ou des 1 c'est quelque chose d'immediat ^^) l'algoritme "classique" (celui qu'on apprend à l'ecole primaire) demande de l'ordre de n^2 opération (n étant le nombres de chiffre maximal de A et de B). En première approche on se moque assez royalement de savoir si c'est 4n² ou 12n² parceque par rapport à ce qui vient après c'est pas forcement pertinent. il existe une algorithme un peu meilleur utilisant une technique "diviser pour regner" (methode de Karatsuba il me semble) qui donne le résultat en n^(sqrt(3)). enfin, la multiplication par FFT (intéressante seulement si n est assez grand) donne le résultat en n.log(n).

  4. #4
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Pour le cas de la multiplication qu'on apprend à l'école le constat est bien plus lourd car certes le nombre de multiplications est de n*m mais il y a également des additions à faire exemple : 23*47 donne 4 multiplications mais aussi 14 chiffres à additionner soit au final et pour reprendre mes notations. A titre de comparaison mon bricolage donne sur cette exemple et .

  5. A voir en vidéo sur Futura
  6. #5
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    L'algo Karatsuba revient souvent sur le tapis et pourtant, il n'aboutit pas à des valeurs faibles de et par rapport à d'autres algo d’où mon étonnement

  7. #6
    erik

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Si tu veut être compris il faut laisser tomber tes alpha et tes mu.

    L'algo de Karatsuba est en (n étant le nombre de chiffres des deux nombres à multipli),ce qui est une amélioration (sans être exceptionnel) par rapport à l'algo (scolaire) est lui en (même en tenant compte des additions en plus des multiplications on reste en O(n²))

    Si tu ne mesures pas la complexité de ton algo, de la même manière que tout le monde cela va être dur de comparer.

  8. #7
    invite4ef352d8

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Si tu trouve que Karatsuba est moins efficace que ton algoritme c'est parceque tu regarde tes trop petit nombre !
    en pratique, quand on travail sur un processeur classique, additionner ou multiplier deux nombres codé sur 32 bits (donc inférieur à 2^32, ou compris entre 2^31 et -2^31 selon le codage utilisé), et garder le résultat modulo 2^32 et une opération élèmentaire. qui n'occupe qu'une unité de temps de processeur. réfkechir aux nombres de multiplication neccessaire pour multiplicer 37 et 52 n'as aucun sens ! surtout que dans l'ordinateur 37 et 52 sont stocké en binaire donc l'addition de chiffres décimal n'est pas une primitive intéressante.

    donc chercher des meilleur algo de multiplication est interessant quand on aura de très très grand nombres (du genre plusieurs dizaine de chiffres en base 2^16 le plus souvent) l'algo classique - et très probablement aussi le tiens - demande alors environ n^2 opération élémentaire. alors que Karatusbu a un exposant <2 (et la multiplication par FFT encore moins) ce qui veut dire que "pour des nombres assez grand, karatsuba sera meilleur que ton algo". après la question de savoir quand utiliser Karatsuba et quand utiliser un algo plus traditionel est intéressante, mais c'est de l'optimisation déjà assez pointu.

  9. #8
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Bonjour

    Il semblerait que je n utilise pas la bonne façon de décrire l algorithme seulement voila je ne sais pas s il est en O(n) ou O(logn) ou tout autre chose Tout ce dont je puis dire c est qu il est question d exécuter que des additions (et ça apparemment ça va vite) et aucune multiplication. D autre part l algo gagne en efficacité avec la taille des entiers a multiplier (cf multiplier sans connaitre ses tables part. 2/2 ou il est question de multiplier deux entiers de 7 chiffres.

    Cordialement
    Anthony

  10. #9
    Tryss

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Ce que tu nous dis là ne nous avance pas vraiment pour savoir si ton algorithme est intéressant... Il va falloir que tu fasses le calcul de la complexité, ou au moins une estimation.

    Une méthode pour l'estimer pourrait être d'implémenter ton algorithme (avec scilab par exemple, mais ça se fait très bien en C), d'ajouter un compteur d'opération, et de calculer , le nombre d'opérations nécessaires pour multiplier 2 nombres aléatoires de taille n.

    Ensuite tu traces => si ça tend vers a>0, la complexité est probablement en O(n²), si ça diverge, la complexité est probablement moins bonne que O(n²), et si ça tend vers 0, la complexité est probablement meilleure que O(n²).

  11. #10
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Merci pour cette réponse Tryss mais malheureusement je n'ai pas de compilateur en C et en plus je suis une horreur en programmation et pour finir je ne vois pas (même le programme écrit) comment voir ce fameux compteur donnant le nombre d'opérations effectuées.
    En tout cas cette façon de tester un algorithme me plait car elle met vraiment tout le monde à égalité.

    Cordialement
    Anthony

  12. #11
    invite4492c379

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Pas la peine de compilateur, quel est ton algo ?

  13. #12
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Mon algo est donné sous forme de videos intitulées "Multiplier sans connaitre ses tables de multiplication".
    Je ne sais pas si c'est suffisamment clair mais en tout cas ça suffit largement pour s'en sortir lorsqu'on a une feuille et un crayon.
    Je ne sais pas le formaliser en tout cas ni sous forme de code ni sous forme de losanges etc...

  14. #13
    invite4492c379

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    à la base un algo est juste une méthode, donc tu peux l'écrire en français. Certains formalismes existent mais rien de réellement universel.

  15. #14
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Ok alors essayons :

    En partant du fait qu'on veuille multiplier deux entiers et écris en ligne.

    Déterminer la digit la plus grande de l'entier gauche (appelons la ).
    Suivant la valeur de , on va additionner l'entier droit (terme 1) par lui même donnant (terme 2) puis ce résultat par lui même donnant (terme 4) etc donnant (terme 8)

    On recopie sous chaque digit de l'entier gauche en commençant par la digit de gauche le terme (1), (2), (4) ou (8) ou une combinaison de ces termes en posant le chiffre des unités du terme dans l'alignement de la digit de l'entier gauche. Ensuite on passe à la seconde digit de l'entier gauche sous laquelle on recopie le terme (1), (2), (4) ou (8) ou une combinaison de ces termes en posant le chiffre des unités du terme dans l'alignement de la digit de l'entier gauche etc .......

    On exécute l'addition de tous les termes recopiés sous l'entier gauche pour aboutir au résultat


    C'est immonde à lire je sais

  16. #15
    invite4492c379

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Non ça va il y a pire. À première vue il est aussi efficace que la méthode de multiplication type école, plus gourmand en mémoire pour s'affranchir de la multiplication.

  17. #16
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Comment avez vous fait pour :

    1/ Décoder ce foutoir

    2/ Coder ce foutoir

    3/ En déduire finalement que ça vaut pas mieux que l'algo de l'école

  18. #17
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Je reste perplexe tout de meme car sur cet exemple

    On voit bien que la méthode école est beaucoup plus longue avec ses 49 multiplications !
    Dernière modification par anthony_unac ; 18/09/2011 à 16h40.

  19. #18
    Médiat

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Que donne votre algorithme pour multiplier 357953973 par 737537935 ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #19
    erik

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Tu comptes pour 2 110 117 x 2 522 144 49 multiplications, c'est ok, je suis d'accord.

    Mais tu considère que 2 110 117 + 2 110 117 ne compte que pour une addition, là pas d'accords, il faut compter 7 additions pour obtenir la somme.

    En comptant le nombre d'addition que tu fait (digit par digit) tu fait une bonne cinquantaine d'opérations.

    Je plussoie donc photon57, à la louche il faut autant d'opération que pour la multiplication standard. (par contre je doit avouer que je n'ai pas cherché à comprendre l'explication de ton algo)
    Dernière modification par erik ; 18/09/2011 à 17h14.

  21. #20
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Citation Envoyé par erik Voir le message
    Tu comptes pour 2 110 117 x 2 522 144 49 multiplications, c'est ok, je suis d'accord.

    Mais tu considère que 2 110 117 + 2 110 117 ne compte que pour une addition, là pas d'accords, il faut compter 7 additions pour obtenir la somme.

    En comptant le nombre d'addition que tu fait (digit par digit) tu fait une bonne cinquantaine d'opérations.

    Je plussoie donc photon57, à la louche il faut autant d'opération que pour la multiplication standard. (par contre je doit avouer que je n'ai pas cherché à comprendre l'explication de ton algo)
    Vous noterez tout de même que l'algo école aussi nécessite de faire beaucoup d'additions digit par digit, car il ne suffit pas de se taper les 49 multiplications

  22. #21
    invite4492c379

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Citation Envoyé par anthony_unac Voir le message
    Comment avez vous fait pour :

    1/ Décoder ce foutoir

    2/ Coder ce foutoir

    3/ En déduire finalement que ça vaut pas mieux que l'algo de l'école
    Je ne l'ai pas codé, ce n'est pas nécessaire. Je l'affirme car a priori, pour ce que j'ai compris, tu remplaces les tables de multiplications des chiffres par le calcul d'une table de multiplication du deuxième nombre.

    Ton algo est bien celui-ci :
    Code:
    UnacMult( N : entier de n chiffres, M : entier de m chiffres) : entier
    début
        kFoisM[0]=0
        pour chaque entier k de 1 à 9
            kFoisM[k] = M + kFoisM[k-1]
    
        res = 0
        pour c de 0 à n-1
            res = res + Decalage(kFoisM[N[c]],c)
    fin.
    où Decalage( E : entier, d : entier) est une fonction qui renvoie E x 10^d

    Non ?

  23. #22
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Citation Envoyé par Médiat Voir le message
    Que donne votre algorithme pour multiplier 357953973 par 737537935 ?
    A peu près ceci :
    Pièce jointe 158709
    Images attachées Images attachées  
    Dernière modification par anthony_unac ; 18/09/2011 à 18h35.

  24. #23
    Médiat

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Ma question portait sur l'efficacité de votre algorithme, pas son application (en tenant compte de la remarque d'Erik au message 19, en ne comptant une addition chaque fois que vous additionnez deux digits).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #24
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Ma question a l'origine portait également sur l'efficacité de l'algo (chose que je suis incapable de mesurer).
    Concernant l 'addition digit par digit je ne sais pas combien il y en a ici beaucoup c'est vrai mais il y en a beaucoup également c'est vrai aussi avec la méthode école qui nécessite au préalable de se taper multiplications.

  26. #25
    invite4492c379

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Citation Envoyé par anthony_unac Voir le message
    Ma question a l'origine portait également sur l'efficacité de l'algo (chose que je suis incapable de mesurer).
    Concernant l 'addition digit par digit je ne sais pas combien il y en a ici beaucoup c'est vrai mais il y en a beaucoup également c'est vrai aussi avec la méthode école qui nécessite au préalable de se taper multiplications.
    Pour mesurer l'efficacité d'un algo il faut déjà écrire cet algo, ma proposition est-elle correcte ?

  27. #26
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Citation Envoyé par photon57 Voir le message
    Je ne l'ai pas codé, ce n'est pas nécessaire. Je l'affirme car a priori, pour ce que j'ai compris, tu remplaces les tables de multiplications des chiffres par le calcul d'une table de multiplication du deuxième nombre.

    Ton algo est bien celui-ci

    Non ?
    Je n'en ai aucune idée car je suis incompétent en informatique.
    Désolé mais c'est vrai

  28. #27
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Bonjour,

    En reprenant l'exemple proposé par Médiat :
    J'aboutis au résultat suivant (sans compter les digits égal à zéro):
    ************************
    Avec mon algo: 194 additions de digits et 0 multiplication soit 194 opérations élémentaires
    Avec l'algo école : 162 additions de digits et 81 multiplications soit 243 opérations élémentaires

    Conclusion:
    **********
    L'algo école est moins performant et cela d'autant plus que Médiat a choisi un exemple très défavorable (le pire cas en fait) pour mon algo au sens ou les deux entiers à multiplier ne comportaient aucune puissance de deux.
    Dernière modification par anthony_unac ; 19/09/2011 à 09h44.

  29. #28
    Médiat

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    Bonjour,

    Citation Envoyé par anthony_unac Voir le message
    Avec mon algo: 194 additions de digits et 0 multiplication soit 194 opérations élémentaires
    Avec l'algo école : 162 additions de digits et 81 multiplications soit 243 opérations élémentaires
    Quand, dans votre algorithme, vous utilisez plusieurs fois le calcul de 2n, 4n ou 8n, vous ne comptez qu'une fois ces calculs, en faisant pareil dans l'algorithme école, vous obtenez 36 multiplications et non 81, soit un total (je n'ai pas vérifié le nombres d'additions) de 198 comparé à 194, la différence n'est, de toute façon, pas significative, et s'inverserait sans doute avec d'autres exemples.
    Dernière modification par Médiat ; 19/09/2011 à 10h54.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  30. #29
    invite4492c379

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    pfff 5 minutes c'est court ...

    Bref,

    Citation Envoyé par anthony_unac Voir le message
    Bonjour,<br>
    <br>
    En reprenant l'exemple proposé par Médiat : <br>
    J'aboutis au résultat suivant (sans compter les digits égal à zéro):<br>
    ************************<br>
    Avec mon algo: 194 additions de digits et 0 multiplication soit 194 opérations élémentaires<br>
    Avec l'algo école : 162 additions de digits et 81 multiplications soit 243 opérations élémentaires<br>
    <br>
    Conclusion:<br>
    **********<br>
    L'algo école est moins performant et cela d'autant plus que Médiat a choisi un exemple très défavorable (le pire cas en fait) pour mon algo au sens ou les deux entiers à multiplier ne comportaient aucune puissance de deux.
    <br>
    <br>
    Je te fais une petite réponse rapide. Oui tu as raison, ton algo est plus performant sur les exemples qui vont bien selon ta méthode de définition de ce qu'est un opération élémentaire.<br>
    <br>
    Quelques remarques cependant:<br><br>La complexité algorithmique d'un algorithme est définie pour<br><br>le comportement de l'algorithme en terme de temps d'exécution par rapport à la taille des données en entrée, et aussi par rapport à la place requise pour le faire tourner.<br><br>Une notation pour mesurer ces comportements est utilisée : la notation Grand O. Celle-ci désigne quelquechose de simple, le comportement de l'algorithme dans le pire des cas. Dire que l'algo <i>recherche_binaire</i> est en O(lg n) signifie que même dans le pire des cas doubler le nombre d'éléments dans un table &nbsp;ne doublera pas le temps d'éxécution au contraire de l'algorithme naïf.<br><br>Sans rentrer dans des calculs complexes, je t'affirme que la complexité en espace de ton algo est plus grand que l'algo école car à chaque opération tu dois recalcler une table d'addition spécifique à chaque donnée en entrée.<br><br><br><br><ul></ul>

  31. #30
    anthony_unac

    Re : Comment mesure t-on l'efficacité d'un algorithme ?

    J en doute fort vu que vous avez choisi le cas le plus défavorable et que même dans ce cas je bats l algo école

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. améliorer l'efficacité d'un insert
    Par neudorf dans le forum Habitat bioclimatique, isolation et chauffage
    Réponses: 2
    Dernier message: 17/06/2012, 23h23
  2. augmanter l'efficacité d'un emetteur ultrasonique
    Par invite1cd80571 dans le forum Électronique
    Réponses: 5
    Dernier message: 05/04/2010, 06h44
  3. Mesurer l'efficacité d'un cryptosystème
    Par invite91e2ca1e dans le forum Logiciel - Software - Open Source
    Réponses: 5
    Dernier message: 04/03/2006, 20h25
  4. comment avoir la mesure principale d'un angle ?
    Par invite13d2b736 dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 19/01/2005, 13h35