Calcul de temps [Résolu]

[invitee3128aa2]

Bonjour , j'ai une question qui je pense est impossible à résoudre , nous voulons un algorithme qui calcule le temps qu'il met du début à la fin de son exécution , un tel algorithme peux-il exister ?
-----

[invite2800a7c8]

Bonjour , j'ai une question qui je pense est impossible à résoudre , nous voulons un algorithme qui calcule le temps qu'il met du début à la fin de son exécution , un tel algorithme peux-il exister ?

Salut,
j'ai pas bien compris,
En général pour tester le temps d'exécution d'une routine, on la met dans une boucle et on l'exécute 1 million de fois par exemple.
On prend le temps avant puis après.
Pour le temps propre de la boucle on met d'abord un NOOP dans la boucle et on la fait tourner quelques millions de fois
( Boucle vide)
Ceci est une façon de faire parmis des milles.

Cordialement
Ludwig

[invitee3128aa2]

Non , ma question est un algorithme qui calculerais le temps de sa propre exécution est-il réalisable ?

[invitef86a6203]

On met en route un timer au début.
puis on le lit à la fin.

c'est tout !

[A voir en vidéo sur Futura]

[invite2800a7c8]

Non , ma question est un algorithme qui calculerais le temps de sa propre exécution est-il réalisable ?

Tu veux faire quoi au juste?
La vitesse d'exécution de n'importe quel Programme est liée au cadencement de ton calculateur (Compteur ordinal)
Tu lis le temps avant puis après, le temps est donné par le circuit horloge qui se trouve dans le calculateur.

Cordialement

Ludwig

[invitee3128aa2]

Non moi je dis calculer et non mesurer le temps de son exécution .

[invitee3128aa2]

Je donne un exemple mais qui je sais ne fonctionne pas , l'algorithme connais le nombre d'instruction qui le composent il connais le temps d'exécution de chaque instruction , il obtient un temps d'exécution mais pas SON temps d'exécution .

[invitee3128aa2]

...t il connais le temps d'exécution de chaque instruction ...

Désolé petite erreur sur ce point il mesure le temps d'exécution d'une instruction (il est donné après l'exécution d'une instruction) , en considérant que le temps varie en fonction de l'instruction .

[invitef86a6203]

les datasheets des µp donne le temps en cycles.
Si la procédures est de longueur fixe avec une boucle simple , il suffit de faire la multiplication.

S'il s'agit de procédures complexes avec des boucles variables qui varient à l'intérieur de la procédure et si en plus elles sont imbriquées, ça devient mission impossible , le calcul risque d'être plus long que l’exécution et surtout dépendre des données entrantes.

[invite6486d7bd]

Pour ce qui est du calcul du temps d'execution d'une portion de code d'un programme ou d'un programme qui commence et se termine de manière prédictive, c'est ce qu'on faisait à une époque (à la main) lorsqu'on voulait faire le programme le plus rapide possible en assembleur, sur des machines très simples.

On se référait à une table qui pour chaque instruction d'un processeur particulier donnait le temps d’exécution.
De nos jours, avec les processeurs qui exécutent en parallèle des instruction qui se suivent (mais qui n’interfèrent pas entre elles) le calcul ne peut plus se référer à une simple table.
On doit connaitre la stratégie d'un processeur en particulier, ainsi que les temps d’Accès à la mémoire, qui dépendent du Bus.

De plus avec l'avènement des systèmes d'exploitation multitâches, le programme n'est plus seul à s’exécuter (le système d'exploitation pour le moins tourne lui aussi), ce qui fait que le calcul est forcément faux.

Maintenant, qu'un programme ait pour fonction de calculer le temps qu'il met à calculer son propre temps d’exécution, c'est, comment dire, super inutile...

[invitee3128aa2]

