Algorithmique 2 : Intro Analyse Amortie

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est utilisée dans l'enseignement d'Algorithmique 2. Vos corrections sont les bienvenues. Mais, merci d'en discuter avant.


Cette page est une petite introduction au coût amorti et à son calcul via la méthode du potentiel.

Présentation

L'idée fondamentale derrière la notion de coût amorti est la suivante:

On peut s'autoriser à faire certaines opérations coûteuses sur une structure de données, si celles-ci n'arrivent pas souvent: autrement dit, le coût élevé de ces opérations est compensé par le fait que la plupart des autres opérations ont un coût faible.

Ainsi, le coût amorti est généralement bien adapté pour raisonner sur le coût d'un ensemble de sous-programmes (typiquement un paquetage).

Définition

Soit un ensemble E d'opérations modifiant une certaine donnée D. Typiquement, E représente une machine à état, et D l'état de la machine. Alternativement, E peut représenter un paquetage et la donnée D être une valeur d'un type abstrait. On appelle ici D_0 la valeur initiale de la donnée D.

Pour un entier n fixé, supposons qu'on sâche calculer le coût total T(n) de l'exécution en séquence de n appels d'opérations quelconques de E à partir de D_0.

Le coût amorti de chaque opération de E est alors défini comme \frac{T(n)}{n}.

