Discussion :

[baccali]

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

[souviron34]

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)

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)

[baccali]

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?

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

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!

[souviron34]

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

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!

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é

[baccali]

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

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

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?

[souviron34]

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

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

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

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

[baccali]

cela dépend des implémentations :

Donc plus tellement portable! Tu le vis bien?

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 :

Tu te crois sur msn?

[souviron34]

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

[baccali]

"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?!!

[Neckara]

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.

[anacharsis]

restons calmes ...

A+

[youssef_the_king]

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 :

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

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

[souviron34]

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

Qui a dit le contraire ???

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