performences des algorithimes Fermé

Question

comment on peut savoir si un programme(en programation) consome moins de ressource et moins de 
temps en execution que un notre qui fait la meme chose que le premier

Nico# · Answer

Salut, Tout dépend du langage est de la façon dont le programme est écrit.

Exemple :

en C#

int i = 0;
While ( i < 100 )
{
      Console.WriteLn( i.ToString());
      i++;
}

est beaucoup plus rapide que 

For( int i = 0; i < 100; i++ )
{
    Console.WriteLn( i.ToString());
}

Ensuite Pour le langage C# est plus long en exécution que C car C# est un langage interprété dans plus lent.

J'espére t'avoir aidé mais si tu as d'autres questions je suis la.

mamiemando · Answer

Bah si ce que tu dis est vrai, ça veut dire que c# ça craint vraiment :-) En plus en C++ c'est le contraire une boucle for est plus rapide qu'un while :-) (et c'est tellement peu sensible qu'au final c'est pareil).

Pour regarder les performances d'un algorithme il suffit de regarder ce qu'il consomme en RAM/CPU via un gestionnaire de processus. Sous windows, il suffit de faire ctrl alt suppr. Sous linux la commande "top" permet faire de même. Le temps d'exécution est également modifié.

Par ailleurs sans écrire de programme il suffit aussi parfois de regarder sa complexité (au sens de la théorie de l'information) :
https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_l%27information

La complexité s'écrit sous la forme O(f(m,n,p...)) ou m,n,p indiquent la taille d'un paramètre. Par exemple considérons le programme de Nico #

void ecrire_chiffre_1_a_n(unsigned int n){
  for(i = 1 ; i <= n ; ++i){ // pour i allant de 1 à n
    printf("%d
",i); // écrire la valeur i
  }
}
L'instruction "écrire i" est en temps constant O(1), par contre la boucle pour s'exécute n fois (n = 100). La complexité de cet algorithme est donc O(n) ou n est un paramètre du programme.

Supposons à présent que je veuille écrire une matrice de taille m,n ou m est le nombre de ligne, n le nombre de colonne, et où la case à la position (i,j) contient la valeur i+j :
void ecrire_matrice(unsigned m,unsigned n){
  for(unsigned i=0;i<n;++i){
    for(unsigned j=0;j<m;++j){
      printf("%d	",i+j);
    }
    printf("
"); // revenir à la ligne
  }
}
L'instruction en gras est en O(1), la boucle en italique en O(m), et le programme en O(m.n).

Ainsi la manière dont tu écris ton programme est effectivement primordiale et doit offrir une complexité aussi faible que possible. Aujourd'hui un problème "facile" est de complexité polynomiale ou logarithmique (ou moins). Les autres problèmes (par exemple donc la complexité est en puissance de n ou exponentielle) sont dit difficiles.

Après, comme l'évoque Nico#, un langage peut être un peu plus efficace pour une même complexité selon la manière dont il est implémenté... mais si c'est un vrai langage normalement tu n'as pas à en tenir compte. Par contre il faut prendre garde à certaines choses importantes. Par exemple, une entrée sortie (écrire dans un fichier ou sur une console) est quelque chose de coûteux, il faut donc éviter d'en abuser. Par ailleurs certaines options de compilations permettent d'optimiser l'efficacité d'un même code (option -O pour gcc et g++ si tu programmes en C ou en C++).

En espérant que tout ceci t'aura un peu éclairé, bonne chance !

Nico# · Answer

Oui Mais regarder la charge CPU/RAM  pour un programme Dotnet et tres eleve car l'execution du framework prend 32Mo je crois

Doctor C · Answer

L'explication de mamiemando est excellente...

simplement rajouter que dans un programme, plus tu as de boucles imbriquées, plus la complexité augmentera donc, plus ton programme sera lent.

C'est pourquoi il est intéressant de se pencher sur des algorithmes rapides. L'utilisation de la récursivité est bien utile dans certaines situations pour éviter l'abus the boucles.

après d'aussi bonnes explications, je ne sais pas trop quoi rajouter!

mamiemando · Answer

Je suis flattée ;-)

Performences des algorithimes

5 réponses