Temps d'exécution algorithme

Bonjour,

Je doit effectuer un projet qui permet de comparer le temps d'exécution de différent algorithme de tri.

Voici mon code

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

double t1, t2, t3; long clk_tck = CLOCKS_PER_SEC; t1 = clock(); tri_par-selection(); t2 = clock(); t3 = t2-t1; printf ("Temps consommes : %lf",t3/(double)clk_tck);   . . .   // ici la méme chose avec d'autre fonction de tri

---

La fontion marche quelque fois(sa affiche 0.0015 ou autre), mais elle affiche souvent 0.000 sec.

Y a t'il un moyen pour avoir plus de précision ? esque ma facon de faire est correcte ?

Merci bonne soirée.

Bonjour,

Citation:

---

Envoyé par chneu87

Y a t'il un moyen pour avoir plus de précision ?

---

Malheureusement non! Est ce que ton projet doit forcément être basé sur la pratique? Parce que le problème dans ce raisonnement c'est le fait que ton système est multitâche. C'est à dire qu'il interrompt ton programme pour laisser la place à d'autres et en favorise même certains qui ont la priorité de passage! D'où les différences que tu as constaté dans les résultats (tu peux avoir un algo 20 fois plus rapide qu'un autre mais si le kworkerd passe par là c'est fichu)

Et tu n'as concrêtement aucun moyen de prévoir le scheduler (et d'autres facteurs d'ordres "matériels" mais moins pénalisants). Et la commande clock() te donne le résultat en millisecondes en partant d'une date bien précise (1700 sur Linux je crois). Bref, en assembleur comme dans n'importe quel autre langage, on a pas encore trouvé de solution matérielle ou logicielle "convenable". C'est un problème bien connu dans les benchmarks. Les résultats sont soumis à l'environnement.

Donc tu as deux solutions (trois en fait mais la dernière est trop compliqué pour rien!).

_ Soit tu te bases sur des statistiques, tu fais tourner chaque algo en boucle genre 1 000 000 de fois par machine et tu fais des moyennes.

_ Soit tu passes par la logique et l'algorithmique. Ca reste quand même la solution la plus fiable et la plus complète. Tu peux savoir par exemple à partir de quelles valeurs tel algo devrait être plus rapide qu'un autre etc...

_ Sinon tu peux aussi recompiler un noyau linux ne faisant tourner qu'un programme à la fois. C'est simple à faire, certe (une option à changer dans le .config), mais ça reste ch*ant pour un seul exercice et surtout si ce n'est pas pour tester d'autres choses en plus comme les bugs et le comportement du programme.

Cordialement

En commande shell,

time ./mon_programme

Il affichera le temps utilisateur, le temps total et le temps sur le CPU il me semble.

Vous pouvez utiliser clock_gettime.

Selon votre os, architecture etc, c'est une fonction qui vous donne une précision pouvant aller jusqu'à la nanoseconde (demander à clock_getres).


Le clock id vous permet de choisir une horloge locale au process (CLOCK_PROCESS_CPUTIME_ID).

Pour le reste voir les pages de man.

Citation:

---

Envoyé par valefor

Vous pouvez utiliser clock_gettime.

Selon votre os, architecture etc, c'est une fonction qui vous donne une précision pouvant aller jusqu'à la nanoseconde (demander à clock_getres).


Le clock id vous permet de choisir une horloge locale au process (CLOCK_PROCESS_CPUTIME_ID).

Pour le reste voir les pages de man.

---

Utilisable uniquement sur les système POSIX.

La Glib fournit des outils de mesures portables qui permettent une résolution de la microseconde. Toutefois, cela reste avant tout un problème d'algorithmique.

Thierry

Citation:

---

Envoyé par chneu87

BY a t'il un moyen pour avoir plus de précision ? esque ma facon de faire est correcte ?

---

oui..

J'ai posté il y a quleques années dans la rubrique Sources une fonction éqivalente à clock() donnant le temps en micro-secondes

Recuperer le temps reel absolu

Maintenant, cette mseure sera empirique.

Comme l'a signalé Baccali, la vraie comparaison est algorithmique, par rapport à la complexité algorithmique...

Citation:

---

Envoyé par baccali

_ Sinon tu peux aussi recompiler un noyau linux ne faisant tourner qu'un programme à la fois. C'est simple à faire, certe (une option à changer dans le .config)

---

Quelle est cette option ?

si tu peux accéder à une machine msdos avec un compilateur C alors tu as une solution simpliste. j'en ai encore 1 ou 2 ... mais les résultats ne correspondent pas aux architectures actuelles. tous les instruments de mesure sont faux, même sous unix, les temps cpu affichés tiennent compte d'une partie de la mise en place du cadre utilisateur pour son quota de temps. mais ils donnent une bonne idée quand même ! la seule vraie solution, c'est de disposer d'une vraie machine monotache ou bien de la simuler; c'est ce qu'a fait knuth (The Art of Computer Programming) mais c'est assez lourd à mettre en place. si le sujet t’intéresse vraiment passe moi un mp (si çà intéresse beaucoup de monde on peut publier un petit truc).

mais la vielle machine msdos, c'est très très bien ...

A+

Citation:

---

Envoyé par valefor

Quelle est cette option ?

---

Salut,

Code:

---

CONFIG_PREEMPT=n

---

Cordialement

Salut,

Citation:

---

Envoyé par chneu87

La fontion marche quelque fois(sa affiche 0.0015 ou autre), mais elle affiche souvent 0.000 sec.

---

C'est un problème de granularité. A ta place, je contournerai le problème. Si les temps ne sont pas affichables parce que trop petits, fais boucler. Ça marche très bien pour comparer des performances de fonctions. En exemple la comparaison de deux fonctions de swap un peu différentes. C'est toujours empirique, mais c'est quand même lissé suffisamment.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

#include <stdio.h> #include <time.h> #include <assert.h>   void swap1(int *a, int *b) { static int c; c = *a; *a = *b; *b = c; }   void swap2( int * const a, int * const b) { int c = *a; *a = *b; *b = c; }   size_t looper(void (*pfunc)(int*, int*)) { int a = 12345678; int b = 23456789; size_t now = time(0); int count = 0; while(count++ < 2000000000) pfunc(&a, &b); return time(0) - now; }   void utest(void) { int a = 1234; int b = 5678; swap1(&a, &b); assert(a == 5678); assert(b == 1234); swap2(&a, &b); assert(a == 1234); assert(b == 5678); }   int main(void) { utest(); printf("2000000000 calls of swap1 : %u seconds\n", looper(swap1)); printf("2000000000 calls of swap2 : %u seconds\n", looper(swap2)); return 0; }

---

Citation:

---

Envoyé par anacharsis

la seule vraie solution, c'est de disposer d'une vraie machine monotache

---

Même sur une machine monotâche il y a des interruptions, donc du temps non maitrisé.

A+

Pfeuh

pour les interruptions tu as 100 fois raison. seule la méthode de knuth n'en tient pas compte. mais elles existent dans tous les systèmes, quelque soit le schéma les résultats sont biaisés.

ta réponse intelligente n'a fait plaisir. merci !

A+

Citation:

---

Envoyé par baccali

Code:

---

CONFIG_PREEMPT=n

---

---

Ha oui, du coup il ne suffit pas que de recompiler le noyau, il reste encore du code à écrire après ça :)

'fin bref, ça dérive pas mal :

• clock() et la fonction de la Glib mentionnée par Thierry Chapuis fournissent le temps utilisateur
  
  
• ma fonction GetClock() donne le temps réel absolu (système).
  
  
• la vraie solution de comparasion entre des algorithmes est le calcul de la complexité algorithmique, comme l'a mentionné Baccali (ce qui est aisément trouvable pour les divers tris : Sorting algorithm)

Recompiler un kernel ou avoir une machine monotâche sans OS (car l'OS tourne en même temps que l'appli), c'est pire que prendre un bulldozer pour écraser une mouche... :aie:

c'est vrai qu'on a pas mal dérivé :

Citation:

---

Je doit effectuer un projet qui permet de comparer le temps d'exécution de différent algorithme de tri.

---

je ne pense pas que son directeur de projet souhaite un cours sur la complexité des algorithmes. il garde ça pour lui ... et il sera très content avec des clock().
un tableau d'entiers assez grand pour que les temps ne soient pas ridicules (64000 c'est assez).

A+

Et le tableau d'entier c'est pour quoi ?

le trier...

A+

Merci de vos réponses, qui m'aide beaucoup. Je suis encore à la recherche de solutions.

Le sujet me semble trés vaste et du coup je recherche les divers possibilitées.

Si vous avez d'autres solutions ou des "précisions" sur des remarques déjà publées n'hésitez pas, ça ne pourra que m'aider.

Citation:

---

Envoyé par anacharsis

le trier...

A+

---

Rha ben oui :). Je pensais que c'était pour enregistrer les temps relevés (donc dans ton exemple, il aurait fait 64000 runs).

Bonjour,

je ne suis pas sûr d'avoir saisi ton problème. Tu cherches à connaître le temps d'exécution du programme, ou écrire un programme A qui compte le temps d'exécution du programme B ?

Dans le premier cas, tu peux utiliser un framework de WCET (Worst Case Execution Time).
Dans le second, bon courage :D

salut !
comment trouver le WCET d'un tri rapide dont on ne dispose pas du code ?

A+

Citation:

---

Envoyé par anacharsis

salut !
comment trouver le WCET d'un tri rapide dont on ne dispose pas du code ?

---

J'ai encore un peu de mal avec l'algorithmique (je suis en plein dedans!). Mais sans l'algo exacte et en particulier la sélection du pivot, je dirai que c'est impossible. D'ailleurs même pour le temps moyen tu ne peux que supposer.


Concernant la question initiale, un bon moyen de connaitre le temps serait aussi de lire les statistiques (maintenues par le système), du pid. Les fichiers se trouvent dans /proc/<pid>/stats. C'est le principe d'utilitaires comme top. Tu peux éviter les getpid() en lisant directement /proc/self/stat.

Cordialement

Citation:

---

Envoyé par baccali

J'ai encore un peu de mal avec l'algorithmique (je suis en plein dedans!). Mais sans l'algo exacte et en particulier la sélection du pivot, je dirai que c'est impossible. D'ailleurs même pour le temps moyen tu ne peux que supposer.

---

Non, la complexité n'en dépend pas...

La complexité algorithmique dépend du comportement de l'algo par rapport à la taille de l'entrée.. (ce qu'on note avec O() : regarde le chapitre Computational_complexity et Big_O_notation)

Citation:

---

Envoyé par baccali

Concernant la question initiale, un bon moyen de connaitre le temps serait aussi de lire les statistiques (maintenues par le système), du pid. Les fichiers se trouvent dans /proc/<pid>/stats. C'est le principe d'utilitaires comme top. Tu peux éviter les getpid() en lisant directement /proc/self/stat.

---

Pourquoi faire simple (et portable) quand on peut faire compliqué (et non portable) :aie:

Citation:

---

Envoyé par souviron34

Non, la complexité n'en dépend pas...

La complexité algorithmique dépend du comportement de l'algo par rapport à la taille de l'entrée.. (ce qu'on note avec O() : regarde le chapitre Computational_complexity et Big_O_notation)

---

Et tu fais comment pour connaitre la complexité de l'algo si tu ne l'as pas?

Citation:

---

Envoyé par souviron34

Pourquoi faire simple (et portable) quand on peut faire compliqué (et non portable) :aie:

---

Tout simplement parce qu'on exploite les ressources mises à disposition par le système (ressources qui sont rarement portables). Si tu veux le temps de ton algo sans le temps que le système à mis à exécuter d'autres threads pendant que tu faisais tes appels systèmes, une solution non portable c'est la seule solution à ma connaissance, n'en déplaise à souviron34!

Citation:

---

Envoyé par baccali

Et tu fais comment pour connaitre la complexité de l'algo si tu ne l'as pas?

---

En l'occurence le PO les avait puisqu'il voulait comparer différents algos de tris :aie:

Citation:

---

Envoyé par baccali

Tout simplement parce qu'on exploite les ressources mises à disposition par le système (ressources qui sont rarement portables). Si tu veux le temps de ton algo sans le temps que le système à mis à exécuter d'autres threads pendant que tu faisais tes appels systèmes, une solution non portable c'est la seule solution à ma connaissance, n'en déplaise à souviron34!

---

:mrgreen: :mouarf:

Euh..

• clock() est portable et donne le temps utilisateur (c'est à dire le temps que ce process a utilisé) (ce qui était pourquoi j'avais fait la fonction GetClock, j'avais besoin d'un temps absolu et non pas relatif)
  
  
• la fonction de la Glib je n'ai pas testé

Citation:

---

Envoyé par souviron34

En l'occurence le PO les avait puisqu'il voulait comparer différents algos de tris :aie:

---

Citation:

---

Envoyé par anacharsis

salut !
comment trouver le WCET d'un tri rapide dont on ne dispose pas du code ?

---

;)

Citation:

---

Envoyé par souviron34

Euh..

• clock() est portable et donne le temps utilisateur (c'est à dire le temps que ce process a utilisé) (ce qui était pourquoi j'avais fait la fonction GetClock, j'avais besoin d'un temps absolu et non pas relatif)
  
  
• la fonction de la Glib je n'ai pas testé

---

Effectivement clock() est donne par processus (jamais utilisé). Seulement il me semble que clock() te donne le temps utilisateur d'un programme mais que ce temps inclue aussi le kernel mode donc le problème est le même! Il me semble que si le kernel mode attend la réponse du disque dur 2 secondes, ces 2 secondes sont inclues dans l'algo. Ou je me trompe?

Citation:

---

Envoyé par baccali

;)

---

Ce n'est pas le PO ni son problème.. :

Citation:

---

Envoyé par chneu87

Je doit effectuer un projet qui permet de comparer le temps d'exécution de différent algorithme de tri.

---

:P

Citation:

---

Envoyé par baccali

;)
Effectivement clock() est donne par processus (jamais utilisé). Seulement il me semble que clock() te donne le temps utilisateur d'un programme mais que ce temps inclue aussi le kernel mode donc le problème est le même! Il me semble que si le kernel mode attend la réponse du disque dur 2 secondes, ces 2 secondes sont inclues dans l'algo. Ou je me trompe?

---

cela dépend des implémentations :

man clock

Citation:

---

Sur plusieurs autres implémentations, la valeur renvoyée par clock() inclue aussi le temps écoulé pour l'exécution des processus fils dont les statistiques ont été collectées lors d'un appel de la famille wait(2). Linux n'inclut pas le temps des enfants attendus dans la valeur renvoyée par clock().

---

Et, tant quà avoir quelque chose de dépendant de l'OS, autant se servir des outils fournis sans réinventer le fil à couper le beurre :

man time :D

Citation:

---

Envoyé par souviron34

cela dépend des implémentations :

---

Donc plus tellement portable! Tu le vis bien?

Citation:

---

Envoyé par souviron34

Et, tant quà avoir quelque chose de dépendant de l'OS, autant se servir des outils fournis sans réinventer le fil à couper le beurre :

---

Effectivement j'y avais pas pensé mais c'est plus simple!

P.S :

Citation:

---

Envoyé par souviron34

:P 8O :aie: 8O :cfou: :D

---

Tu te crois sur msn?

Citation:

---

Envoyé par baccali

Tu te crois sur msn?

---

tu préfères que je te dise "tu nous gonfles, ça fait 15 messages que la discussion est close et qu'on a répondu au PO" ????

Citation:

---

Envoyé par souviron34

"tu nous gonfles, ça fait 15 messages que la discussion est close et qu'on a répondu au PO" ????

---

Qui t'as obligé à lire et répondre?!!

Citation:

---

Envoyé par souviron34

:mouarf:

---

Citation:

---

Envoyé par souviron34

tu préfères que je te dise "tu nous gonfles, ça fait 15 messages que la discussion est close et qu'on a répondu au PO" ????

---

Le but d'un sujet de forum n'est pas seulement de répondre à la question du PO, mais de permettre à tous les futurs lecteurs ayant la même question que le PO de trouver la solution.

En continuant la discutions et en approfondissant le sujet, ceci permet non pas de flooder, mais d'apporter aux autres lecteurs voir même au PO un approfondissement bénéfique qui peut anticiper des questions futures.

restons calmes ...

A+

la fonction clock() , define dans la bibliothèque time.h, ne retourne pas un float mais un clock_t . Alors je me propose pour chronometrer votre trie de faire :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <time.h> ...   double temps; clock_t start; start = clock(); //le compteur //fct à chronometrer temps = (double)(clock()-start)/(double)CLOCKS_PER_SEC; printf("\n en %.2f seconde(s)!\n", temps);   }

---

merci :ccool:

Citation:

---

Envoyé par youssef_the_king

la fonction clock() , define dans la bibliothèque time.h, ne retourne pas un float mais un clock_t .

---

8O

Qui a dit le contraire ???

Et toutes les réponses ont été données...