Ce qu'il se cache derrière cette définition

  1. Dans la suite de cette introduction T(n) est implicitement le coût dans le pire cas de n appels d'opérations quelconquesn fixé). Dans d'autres exemples, T(n) est le coût moyen d'une séquence de n appels. Dans ce cas, on parlera de "coût moyen amorti" (le terme "coût amorti" étant donc implicitement du "coût dans le pire cas amorti").
  2. Comme précisé en introduction, on veut autoriser certains des "n" appels à être très coûteux (par exemple, de l'ordre de T(n)). Mais ces appels coûteux arrivent peu souvent (par exemple, au plus un nombre constant de fois): leur coût élevé est donc compensé par les autres appels qui sont peu coûteux.
  3. Souvent, on cherche à montrer que T(n) est linéaire (en fonction de n). Dans ce cas, le coût amorti est donc constant. Dans d'autres exemples, on peut avoir T(n) vaut "n\log\,n". Dans ce cas le coût amorti est "\log\,n".
  4. Il ne faut pas confondre "analyse amortie" et "analyse en moyenne". Dans l'analyse en moyenne, on considère que chaque appel d'opération est indépendant: il n'y a pas de notion d'état mémoire. C'est donc bien adapté pour des opérations comme le tri que, dans l'idéal, on applique une fois pour toute sur la donnée à trier. Au contraire, dans l'analyse amortie, il y a un état mémoire (la donnée D): cette analyse prend en compte les histoires possibles de cet état mémoire.

Méthode du potentiel

Notations: À n fixé, on considère une séquence de n appels d'opération de E. Pour i de 1..n, on note op_i l'appel correspondant et D_i l'état de la donnée après l'appel. L'appel op_i transforme donc la donnée D_{i-1} en D_i (D_0 étant la donnée initiale).

Ainsi, si chaque appel op_i a un "coût réel" noté cr_i, le coût T(n) de la séquences de op_i se décompose en

T(n) = \Sigma_{i=1}^n cr_i

Présentation: La méthode de potentiel est une méthode "systématique" pour majorer T(n). L'idée est d'exprimer la "compensation" de coût entre les différents appels par une fonction \Phi qui associe à chaque donnée D un entier naturel. Cette fonction, appelée "potentiel" de la donnée, représente le "coût accumulé" dans la donnée. Le nom "potentiel" doit faire penser à "énergie potentielle": de l'énergie qu'on peut dépenser quand on en a accumulé suffisamment. Toute la difficulté de cette méthode est de choisir le bon \Phi. En effet, une fois \Phi choisi , le reste de la méthode est pratiquement automatique.

Hypothèse sur \Phi: la seule contrainte sur \Phi est d'être à valeur positive ou nulle. \Phi(D_0) n'est pas forcément nul: il représente alors en quelque sorte le potentiel accumulé lors de la phase d'initialisation de la donnée.

Principe: à partir de \Phi, on calcule le coût compensé "cc_i" de chaque appel "op_i" qui prend en compte la modification du potentiel sur les données. Le coût compensé est défini par:

cc_i = cr_i + \Phi(D_i) - \Phi(D_{i-1})

On applique alors le résultat suivant:

T(n) \leq (\Sigma_{i=1}^n cc_i) + \Theta(1)

Si on a bien choisi \Phi, alors les coûts compensés de chaque appel sont du même ordre que le coût amorti recherché.

En pratique, on se contente de calculer un majorant des coûts compensés pour chaque opération de E. Typiquement, on calcule le coût compensé dans le pire cas pour chaque opération. Si on veut montrer que le coût amorti des opérations est constant, on choisit \Phi de façon à ce que leur coût compensé soit lui-même constant.

En conclusion, lors du choix de \Phi, on s'arrange pour que les opérations qui ont un coût réel faible accumulent petit-à-petit du potentiel qu'on dépense dans les opérations qui un coût réel élevé.

Exemple 1 (le plus facile)

On construit une file FIFO (premier entré/premier sorti) à partir de deux piles.

Spécifications des piles

Fichier : IntroAnalyseAmortie/lifo.ads |raw |historique |rafraichir

<include select="" lines="1-23" fromXXX="{{{from}}}" toXXX="{{{to}}}" beforeXXX="{{{before}}}" afterXXX="{{{after}}}" linestartXXX="{{{linestart}}}" linenumsXXX="{{{linenums}}}" src="http://github.com/boulme/algo2/raw/master/IntroAnalyseAmortie/lifo.ads" highlight="ada" style="border: 0px none white"> </include>

On suppose ici que le coût de chaque opération du paquetage Lifo est borné par une constante "C".

Spécifications des files et implémentation des files

Fichier : IntroAnalyseAmortie/fifo.ads |raw |historique |rafraichir

<include select="" linesXXX="{{{lines}}}" fromXXX="{{{from}}}" toXXX="{{{to}}}" beforeXXX="{{{before}}}" afterXXX="{{{after}}}" linestartXXX="{{{linestart}}}" linenumsXXX="{{{linenums}}}" src="http://github.com/boulme/algo2/raw/master/IntroAnalyseAmortie/fifo.ads" highlight="ada" style="border: 0px none white"> </include>

L'idée de l'implémentation derrière la définition du type Queue ci-dessus est la suivante:

Les éléments insérés dans la file Q sont empilés dans Q.Tete et les éléments extraits sont dépilés de Q.Queue. Dans le cas où on essaie d'extraite un élément alors Q.Queue est vide, on commence au prélable par dépiler successivement les éléments de Q.Tete pour les empiler dans Q.Queue. Ceci a pour effet de renverser l'ordre des éléments: le premier élément à avoir été inséré dans Q.Tete est bien le premier qu'on va dépiler dans Q.Queue.

Exercice: Écrire cette implémentation.

Analyse amortie

Exercice: Montrer que toutes les opérations de la file sont à coût amorti constant.

Exemple 2 (plus dur)

On implémente maintenant le paquetage Lifo de l'exemple précédent en codant chaque pile comme un tableau avec redimensionnement dynamique.

Implémentation des piles

Type des piles (dans lifo.ads):

Fichier : IntroAnalyseAmortie/lifo.ads |raw |historique |rafraichir

<include select="" lines="23-42" fromXXX="{{{from}}}" toXXX="{{{to}}}" beforeXXX="{{{before}}}" afterXXX="{{{after}}}" linestartXXX="{{{linestart}}}" linenumsXXX="{{{linenums}}}" src="http://github.com/boulme/algo2/raw/master/IntroAnalyseAmortie/lifo.ads" highlight="ada" style="border: 0px none white"> </include>

Ici, lors de l'ajout ou la suppression d'un élément, on doit redimensionner le tableau de manière à préserver l'invariant.

Exercice: Écrire cette implémentation.

Analyse amortie

Exercice 1: Supposons que dans Destruct, au lieu de redimensionner quand S.Taille = S.Pile'Length/4, on redimensionne lorsque S.Taille = S.Pile'Length/2 (avec la dimension S.Pile'Length/2). Montrer que le coût amorti n'est pas constant.

Exercice 2: En supposant qu'on respecte bien le redimensionnement dans Destruct lorsque S.Taille = S.Pile'Length/4, montrer que le coût amorti est constant.

Conclusion sur ces deux exemples

Exercice 1: vérification théorique

Est-il correct de "composer" les coûts amortis, comme on l'a fait implicitement ici ? En effet, dans l'analyse amortie des files, on a supposé le coût des opérations des piles constant, ce qui est vrai uniquement de leur coût amorti.

Exercice 2: vérification expérimentale

Les fichiers fournis ici sont disponibles dans le répertoire IntroAnalyseAmortie/ de l'archive Git publique des enseignants. Le fichier IntroAnalyseAmortie/testfifo.adb crée une séquence de N appels aléatoires d'opérations "Insert" et "Destruct" sur une file.

Mesurer les temps d'exécution de "testfifo" (via la commande Unix "time" par exemple) pour diverses valeurs de la constante "N":

  • N=1000000
  • N=10000000
  • N=100000000

L'analyse amortie ci-dessus prédit que le temps d'exécution doit croître de façon linéaire (donc on devrait observer une augmentation d'un facteur 10 sur chaque cas précédent).

Références

  • page wikipedia sur le sujet.
  • page wikipedia de Tarjan coinventeur du concept et qui l'a mis en oeuvre dans de nombreuses structures de données.
  • T. Cormen, C.E. Leiserson, R. Rivest, C. Stein : "Introduction to algorithms", MIT Press, 2nd edition, 2001.
  • Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998. Cet ouvrage contient de nombreux exemples dans le contexte de structures de données persistentes (e.g. non mutables). Il est tiré de la thèse de l'auteur qui est en ligne.