Temps d'exécution algorithme

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