“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 149 — #159
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
149
Calculer le temps d’exécution
Nous utilisons le langage noyau comme un guide. Chaque instruction noyau a un
temps d’exécution bien défini, qui peut être une fonction de la taille de ses arguments.
Supposons un programme qui contient les p fonctions F1, . . . , Fp. Nous voudrions
calculer les p fonctions T F1 , . . . , T Fp . On peut le faire en trois étapes :
1. Traduisez le programme en langage noyau.
2. Utilisez les temps d’exécution des instructions noyau pour faire un ensemble
d’équations qui contient T F1 , . . . , T Fp . Nous appelons ces équations des équations de récurrence parce qu’elles définissent le résultat pour n en utilisant les
résultats pour des valeurs plus petites que n.
3. Résolvez les équations de récurrence pour T F1 , . . . , T Fp .
Le tableau 3.3 donne le temps d’exécution T (s) pour chaque instruction noyau s.
Dans ce tableau, s est un entier et les arguments y i = E(y i ) avec 1 i n, pour
l’environnement approprié E. Chaque instance de k est une autre constante réelle
et positive. La fonction I x ({y 1 , . . . , y n }) renvoie le sous-ensemble des arguments
d’une procédure qui est utilisé comme entrées.
8 La fonction size x ({y 1 , . . . , y k }) est
la « taille » des entrées pour la procédure x. Nous avons la liberté de définir la taille
comme nous le voulons ; si elle est mal définie, les équations de récurrence n’auront
pas de solution. Pour les instructions x=y et x=v il y a un cas rare pour lequel
elles prennent plus de temps qu’un temps constant, à savoir quand les deux arguments
sont liés à des valeurs partielles de grande taille. Dans ce cas, le temps est proportionnel
à la taille de la partie commune des deux valeurs partielles.
Un exemple : la fonction Append
Voici un exemple simple pour illustrer la méthode. Prenons la fonction Append :
fun {Append Xs Ys}
case Xs of nil then Ys
[] X|Xr then X|{Append Xr Ys} end
end
Elle a la traduction suivante en langage noyau (légèrement simplifiée) :
proc {Append Xs Ys ?Zs}
case Xs of nil then Zs=Ys
[] X|Xr then Zr in Zs=X|Zr {Append Xr Ys Zr} end
end
8. Cela peut changer d’appel en appel, par exemple quand la même procédure est utilisée pour accomplir
des tâches différentes lors des appels différents.
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
149
Calculer le temps d’exécution
Nous utilisons le langage noyau comme un guide. Chaque instruction noyau a un
temps d’exécution bien défini, qui peut être une fonction de la taille de ses arguments.
Supposons un programme qui contient les p fonctions F1, . . . , Fp. Nous voudrions
calculer les p fonctions T F1 , . . . , T Fp . On peut le faire en trois étapes :
1. Traduisez le programme en langage noyau.
2. Utilisez les temps d’exécution des instructions noyau pour faire un ensemble
d’équations qui contient T F1 , . . . , T Fp . Nous appelons ces équations des équations de récurrence parce qu’elles définissent le résultat pour n en utilisant les
résultats pour des valeurs plus petites que n.
3. Résolvez les équations de récurrence pour T F1 , . . . , T Fp .
Le tableau 3.3 donne le temps d’exécution T (s) pour chaque instruction noyau s.
Dans ce tableau, s est un entier et les arguments y i = E(y i ) avec 1 i n, pour
l’environnement approprié E. Chaque instance de k est une autre constante réelle
et positive. La fonction I x ({y 1 , . . . , y n }) renvoie le sous-ensemble des arguments
d’une procédure qui est utilisé comme entrées.
8 La fonction size x ({y 1 , . . . , y k }) est
la « taille » des entrées pour la procédure x. Nous avons la liberté de définir la taille
comme nous le voulons ; si elle est mal définie, les équations de récurrence n’auront
pas de solution. Pour les instructions x=y et x=v il y a un cas rare pour lequel
elles prennent plus de temps qu’un temps constant, à savoir quand les deux arguments
sont liés à des valeurs partielles de grande taille. Dans ce cas, le temps est proportionnel
à la taille de la partie commune des deux valeurs partielles.
Un exemple : la fonction Append
Voici un exemple simple pour illustrer la méthode. Prenons la fonction Append :
fun {Append Xs Ys}
case Xs of nil then Ys
[] X|Xr then X|{Append Xr Ys} end
end
Elle a la traduction suivante en langage noyau (légèrement simplifiée) :
proc {Append Xs Ys ?Zs}
case Xs of nil then Zs=Ys
[] X|Xr then Zr in Zs=X|Zr {Append Xr Ys Zr} end
end
8. Cela peut changer d’appel en appel, par exemple quand la même procédure est utilisée pour accomplir
des tâches différentes lors des appels différents.
© Dunod – La photocopie non autorisée est un délit