Donc c'est impossible . voici à quoi j'ai pensée en écrivant mon premier message un algorithme qui pendant qu'il calcule le temps qu'il à mis jusque là , doit calculer le temps qu'il à mis pour calculer le temps qu'il à mis jusque là , etc ... c'est une boucle insolvable si on considère le temps d'exécution des instructions variable , on peux juste donné une approximation .

[invitef86a6203]

ça peut être une statistique , une évaluation, un peu comme lorsqu'on télécharge un long fichier , il dit qu'il reste xx temps.
Mais ça ne peut pas être un calcul précis...

[invitee3128aa2]

Mais même si on considère que les mesure du temps mis à l'exécution sont parfaitement précises , cette algorithme ne pourrait quand même pas exister , car la boucle cité plus haut ne s'arrêterais jamais .

[invite6486d7bd]

Mais même si on considère que les mesure du temps mis à l'exécution sont parfaitement précises , cette algorithme ne pourrait quand même pas exister , car la boucle cité plus haut ne s'arrêterais jamais .

A priori, c'est ce qu'on pourrait croire.
Mais, si "on", c'est à dire le programme fait appel à une table fixe, imaginons un programme qui tourne sur un Z80, il peut, il me semble, faire la somme des durées de ses propres instructions, instructions de somme comprises.
Le programme s'arretera à la dernière instruction ADD (dont la durée est connue du programmeur) et qui écrit la donnée sans la derniere instruction augmentée de la durée de la dernière instruction (cette valeur constante à ajouter est en mémoire et n'a pas de durée, elle fait partie de l'instruction finale), genre "ADD valeur presque-finale, durée de ADD".

[invitee3128aa2]

Moi je parle du temps totale (la dernière instruction comprise ).

[invite6486d7bd]

Moi je parle du temps totale (la dernière instruction comprise ).

Moi aussi, et la durée de la dernière instruction peut être codée, soit en dur (exemple, 100), soit en copiant la valeur récupérée depuis la table à l’adresse qui contient la valeur que l'on doit ajouter à la valeur calculée sans la dernière instruction.
Comme dit, cette valeur n'influe pas sur la durée de l'instruction ADD.
Si la dernière instruction se trouve à l'adresse 2114, la valeur associée à cette instruction se trouve à l'adresse 2115.
Pour mieux comprendre ADD est une instruction et xx la valeur et lorsque je dis que xx est la valeur de l'instruction ADD ça s'écrit ADD (HL), xx.
En mémoire on a donc le code de l'instruction suivi par une valeur ;
L'Adresse 2114 contient : Code de ADD (HL), nn (ex: 3Fh)
L'Adresse 2115 contient : Valeur (ex: 64h)
Si par exemple HL est l'adresse contenant la durée sans la dernière instruction, ADD (HL), 100 a le même temps d'instruction que ADD (HL), 200, par exemple => la "valeur" n'influe pas sur la durée de ADD.

Il y d'autre manières de programmer le résultat final (ici c'est juste la première idée la plus simple qui m'est passé par la tête, n'ayant par ailleurs plus programmé en assembleur depuis longtemps).

Donc à mon avis le programme est faisable.

[invitee3128aa2]

Je comprend ce que tu dis mais malheureusement le temps des instruction ADD n'est pas similaire quand bien même il le serait pour des valeur similaires si le temps que prend un ADD est un nombre avec énormément de décimales aléatoires une sorte de nombre pseudo-aléatoire , la somme serais différente à chaque fois car le temps changera à chaque fois .

[invite6486d7bd]

Je comprend ce que tu dis mais malheureusement le temps des instruction ADD n'est pas similaire quand bien même il le serait pour des valeur similaires si le temps que prend un ADD est un nombre avec énormément de décimales aléatoires une sorte de nombre pseudo-aléatoire , la somme serais différente à chaque fois car le temps changera à chaque fois .

Le temps des différents types d'ADD change effectivement, mais il me semble que pour un type d'ADD la valeur n'influe pas sur le temps d'instruction.
Ceci dit, maintenant que vous me le faites remarquer, il est possible, il est vrai, que les registres de flag qui peuvent être plaçés par le processeur lors d'un calcul puisse influer très légèrement sur la durée, à vérifier.
Mais si on va jusque là, il faut aussi prendre en compte la température de la pièce .

