IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

Evaluer la complexité d'un programme


Sujet :

C

  1. #1
    Membre averti
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2011
    Messages
    754
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Août 2011
    Messages : 754
    Points : 376
    Points
    376
    Par défaut Evaluer la complexité d'un programme
    Bonjour,

    j'aimerais savoir s'il existe des méthodes permettant de déterminer la complexité d'un algorithme.


    En gros, j'ai un programme A et un programme B; les deux effectuent le même traitement, mais de façon différente.

    Dans un premier temps, j'ai effectué une comparaison sur la durée d'exécution; et elle est similaire.

    Maintenant ce que j'aimerais voir c'est regarder de plus près la complexité "mémoire" de ces algos.

    Autrement dit, combien d'appels mémoire sont effectué.

    Je pourrais obtenir ces chiffres en ajoutant des "compteurs" dans mes fonctions, mais ce serait assez fastidieux et pas vraiment très pratique ni propre; du coup je me demande s'il n'existe pas des fonctions déjà implémenté réalisant ce type d'opération.


    Merci à vous !

  2. #2
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    Janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : Janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    Bonjour,

    tu peux le faire à la main en évaluant la complexité tant spatiale qu'en temps des algos que tu utilises. Ensuite si tu n'es pas à l'aise avec ça il y a des outils.
    Dans le monde unix (linux, mac, …) il y a des outils comme gperf pour étudier en détails les temps passé dans chaque partie de ton programme, valgrind propose massif pour le profilage mémoire … bref google t'en dira bien plus.

  3. #3
    Membre averti
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2011
    Messages
    754
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Août 2011
    Messages : 754
    Points : 376
    Points
    376
    Par défaut
    Je sais étudier la complexité d'une fonction , d'un algo, mais bon faire ça sur une vingtaine de sous fonction, comme j'ai dis à la main c'est très vite fastidieux.

    J'étais plus intéressé par des méthodes en C, je m'imagine bien qu'il existe des outils traitant ce genre de problème, mais là je voudrais arriver à faire un truc pas trop détaillé qui me donne simplement à la fin le nombre d'appel à une case mémoire que j'ai fais.

    En gros si mon programme c'est

    int nb= 3 + 2;

    A la fin je veux détecter qu'il y a eu 2 opérations. Une affectation et une addition.

    Si j'ai

    int a=3;
    int b=2;
    int nb = a+b;

    Je détecte 6 opérations dont 3 affectation 1 addition et 2 accès mémoires.

    Etc etc...j'aimerais arriver à montrer ce genre de chose directement avec une process dans mon main.

  4. #4
    Modérateur
    Avatar de gangsoleil
    Homme Profil pro
    Manager / Cyber Sécurité
    Inscrit en
    Mai 2004
    Messages
    10 148
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Manager / Cyber Sécurité

    Informations forums :
    Inscription : Mai 2004
    Messages : 10 148
    Points : 28 113
    Points
    28 113
    Par défaut
    Bonjour,

    Est-ce une question théorique, ou réelle ?

    Si c'est réel, je pense que tu ne prends pas le problème par le bon bout : affectation et additions coûtent beaucoup moins qu'une multiplication (et une division), et encore moins par rapport à des boucles ou des algos complexes. Si on prend le cas d'un tri à bulle, la complexité de l'algorithme est en N^3 : par rapport à ça, le fait que tu fasses 10 initialisations est la plupart du temps négligeable.

    Si c'est théorique, alors tu vas devoir tout compter à la main (ou équivalent), je ne connais pas de programme qui le fasse.

    Enfin, n'oublie pas qu'il y a une grosse différence entre le code que tu écris et le code réellement exécuté : les compilateurs font des passes d'optimasation (plus ou moins, tu peux forcer moins le cas échéant), et on pourrait aussi discuter du fait que si les valeurs sont en cache processeur, c'est beaucoup plus rapide que de faire une lecture mémoire (qui est elle-même plus rapide qu'une lecture disque, etc).
    Et n'oublie pas aussi que 0 est un registre pré-chargé sur certains processeurs, ce qui fait que int a = 0; est plus rapide que int a = 1;.

    Donc la réponse à ta question est : ça dépend
    "La route est longue, mais le chemin est libre" -- https://framasoft.org/
    Les règles du forum

  5. #5
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    En gros tu veux jeter un œil sur la sortie assembleur ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    $ gcc -O2 -S -fverbose-asm main.c

  6. #6
    Membre averti
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2011
    Messages
    754
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Août 2011
    Messages : 754
    Points : 376
    Points
    376
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    En gros tu veux jeter un œil sur la sortie assembleur ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    $ gcc -O2 -S -fverbose-asm main.c

    Je ne sais pas ce que ça donne, mais je vais essayer !

    =====================================================

    C'est sur une situation réelle...bien que pour moi ça reste plutôt théorique...

    On m'a donné une implémentation de l'algo de dijkstra utilisant une tas binaire implémenté avec une liste doublement chaînée.
    A coté j'ai fais une implémentation du même algo utilisant un tas binaire implémenté sous forme de tableau.

    Ce qui théoriquement devrait m'apporter une meilleure performance.

    Dans la pratique, quand je mesure les durées d'exécutions, les deux algos me font leur traitement en 0.01 secondes.

    Donc je cherche des éléments pour prouver que mon algo avec tableau est plus efficace. Si ce n'est pas sur la temporalité, c'est de mon point de vue forcément sur les accès mémoire.

    Notamment du fait que l'on va beaucoup de servir de décalage de bits avec l'implémentation du tableau ce qui ne devrait quasiment rien coûté.

    En somme, j'ai donc un résultat théorique que je suis sensé retrouver par la pratique.

    Hors ici le temps d'exe ne suffit pas.

  7. #7
    Modérateur
    Avatar de gangsoleil
    Homme Profil pro
    Manager / Cyber Sécurité
    Inscrit en
    Mai 2004
    Messages
    10 148
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Manager / Cyber Sécurité

    Informations forums :
    Inscription : Mai 2004
    Messages : 10 148
    Points : 28 113
    Points
    28 113
    Par défaut
    Je vois un peu mieux.

    Le temps que tu mesures est trop petit pour être précis, c'est pour ça que tu ne vois pas la différence. Il faut que tu appliques ton algo sur un volume de données beacoup plus grand, pour que ta durée de traitement soit significative, et que les temps annexes (initialisation, finalisation) deviennent négligeables (à moins qu'ils ne fassent partie de l'algo). Un temps de traitement de plusieurs secondes serait déjà plus significatif.
    "La route est longue, mais le chemin est libre" -- https://framasoft.org/
    Les règles du forum

  8. #8
    Membre expérimenté
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    Mai 2010
    Messages
    543
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Mai 2010
    Messages : 543
    Points : 1 745
    Points
    1 745
    Par défaut
    Bonjour
    +1 @gangsoleil "bonnes astuces", .

    Citation Envoyé par Matt_Houston Voir le message
    En gros tu veux jeter un œil sur la sortie assembleur ?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    $ gcc -O2 -S -fverbose-asm main.c
    Non. En quoi la sortie assembleur peut-elle aider ?. Mise à part lire le code assembleur généré avec des informations supplémentaires par exemple: les informations sur la version du compilateur et les options de ligne de commande, les lignes de code sources associées aux instructions sous la forme "non_du_fichier": "ligne de l'instruction": "contenue de la ligne", où encore d’autres informations sur lequel certaines expressions de haut niveau correspondent aux différents opérandes d'instructions ?. (ça n’aide pas) .

    Sinon, tout est dit précédemment, soit vous le faite a la main. Soit en utilisant les outils adéquats.
    Cependant l’algorithme de Dijkstra a ça propre complexité tout comme leurs variantes. Le plus simple est alors de commencer à faire l’évaluer la complexité en temps [B]de l’algorithmes de Dijkstra puis le vôtre. La comparaison des deux résultantes de l’évaluation démontrera que le vôtre ou celui de Dijkstra est le mieux adapté ou pas. De mémoire je sais que le temps d’exécution de l’algorithme de Dijkstra est O(n tMin(n) + m) avec un graphe stocké en listes d’adjacence. Soit "tmin(n) = O(n)", ce qui donne un temps d’exécution de l’algorithme de Dijkstra en "O(n2 +m) = O(n2)".
    En stockant les sommets sous forme d’une liste de sommets, en liste triée par ordre croissant des valeurs en utilisant des structures de données comme un tas binaire ou tas de Fibonacci. La complexité de l’algorithme devient O(m + n log n). (Car, l’étape de sélection d’un noeud demande au plus "n" opérations donc, au plus "n" fois sélection. Ce qui aux finales demande "n2" opérations y compris l’examen de chaque arc au plus une fois donc cela requiert "m" opération. Au finale l’algorithme est en n2 + m opérations ≤ 2 n2 opérations. donc O(m + n log(n)) mais là c'est le cas en temps d’exécution en utilisant des structures de données telles qu’un tas binaire ou un tas de Fibonacci). Bref, Sur la base d’une analyse en temps d’exécution, vous pouvez en déduire que le vôtre est mieux adapté et si vraiment vous souhaitez aller plus loin alors dans ce cas, déterminer la complexité spatiale des deux algorithmes et comparer les deux sous tous les points et apporter une conclusion efficace appuyons votre choix . libre à vous de faire comme bon vous semble à bientôt.
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

  9. #9
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    Janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : Janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    Citation Envoyé par Amnael Voir le message
    On m'a donné une implémentation de l'algo de dijkstra utilisant une tas binaire implémenté avec une liste doublement chaînée.
    A coté j'ai fais une implémentation du même algo utilisant un tas binaire implémenté sous forme de tableau.
    Quelle que soit l'implémentation «réelle» choisie la complexité asymptotique reste la même, seules les constantes changeront. Je raconte des bêtises mais pour une primitive classique hors construction de l'une des implémentation sera en 27+18 log n alors que pour l'autre on aura 57+15 log n, mais pour les deux la complexité sera en O(log n). C'est donc tout à fait normal d'avoir des résultats proches qui resteront proche pour de petites instances.
    Citation Envoyé par Amnael Voir le message
    Ce qui théoriquement devrait m'apporter une meilleure performance.
    Non théoriquement tu as des performances similaires, mais pourquoi aurais-tu de meilleure performance pratique avec un tableau ?

    L'avantage supposé d'utiliser un tableau est de garder les données locales et contigües = c'est cache friendly et ça ne «gaspille» pas la mémoire en pointeurs, sauf si éventuellement pour simplifier certains traitements tu décides de créer un arbre binaire complet avec tous les niveaux remplis.
    Le désavantage supposé d'utiliser les pointeurs est, en plus de leur consommation mémoire accrue (2 pointeurs en plus par sommets), de disperser les données en mémoire.

    Citation Envoyé par Amnael Voir le message

    Dans la pratique, quand je mesure les durées d'exécutions, les deux algos me font leur traitement en 0.01 secondes.

    Donc je cherche des éléments pour prouver que mon algo avec tableau est plus efficace. Si ce n'est pas sur la temporalité, c'est de mon point de vue forcément sur les accès mémoire.
    Oui, théoriquement ton algo à base de tableau est moins gourmand en mémoire, par définition.

    Citation Envoyé par Amnael Voir le message

    Notamment du fait que l'on va beaucoup de servir de décalage de bits avec l'implémentation du tableau ce qui ne devrait quasiment rien coûté.

    En somme, j'ai donc un résultat théorique que je suis sensé retrouver par la pratique.

    Hors ici le temps d'exe ne suffit pas.
    Essaye sur des instances plus grandes en faisant varier la densité des graphes. Plus un graphe sera dense, plus tu vas passer du temps à diminuer des clés dans ton tas.

  10. #10
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 352
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 352
    Points : 20 359
    Points
    20 359
    Par défaut
    Citation Envoyé par sambia39 Voir le message
    Non. En quoi la sortie assembleur peut-elle aider ?. Mise à part lire le code assembleur généré
    oui en apparence le code assembleur n'est pas forcément utile...
    mais faut connaitre un minimum l'assembleur pour que ça soit pertinent.
    Il y a des instructions qui demandent 3 cycles d'horloge comme MUL AX,registre (avec Intel -multiplier une valeur avec le registre AX ) et d'autres qui n'en demandent qu'un seul..( vérifier dans la doc d'Intel sur le jeu d'instructions )
    Donc cela permet éventuellement de détecter les goulots d'étranglement.
    Mais étant donné que les CPU et les OS sont multitâches oui c'est peut-être pas toujours bien révélateur.

    Ensuite là c'est précisément analyser les performances et non pas la complexité d'un algorithme ( bref le sujet demandé)

    Et puis il y aussi le problème du cache hardware d'instructions en entrée au niveau du CPU( il y en même deux niveaux ) qui peut éventuellement fausser les mesures mais ça c'est un autre débat

  11. #11
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    Euh.. ben non, la demande de l'OP n'est pas claire justement. Quand je lis ça :

    Citation Envoyé par Amnael Voir le message
    En gros si mon programme c'est

    int nb= 3 + 2;

    A la fin je veux détecter qu'il y a eu 2 opérations. Une affectation et une addition.

    Si j'ai

    int a=3;
    int b=2;
    int nb = a+b;

    Je détecte 6 opérations dont 3 affectation 1 addition et 2 accès mémoires.
    Ben c'est pas la complexité algorithmique qu'on cherche à mesurer là. Si on veut voir ce que ça donne effectivement en terme d'instructions, ben faut lire la sortie assembleur. De chaque architecture cible. Mais peut-être connaissez-vous un moyen plus direct.. oh wait, y'en a pas.

    Donc non c'est pas évident. Raison pour laquelle je tente une passe à l'as en évoquant cette possibilité au risque d'être hors-sujet et raison pour laquelle je formule mon message sous forme de question.

  12. #12
    Membre expérimenté
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    Mai 2010
    Messages
    543
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Mai 2010
    Messages : 543
    Points : 1 745
    Points
    1 745
    Par défaut
    Bonjour,
    Citation Envoyé par Mat.M Voir le message
    oui en apparence le code assembleur n'est pas forcément utile...
    mais faut connaitre un minimum l'assembleur pour que ça soit pertinent.
    Il y a des instructions qui demandent 3 cycles d'horloge comme MUL AX,registre (avec Intel -multiplier une valeur avec le registre AX ) et d'autres qui n'en demandent qu'un seul..( vérifier dans la doc d'Intel sur le jeu d'instructions )
    Donc cela permet éventuellement de détecter les goulots d'étranglement.
    Mais étant donné que les CPU et les OS sont multitâches oui c'est peut-être pas toujours bien révélateur.

    Ensuite là c'est précisément analyser les performances et non pas la complexité d'un algorithme ( bref le sujet demandé)

    Et puis il y aussi le problème du cache hardware d'instructions en entrée au niveau du CPU( il y en même deux niveaux ) qui peut éventuellement fausser les mesures mais ça c'est un autre débat
    D’accord, mais on quoi cela va-t-il être concrètement pertinent ou utile pour l'évaluation d'une complexité algorithmique? Dans un contexte d’optimisation, cela est acceptable (sans oublier que les récents compilateurs appliquent de façon automatique un certain nombre d'optimisations). Bref, pour moi choisir le bon algorithme est déjà un bon point de départ d’optimisation de haut niveau et facilite dans la limite du possible l'optimisation bas niveaux avec le langage assembleur. Ceci dit qu’il ne faut pas non plus procéder à une optimisation à tout va dés le départ d'un projet ou l'écriture du codes, mais uniquement en cas de nécessité (du type du projet ou architecture par exemple) justifiable. Après c’est mon point de vue et y a pas lieu de parler d’assembleurs pour ma part.
    Cependant, je suis d’avis avec vous sur l’analyse de performance et il existe des outils pour. Ce n’est qu’une confusion de la part de l’auteur.
    à bientôt.
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Evaluer la complexité des Algorithmes
    Par AkiyamaS dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 08/04/2013, 17h27
  2. Réponses: 8
    Dernier message: 28/04/2011, 10h56
  3. [AJAX] comment programmer les evaluations avec les etoiles?
    Par makohsarah dans le forum Général JavaScript
    Réponses: 0
    Dernier message: 26/04/2008, 23h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo