Discussion :

[chneu87]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[baccali]

Bonjour,

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

[Neckara]

En commande shell,

time ./mon_programme

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

[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.

[Thierry Chappuis]

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

[souviron34]

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...

[valefor]

_ 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 ?

[anacharsis]

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+

[baccali]

Quelle est cette option ?

Salut,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

CONFIG_PREEMPT=n

Cordialement

[pfeuh]

Salut,

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

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

[anacharsis]

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+

[valefor]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[souviron34]

'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...

[anacharsis]

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

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+

[valefor]

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

[anacharsis]

le trier...

A+

[chneu87]

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.

[valefor]

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).

[ManusDei]

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

[anacharsis]

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

A+