Evaluer la complexité d'un programme

Version imprimable

26/10/2016, 17h41
Amnael

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 !
26/10/2016, 17h49
picodev

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.
27/10/2016, 11h53
Amnael

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.
27/10/2016, 12h04
gangsoleil

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 :)
27/10/2016, 12h09
Matt_Houston

En gros tu veux jeter un œil sur la sortie assembleur ?

Code:

$ gcc -O2 -S -fverbose-asm main.c
27/10/2016, 13h08
Amnael

Citation:

Envoyé par Matt_Houston

En gros tu veux jeter un œil sur la sortie assembleur ?

Code:

$ 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.
27/10/2016, 14h32
gangsoleil

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.
27/10/2016, 14h50
sambia39

Bonjour
+1 @gangsoleil "bonnes astuces", .

Citation:

Envoyé par Matt_Houston

En gros tu veux jeter un œil sur la sortie assembleur ?

Code:

$ 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(n² +m) = O(n²)".
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 "n²" 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 n²+ m opérations ≤ 2 n² 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.
27/10/2016, 15h31
picodev

Citation:

Envoyé par Amnael

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

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

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

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.
27/10/2016, 20h43
Mat.M

Citation:

Envoyé par sambia39

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 :mouarf:
27/10/2016, 21h30
Matt_Houston

Euh.. ben non, la demande de l'OP n'est pas claire justement. Quand je lis ça :

Citation:

Envoyé par Amnael

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.
31/10/2016, 17h26
sambia39

Bonjour,

Citation:

Envoyé par Mat.M

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

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.