“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 159 — #169
i
i
i
i
i
i
i
i
3.7 Les besoins non déclaratifs
159
tous les problèmes NP en temps polynomial. Beaucoup de chercheurs en informatique
ont essayé pendant des décennies de trouver une solution en temps polynomial aux
problèmes NP-complets, et aucun n’a réussi. La plupart des chercheurs soupçonne
donc que les problèmes NP-complets ne peuvent pas être résolus en temps polynomial.
Nous ne parlerons plus des problèmes qui ont besoin d’une grande puissance de
calcul. Comme notre but est d’expliquer la programmation, nous nous limiterons aux
problèmes solubles en pratique.
L’optimisation
Dans certains cas, la performance d’un problème peut être insuffisante même si le
problème est théoriquement soluble en pratique. Il faut alors réécrire le programme
pour améliorer sa performance. Réécrire un programme pour améliorer une de ses
caractéristiques s’appelle l’optimisation, mais le programme n’est jamais optimal
dans un sens mathématique. Généralement, on peut améliorer le programme jusqu’à
un certain point, au-delà duquel il devient rapidement de plus en plus compliqué pour
des améliorations de plus en plus petites. L’optimisation ne doit donc pas être faite
sans nécessité. L’optimisation prématurée est la source de tous les maux.
14 Ce principe
ne libère pas le programmeur de la responsabilité de faire une bonne conception du
système ; il s’agit plutôt de ne pas perdre son temps à optimiser à petite échelle.
L’optimisation a un bon et un mauvais côté. Le bon côté est que le temps d’exécution
de la plupart des applications est largement déterminé par une toute petite partie
du texte du programme. L’optimisation de la performance, si nécessaire, peut donc
presque toujours être faite en réécrivant cette petite partie (parfois quelques lignes
suffisent). Le mauvais côté est qu’il n’est pas évident, même pour des programmeurs
expérimentés, de savoir a priori où se trouve cette partie. La partie peut être identifiée
en exécutant l’application, mais seulement s’il y a un problème de performance. S’il
n’y a pas de problème, aucune optimisation de la performance ne doit être faite. La
meilleure technique pour identifier la partie est de profiler l’application : instrumenter
l’application pour mesurer ses caractéristiques à l’exécution.
3.7 LES BESOINS NON DÉCLARATIFS
La programmation déclarative, à cause de sa vue purement fonctionnelle de la programmation, est un peu détachée du monde réel, dans lequel les entités ont de la mémoire
(l’état) et peuvent évoluer de façon indépendante et proactive (la concurrence). Pour
connecter un programme déclaratif au monde réel, il faut quelques opérations nondéclaratives. Cette section présente deux classes de ces opérations : l’entrée/sortie
14. Une phrase célèbre de C.A.R. Hoare : « premature optimization is the root of all evil ».
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.7 Les besoins non déclaratifs
159
tous les problèmes NP en temps polynomial. Beaucoup de chercheurs en informatique
ont essayé pendant des décennies de trouver une solution en temps polynomial aux
problèmes NP-complets, et aucun n’a réussi. La plupart des chercheurs soupçonne
donc que les problèmes NP-complets ne peuvent pas être résolus en temps polynomial.
Nous ne parlerons plus des problèmes qui ont besoin d’une grande puissance de
calcul. Comme notre but est d’expliquer la programmation, nous nous limiterons aux
problèmes solubles en pratique.
L’optimisation
Dans certains cas, la performance d’un problème peut être insuffisante même si le
problème est théoriquement soluble en pratique. Il faut alors réécrire le programme
pour améliorer sa performance. Réécrire un programme pour améliorer une de ses
caractéristiques s’appelle l’optimisation, mais le programme n’est jamais optimal
dans un sens mathématique. Généralement, on peut améliorer le programme jusqu’à
un certain point, au-delà duquel il devient rapidement de plus en plus compliqué pour
des améliorations de plus en plus petites. L’optimisation ne doit donc pas être faite
sans nécessité. L’optimisation prématurée est la source de tous les maux.
14 Ce principe
ne libère pas le programmeur de la responsabilité de faire une bonne conception du
système ; il s’agit plutôt de ne pas perdre son temps à optimiser à petite échelle.
L’optimisation a un bon et un mauvais côté. Le bon côté est que le temps d’exécution
de la plupart des applications est largement déterminé par une toute petite partie
du texte du programme. L’optimisation de la performance, si nécessaire, peut donc
presque toujours être faite en réécrivant cette petite partie (parfois quelques lignes
suffisent). Le mauvais côté est qu’il n’est pas évident, même pour des programmeurs
expérimentés, de savoir a priori où se trouve cette partie. La partie peut être identifiée
en exécutant l’application, mais seulement s’il y a un problème de performance. S’il
n’y a pas de problème, aucune optimisation de la performance ne doit être faite. La
meilleure technique pour identifier la partie est de profiler l’application : instrumenter
l’application pour mesurer ses caractéristiques à l’exécution.
3.7 LES BESOINS NON DÉCLARATIFS
La programmation déclarative, à cause de sa vue purement fonctionnelle de la programmation, est un peu détachée du monde réel, dans lequel les entités ont de la mémoire
(l’état) et peuvent évoluer de façon indépendante et proactive (la concurrence). Pour
connecter un programme déclaratif au monde réel, il faut quelques opérations nondéclaratives. Cette section présente deux classes de ces opérations : l’entrée/sortie
14. Une phrase célèbre de C.A.R. Hoare : « premature optimization is the root of all evil ».
© Dunod – La photocopie non autorisée est un délit