[invitee3128aa2]

Donc ça reste un problème impossible à résoudre .

[invite6486d7bd]

Donc ça reste un problème impossible à résoudre .

Je ne dirais pas ça, sinon on devrait dire que tout calcul basé sur une mesure préalable (durée d'une instruction, longueur un bassin, hauteur d'une tour, poids d'un objet) est impossible.
A un moment donnée, un calcul est considéré comme juste lorsque la précision atteint un seuil acceptable.
Il n'y a que les calculs basé sur des valeurs virtuelles ou issues d'un comptage (3 pommes ça reste 3 pommes) qui peuvent être parfaitement justes.

Ici, le seuil est, je pense, acceptable et il n'existe pas de problème lié à l'algorithmique à proprement parler car si on a la table des durées qu'on considère suffisamment exacte, qui peut même être raffinée par le variation (éventuelle, puisque comme je l'ai dit, je ne sais pas exactement) induite par les valeurs associées aux instructions, le programme peut être réalisé (il se complique certes mais ce n'est pas la question).

[invitee3128aa2]

Ma question traiter de temps parfait et non de temps acceptable , il est bien sûr possible de créer un tel algorithme de cette manière .

[CM63]

Mais même si on considère que les mesure du temps mis à l'exécution sont parfaitement précises , cette algorithme ne pourrait quand même pas exister , car la boucle cité plus haut ne s'arrêterais jamais .

Tout-à-fait. Car dès que tu ajoutes des instructions pour compléter le calcul, cela consomme à nouveau des ressources, etc. C'est une illustration du fait bien connu en physique: qu'on ne peut mesurer un phénomène physique sans le modifier.
Mais il suffit de s'arrêter lors de la première insertion d'instruction: certes on a modifié le phénomène physique, mais on mesure bien le phénomène ainsi modifié.

[invitee3128aa2]

Tout-à-fait. Car dès que tu ajoutes des instructions pour compléter le calcul, cela consomme à nouveau des ressources, etc. C'est une illustration du fait bien connu en physique: qu'on ne peut mesurer un phénomène physique sans le modifier.
Mais il suffit de s'arrêter lors de la première insertion d'instruction: certes on a modifié le phénomène physique, mais on mesure bien le phénomène ainsi modifié.

Oui , mais on ne pourra jamais prévoir le temps de la dernière instruction , donc nous devrons toujours en ajouter une pour calculer le temps d'exécution de la précédente c'est une boucle sans fin .

[Dlzlogic]

Bonjour,
Depuis le début de ce fil, on parle du temps comme d'une notion parfaitement définie et mesurable. Or, le temps a une définition précise (basée sur la durée de l'année 1900).
Par ailleurs, j'ai bien compris qu'il s'agissait d'une question théorique.
Je retiens la réponse : "on ne peut mesurer un phénomène physique sans le modifier."

[invite6486d7bd]

Oui , mais on ne pourra jamais prévoir le temps de la dernière instruction , donc nous devrons toujours en ajouter une pour calculer le temps d'exécution de la précédente c'est une boucle sans fin .

Absolument pas.
D'ailleurs, si j'ai focalisé sur "la dernière instruction", c'était pour montrer que la solution existait à ce niveau, puisque c'était le seul point qui pouvait poser problème.

Tout-à-fait. Car dès que tu ajoutes des instructions pour compléter le calcul, cela consomme à nouveau des ressources, etc. C'est une illustration du fait bien connu en physique: qu'on ne peut mesurer un phénomène physique sans le modifier.
Mais il suffit de s'arrêter lors de la première insertion d'instruction: certes on a modifié le phénomène physique, mais on mesure bien le phénomène ainsi modifié.

Certes, mais ce n'est pas de la physique.
Ce que vous confondez, c'est le calcul, simple addition des durées basées sur le code (qui est fini, mais il faut arriver à le voir), et le temps de traitement physique (le réel) qui est indépendant PHYSIQUEMENT de la valeur fournie.
L'erreur (amusante) est de croire que le programme va faire les choses tout seul...comme un phénomène physique.
Or il y a un intervenant supplémentaire, l'informaticien, et c'est LUI qui contraint le code.
Par exemple, vous pourriez me dire : La tâche est impossible, puisque dans le cas d'une boucle, la durée s'allonge et il faudra ajouter le calcul suplémentaire.
Heureusement, nous avons inventé la multiplication (calcul), qui permet de faire en 1 fois ce que le traitement fait en plusieurs fois.

[invite6486d7bd]

Bonjour,
Depuis le début de ce fil, on parle du temps comme d'une notion parfaitement définie et mesurable. Or, le temps a une définition précise (basée sur la durée de l'année 1900).
Par ailleurs, j'ai bien compris qu'il s'agissait d'une question théorique.
Je retiens la réponse : "on ne peut mesurer un phénomène physique sans le modifier."

Le code n'est pas le phénomène.
Le calcul ne rend pas compte du traitement physique (qui n'est pas le code), mais ce qu'on peut dire du code d'après l'évaluation depuis une table.

[invitee3128aa2]

LeMulet je répète que dans l'algorithme que l'on considère le temps d'exécution diffère pour chaque valeur , et qu'il est donné à plus de cents chiffres significatifs totalement imprévisible pour deux valeurs différents , (c'est un algorithme théorique ).

[invite6486d7bd]

LeMulet je répète que dans l'algorithme que l'on considère le temps d'exécution diffère pour chaque valeur , et qu'il est donné à plus de cents chiffres significatifs totalement imprévisible pour deux valeurs différents , (c'est un algorithme théorique ).

Justement, c'est un algorithme théorique, donc la question des chiffres significatifs n'a pas lieu d'être, sinon comme déjà dit, vous affirmez par là que TOUT calcul basé sur des valeurs mesurées etc est impossible.
La question que vous posez, la question d'algorithmique est alors sans aucune importance, ce serait juste un cas parmi tous les cas que vous supposez impossible.

De plus, si vous me dites que le temps d’exécution diffère à chaque valeur, je pense que vous pouvez encore faire ce programme.
C'est plus compliqué, voilà tout.

[invitee3128aa2]

De plus, si vous me dites que le temps d’exécution diffère à chaque valeur, je pense que vous pouvez encore faire ce programme.
C'est plus compliqué, voilà tout.

Désolé mais sur ce point c'est impossible de donner un temps exacte même avec des mesures exactes je vais vous expliquer , il commence par une instruction quelconque , il obtient le temps de cette instruction par exemple , 1,234567 (bien sûr ce n'est pas vrai) , il ajoute le temps de cette instruction à la variable , on obtient un nouveau temps à ajouter , complètement imprévisible , par exemple 1,478545 , comme je l'ai dit plus haut , même si le temps est le même pour un même type d'instruction et une même valeur il ne l'est plus avec une valeur différente ou un type d'instruction différent , donc il ajoute 1,478545 il obtient un nouveau temps , 1,49601 puis ça recommence sans arrêt le seul moyen de pouvoir arrêter cet boucle c'est de connaitre le temps d'avance .

[inviteeecca5b6]

Ca n'a rien d'impossible mais effectivement, selon la précision que tu souhaites, ça peut être très difficile...

Ceci dit, il existe déjà une tonne de litterature sur le sujet (mesure de la complexité d'un algorithme):
https://en.wikipedia.org/wiki/Analys...-time_analysis

Commence par lire ceci, et ensuite on pourra développer. Le problème étant que pour le moment tu n'en sais pas assez pour mener une reflexion interessante (et je dis pas ça pour être méchant, on a tous commencé à zéro).