{ "cells": [ { "cell_type": "markdown", "source": [ "# Complexité amortie\n", "\n", "# La méthode du potentiel\n", "\n", "Marc Lorenzi\n", "\n", "2 juillet 2019" ], "metadata": {} }, { "cell_type": "code", "source": [ "import matplotlib.pyplot as plt\n", "import random\n", "import math" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "plt.rcParams['figure.figsize'] = (12, 6)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "On se place dans la situation où un algorithme $\\mathcal A$ prend une structure de données $s$ ayant la \"valeur\" $x$ en paramètre et modifie la valeur cette structure. Les objets qui nous intéressent sont des listes, des arbres, des graphes, des entiers, etc. La __complexité__ de l'algorithme lorsqu'il est exécuté sur la structure est le nombre d'opérations élémentaires effectuées par l'algorithme. Bien évidemment, il s'agit avant toute chose de s'entendre sur ce que l'on appelle \"opération élémentaire\".\n", "\n", "Notons $C_{\\mathcal A}(x)$ cette complexité. La quantité $C_{\\mathcal A}(x)$ est souvent difficile à calculer exactement. On définit à partir de celle-ci un certain nombre d'autres quantités, indépendantes de $x$, et parfois plus faciles à évaluer. Si nous appelons $\\mathcal E$ l'ensemble des valeurs $x$ qui nous intéressent, on peut considérer\n", "\n", "- La complexité en pire cas de l'algorithme $\\mathcal A$ :\n", "\n", "$$C'_{\\mathcal A}=\\max_{x\\in\\mathcal E}C_{\\mathcal A}(x)$$\n", "\n", "- La complexité en meilleur cas de l'algorithme $\\mathcal A$ :\n", "\n", "$$C''_{\\mathcal A}=\\min_{x\\in\\mathcal E}C_{\\mathcal A}(x)$$\n", "\n", "- La complexité en moyenne de l'algorithme $\\mathcal A$. Pour cela on commence par mettre une probabilité sur l'ensemble $\\mathcal E$. La fonction $C_{\\mathcal A}:\\mathcal E\\to\\mathbb R$ est alors une variable aléatoire et la complexité en moyenne de l'algorithme est son espérance :\n", "\n", "$$C'''_{\\mathcal A}=E(C_{\\mathcal A})$$\n", "\n", "Par exemple, si $\\mathcal E$ est fini de cardinal $n$ et muni de la probabilité uniforme, alors\n", "\n", "$$C'''_{\\mathcal A}=\\frac 1 n\\sum_{x\\in\\mathcal E}C_{\\mathcal A}(x)$$\n", "\n", "Dans ce notebook, nous allons parler d'un quatrième type de complexité : la __complexité amortie__." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## 1. La complexité amortie" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 1.1 Introduction" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Histoire de ne pas parler dans le vide, voici quelques exemples d'algorithmes pour lesquels une analyse amortie aurait un sens.\n", "\n", "- On ajoute un objet à la fin d'une liste.\n", "- On retire un objet à la fin d'une liste.\n", "- On ajoute un sommet à un graphe, à un arbre binaire, etc.\n", "- On incrémente un compteur binaire.\n", "- Ayant ordonné totalement l'ensemble $\\mathcal E$, on passe d'un élément de $\\mathcal E$ à l'élément suivant.\n", "\n", "Ce qui nous intéresse, c'est le \"temps\" mis par une __succession__ de $n$ applications de l'algorithme sur la structure de données. Par exemple, on ajoute $n$ objets à la fin d'une liste, on incrémente $n$ fois un compteur binaire, on énumère les parties d'un ensemble. Bien évidemment, la complexité de cette succession de calculs est inférieure à\n", "\n", "$$nC'_{\\mathcal A}$$\n", "\n", "où $C'_{\\mathcal A}$ est le complexité en pire cas de l'algorithme $\\mathcal A$. Dans les exemples qui vont suivre, il s'avère que ce majorant est pessimiste : une application particulière de l'algorithme peut être coûteuse, mais si beaucoup d'autres applications ne le sont pas alors la complexité globale de l'algorithme sera faible." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 1.2 Considérations énergétiques" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Calculer un objet $x'$ à partir d'un objet $x$ demande une certaine quantité de travail. Vous savez tous cela si vous avez déjà résolu une équation de degré 5 ou calculé une intégrale triple :-). Notons $\\Delta c=c(x)$ le travail fourni, mesuré en \"opérations élémentaires\" : chaque opération élémentaire vaut un quantum de travail. Pour certains calculs nous pouvons interpréter une partie du travail $\\Delta c$ comme une différence de potentiel :\n", "\n", "$$\\Delta c = \\Delta c_a - \\Delta \\Phi$$\n", "\n", "où $\\Delta\\Phi = \\Phi(x')-\\Phi(x)$ est la différence du potentiel $\\Phi$ entre les objets $x$ et $x'$, et $\\Delta c_a=c_a(x)$ est le \"reliquat\" de travail. Que vaut ce potentiel $\\Phi$ ? Cela dépend évidemment de l'algorithme $\\mathcal A$ et, comme en physique (en fait beaucoup plus) le choix de $\\Phi$ contient une dose d'arbitraire. Comme en physique, le potentiel peut travailler contre nous (on monte au sommet de la montagne) ou pour nous (on redescend à ski). Plus nous augmentons notre potentiel, plus nous accumulons de l'énergie . Nous pourrons ensuite utiliser cette énergie en notre faveur.\n", "\n", "L'idée de __l'analyse amortie__ est de trouver un potentiel tel que le reliquat de travail $c_a$ soit faible : une fois trouvée la fonction magique $\\Phi$ et calculée la quantité $c_a$ on en déduit $c$ !\n", "\n", "__Définition__ : $c_a(x)$ est la __complexité amortie__ de l'algorithme $\\mathcal A$ pour le calcul de $x'$ à partir de $x$.\n", "\n", "Les exemples qui suivent éclaireront (un peu) tout cela." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## 2. Compteurs binaires" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 2.1 C'est quoi ?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Commençons par un exemple simple, celui des compteurs binaires. \n", "\n", "Nous appelons __compteur binaire__ de taille $n$ une liste $s$ de longueur $n$ dont les éléments sont des 0 et des 1, représentant un entier en base 2. Pour reprendre les cotations de l'introduction,\n", "\n", "- La structure de données est la liste $s$.\n", "- Sa valeur $x$ est l'entier représenté par $s$.\n", "- L'algorithme $\\mathcal A$ incrémente $s$, ou plutôt sa valeur, de 1.\n", "\n", "Dans la discussion qui va suivre nous identifions la liste $s$ à cet entier. Les éléments de $s$ s'appelleront donc sans surprise ses __bits__. Lorsqu'on ajoute 1 à l'entier (représenté par) $s$, certains 0 deviennent des 1, certains 1 deviennent des 0. Le nombre de changements de bits (que nous appellerons des __swaps__) est la complexité de l'opération d'incrémentation." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici la fonction qui modifie le $k$-ième bit de $s$ :" ], "metadata": {} }, { "cell_type": "code", "source": [ "def swap(s, k):\n", " global cmpt\n", " s[k] = 1 - s[k]\n", " cmpt.incr()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Remarquez la variable `cmpt`: ce sera dans quelques secondes un \"compteur de swaps\"." ], "metadata": {} }, { "cell_type": "code", "source": [ "class Compteur:\n", " \n", " def __init__(self): self.val = 0\n", " def incr(self): self.val += 1\n", " def reset(self): self.val = 0" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "cmpt = Compteur()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "s = [1, 0, 1, 1, 0]\n", "swap(s, 2)\n", "print(s)\n", "print(cmpt.val)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "### 2.3 Incrémenter un compteur binaire" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Quel est le successeur de l'entier 10110111 ? C'est 10111000. Pour l'obtenir on part de la fin de $s$. Tant qu'on rencontre un 1, on le met à 0. Puis on met à 1 le premier 0 rencontré. La fonction d'incrémentation est donc évidente." ], "metadata": {} }, { "cell_type": "code", "source": [ "def incr(s):\n", " n = len(s)\n", " k = n - 1\n", " while k >= 0 and s[k] == 1: \n", " swap(s, k)\n", " k = k - 1\n", " if k == -1: return False\n", " else:\n", " swap(s, k)\n", " return s" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "incr([1, 0, 1, 1, 0, 1, 1, 1])" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "La liste qui ne contient que des 1 est un peu particulière, puisqu'elle n'a pas de successeur." ], "metadata": {} }, { "cell_type": "code", "source": [ "incr([1, 1, 1, 1])" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "### 2.4 Compter" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "La fonction `count` incrément un compteur binaire initialement égal à $[0,\\ldots,0]$. Elle termine lorsque le compteur est égal à $[1,\\ldots,1]$, ou, plutôt, lorsque la tentative d'incrémenter $[1,\\ldots,1]$ échoue." ], "metadata": {} }, { "cell_type": "code", "source": [ "def count(n, prt=False):\n", " s = n * [0]\n", " while True:\n", " b = incr(s)\n", " if b == False: break\n", " if prt: print(s)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "count(4, prt=True)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "cmpt.reset()\n", "count(10)\n", "print(cmpt.val)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Une liste de 10 bits peut représenter tous les entiers entre 0 et $2^{10}-1=1023$.\n", "\n", "Pour compter de 0 à $2^{10}-1$, nous faisons $2^{10}$ incrémentations (dont la dernière échoue). Pourtant, nous n'avons effectué qu'environ $2^{11}$ swaps, alors que certaines incrémentations d'entiers peuvent demander jusqu'à 10 swaps !\n", "\n", "Montrons tout d'abord \"à la main\" que ceci reste valable en général. Nous le reprouverons ensuite de façon beaucoup plus rusée." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 2.5 Nombre total de swaps" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Combien de swaps effectue-t-on pour incrémenter un compteur binaire ? Cela dépend de la position du premier 0 en partant de la fin de la liste.\n", "\n", "- Si la liste termine par un 0, il y a un seul swap. Et il y a $2^{n-1}$ telles listes.\n", "- Si la liste termine par 01, il y a 2 swaps. Et il y a $2^{n-2}$ telles listes.\n", "- Si la liste termine par 011, il y a 3 swaps. Et il y a $2^{n-3}$ telles listes.\n", "...\n", "- Si la liste est 011...1, il y a $n$ swaps. Et il y a une seule telle liste.\n", "- La liste 11...1 est un peu à part. On y effectue $n$ swaps. Et la fonction d'incrémentation renvoie `False`.\n", "\n", "Au total, l'itération de la fonction d'incrémentation effectue un nombre de swaps égal à\n", "\n", "$$C_n= \\sum_{k=1}^n k2^{n-k}+n$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Proposition__ : $C_n=2^{n+1}-2$.\n", "\n", "__Démonstration__ : Posons pour $x\\in]0,1[$, \n", "\n", "$$f(x)=\\sum_{k=0}^nx^k$$\n", "\n", "On a \n", "\n", "$$C_n=2^{n-1}f'\\left(\\frac 1 2\\right)+n$$\n", "\n", "Or, \n", "\n", "$$f(x)=\\frac{1-x^{n+1}}{1-x}$$\n", "\n", "On en déduit que\n", "\n", "$$f'(x)=\\frac{-(1-x)(n+1)x^n+(1-x^{n+1})}{(1-x)^2}=\\frac{nx^{n+1}-(n+1)x^n+1}{(1-x)^2}$$\n", "\n", "d'où\n", "\n", "$$f'\\left(\\frac 1 2\\right)=4\\left(\\frac n {2^{n+1}}-\\frac{n+1}{2^n}+1\\right)=4-\\frac{n+2}{2^{n-1}}$$\n", "\n", "et\n", "\n", "$$C_n=2^{n+1}-2$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 2.6 Complexité amortie" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Venons en au vif du sujet, la __méthode du potentiel__. Nous allons retrouver le résultat précédent par une toute autre méthode. Pour tout compteur $s$ de $n$ bits autre que la liste qui ne contient que des 1, soit $s'$ la liste obtenue par incrémentation de $s$. Notons $c(s)$ la complexité de cette opération (nombre de swaps). \n", "\n", "Notons $\\Phi(s)$ le nombre de bits de $s$ égaux à 1. Enfin, appelons __complexité amortie__ de l'algorithme d'incrémentation sur la liste $s$ la quantité\n", "\n", "$$c_a(s)=c(s)+\\Phi(s')-\\Phi(s)$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Partons de la liste $s_0=[0,\\ldots,0]$ et effectuons $q\\ge 1$ incrémentations pour obtenir successivement les listes $s_1,\\ldots,s_q$. On a\n", "\n", "$$\\sum_{k=0}^{q-1}c_a(s_k)=\\sum_{k=0}^{q-1}(c(s_k)+\\Phi(s_{k+1})-\\Phi(s_k))$$\n", "\n", "Un téléscopage se produit sur les différences de potentiels, et on obtient\n", "\n", "$$\\sum_{k=0}^{q-1}c_a(s_k)=\\Phi(s_q)-\\Phi(s_0)+\\sum_{k=0}^{q-1}c(s_k)$$\n", "\n", "d'où\n", "\n", "$$\\sum_{k=0}^{q-1}c(s_k)=-\\Phi(s_q)+\\Phi(s_0)+\\sum_{k=0}^{q-1}c_a(s_k)$$\n", "\n", "La complexité réelle est donc la somme des complexités amorties, à laquelle on soustrait la différence globale de potentiel." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Que vaut ici la complexité amortie $c_a(s)$ ?\n", "\n", "Supposons que $c(s)=k$. Cela veut dire que pour passer de $s$ à $s'$, on a effectué $k$ swaps. Plus précisément, $k-1$ uns sont devenus des zéros, et un zéro est devenu un 1. La liste $s'$ a donc $k-2$ uns de moins que la liste $s$. Ainsi \n", "\n", "$$\\Phi(s')=\\Phi(s)-(k-2)$$\n", "\n", "De là,\n", "\n", "$$c_a(s)=c(s)+\\Phi(s')-\\Phi(s)=k-(k-2)=2$$\n", "\n", "La complexité amortie est constante, égale à 2. Ainsi, en reprenant les calculs faits plus haut,\n", "\n", "$$\\sum_{k=0}^{q-1}c(s_k)=-\\Phi(s_q)+\\Phi(s_0)+2q$$\n", "\n", "Comme $s_0=[0,\\ldots, 0]$, on a $\\Phi(s_0)= 0$. Et comme $\\Phi(s_q)\\ge 0$, on obtient \n", "\n", "$$\\sum_{k=0}^{q-1}c(s_k)\\le 2q$$\n", "\n", "Pour une itération sur toutes les valeurs du compteur binaire, $q=2^n$, et donc\n", "\n", "$$\\sum_{k=0}^{2^n-1}c(s_k)\\le 2^{n+1}$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Remarque__ : Si nous prenons $q=2^n-1$, nous avons $s_q=[1,\\ldots,1]$ donc $\\Phi(s_q)=n$. Ainsi,\n", "\n", "$$\\sum_{k=0}^{q-1}c(s_k)=-\\Phi(s_q)+\\Phi(s_0)+2q=-n+0+2(2^n-1)=2^n-n-2$$\n", "\n", "Nous retrouvons le résultat obtenu au paragraphe précédent (rappelons-nous qu'il faut ajouter $n$ à cela pour tenir compte du calcul (qui échoue) du successeur de $[1,\\ldots,1]$)." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 2.7 Commentaires" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Traçons le graphe des valeurs du potentiel et aussi celui des différences de potentiel !" ], "metadata": {} }, { "cell_type": "code", "source": [ "def tracer_potentiel(n):\n", " s = n * [0]\n", " ps = []\n", " while True:\n", " ps.append(sum(s))\n", " b = incr(s)\n", " if b == False: break\n", " qs = [ps[k+1]-ps[k] for k in range(len(ps)-1)]\n", " plt.plot(qs, 'r')\n", " plt.plot(ps, 'k')\n", " plt.grid()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici le tracé du potentiel au cours des incrémentations. En noir les potentiels, et en rouge les différences de potentiel." ], "metadata": {} }, { "cell_type": "code", "source": [ "tracer_potentiel(8)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Lorsque la liste $s$ est incrémentée de $[0,\\ldots,0]$ à $[1,\\ldots,1]$ le potentiel fluctue assez irrégulièrement de 0 à $n$. Quelles sont les incrémentations qui augmentent le potentiel ? Rappelons-nous que si $c(s)=k$ alors $\\Delta \\Phi=-(k-2)$. Ce sont donc les listes telles que $k=0$ (la liste $[0,\\ldots,0]$) ou $k=1$ (les listes non nulles qui finissent par $0$), c'est à dire la moitié des listes. Lorsqu'on incrémente ces listes, l'augmentation du potentiel fournit en quelque sorte une réserve d'énergie dans laquelle l'algorithme puisera lorsqu'une incrémentation coûteuse surviendra.\n", "\n", "Alors pourquoi la complexité amortie est-elle faible ? Parce que la réserve d'énergie stockée dans le potentiel ne génère jamais de dettes importantes ! Regardez par exemple, dans le graphique ci-dessus, le grand pic au milieu : il correspond à $s=[0,1,\\ldots,1]$. L'incrémentation de $s$ coûte 8 unités d'énergie. À ce moment là le potentiel est à 7. La dette d'énergie après incrémentation n'est donc que de 1. En rajoutant à cela la complexité amortie, qui vaut 2, on se retrouve avec un bénéfice de 1 :-)." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## 3. Files d'attente" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 3.1 C'est quoi ?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Une __file d'attente__ est une structure de données dynamique permettant deux opérations :\n", "\n", "- `push`, qui permet d'ajouter un objet $x$ en __queue__ de la file.\n", "- `pop`, qui permet de retirer l'objet en __tête__ de la file.\n", "\n", "Une simple liste Python semble faire l'affaire. Il suffit par exemple d'ajouter des objets à la fin de la liste et de retirer des objets au début de la liste. Quelles sont les complexités de ces opérations ?\n", "\n", "- La bonne nouvelle est que l'ajout d'un objet à la fin d'une liste Python a une complexité amortie en $O(1)$. Pour ajouter $x$ à la fin de la liste $s$, on appelle la méthode `append` : `s.append(x)`. Dans la discussion qui suit nous ferons comme si la complexité en question était toujours $O(1)$.\n", "- La mauvaise nouvelle est que retirer le premier élément d'une liste Python a une complexité en $O(n)$ où $n$ est la longueur de la liste. Pour retirer le premier élément de $s$ il faut faire quelque chose du genre `s = s[1:]`, qui entraîne une recopie des éléments de $s$.\n", "\n", "__Remarque__ : Pour comprendre pourquoi le début et la fin d'une liste Python ne sont pas équivalents, ils faut comprendre comment les listes sont implémentées de facon interne. Nous reviendrons sur ce sujet et sur la complexité de `append` dans la dernière section du notebook. Dans cette section et la suivante, nous ferons comme si la complexité de `append` était effectivement $O(1)$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 3.2 Implémentation" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Il y a différentes façons d'écrire une structure de file d'attente efficace en Python. Nous choisirons la suivante (ce n'est pas celle adoptée par les concepteurs du langage, qui utilisent une \"liste doublement chaînée\"). Un objet de notre classe `File` possède deux champs\n", "\n", "- Un champ $f$ (comme \"front\") qui est une liste. Cette liste contiendra les éléments \"en tête de la file\", le dernier élément de $f$ étant le premier de la file d'attente.\n", "- Un champ $r$ (comme \"rear\") qui est aussi une liste. Cette liste contiendra les éléments \"en queue de la file\", mais rangés à l'envers par rapport à ceux du champ $f$ : le dernier élément de $r$ sera le dernier de la file d'attente.\n", "\n", "Par exemple, si $s$ est la file $$, où $a$ est le denier élément et $e$ est le premier, on aura par exemple $s.f=[d,e]$ et $s.r=[c,b,a]$, ou peut-être $s.f=[b,c,d,e]$ et $s.r=[a]$, etc. \n", "\n", "On rajoute un troisième champ `counter` qui comptera les opérations élémentaires. Nous décidons que ces opérations élémentaires sont :\n", "\n", "- Les appels à la méthode `append` (ajouter un élément) sur des listes.\n", "- Les appels à la méthode `pop` (enlever un élément) sur des listes.\n", "\n", "Chaque appel à ces méthodes incrémentera un compteur de 1.\n", "\n", "Voici un premier jet de la classe `File`. La méthode `reset_counter` remet le compteur à 0." ], "metadata": {} }, { "cell_type": "code", "source": [ "class File:\n", " \n", " def __init__(self):\n", " self.f = []\n", " self.r = []\n", " self.counter = 0\n", " \n", " def reset_counter(self):\n", " self.counter = 0" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Pour ajouter un objet à une file d'attente, on l'ajoute en fin du champ $r$. Cette opération s'effectue en complexité $O(1)$ (voir remarque un peu plus haut !)." ], "metadata": {} }, { "cell_type": "code", "source": [ "def ajouter(s, x):\n", " s.r.append(x)\n", " s.counter += 1" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "s = File()\n", "ajouter(s, 123)\n", "ajouter(s, 456)\n", "ajouter(s, 789)\n", "print(s.f, s.r, s.counter)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Pour supprimer l'objet en tête de la file, on supprime le dernier élément du champ $f$. Complexité en $O(1)$. Euh, oui, mais non ! Que faire si $s.f$ est vide ? Dans ce cas, on renverse $s.r$ puis on le recopie dans $s.f$. Et on efface $s.r$. C'est évidemment là que le bât blesse, car renverser une liste est une opération coûteuse, de complexité $O(n)$ où $n$ est la longueur de la liste à renverser." ], "metadata": {} }, { "cell_type": "code", "source": [ "def supprimer(s):\n", " if s.f == []:\n", " s.r.reverse()\n", " s.f = s.r[:]\n", " s.r = []\n", " s.counter += len(s.f)\n", " x = s.f.pop()\n", " s.counter += 1\n", " return x" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "supprimer(s)\n", "print(s.f, s.r, s.counter)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Si vous voulez une justification du fait que l'on ajoute `len(s.f)` au compteur, rappelez-vous que nos opérations élémentaires sont `append` et `pop`. Voici une fonction `renverser` qui fait exactement $n$ appels à `append` pour renverser une liste de longueur $n$. " ], "metadata": {} }, { "cell_type": "code", "source": [ "def renverser(s):\n", " s1 = []\n", " n = len(s)\n", " for k in range(n - 1, -1, -1):\n", " s1.append(s[k])\n", " return s1" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "renverser([1, 2, 3, 4, 5])" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Pour faire plus propre, réécrivons la classe `File`, avec ses deux méthodes `push` et `pop`. Profitons en pour rajouter un champ `maxlen` qui contient la longeur maximale (somme des longeurs de $s.f$ et $s.r$) atteinte par la file $s$. Chaque appel à `push` met éventuellement à jour le champ `maxlen`. Un appel à `pop` ne peut que diminuer la longueur, bien entendu. " ], "metadata": {} }, { "cell_type": "code", "source": [ "class File:\n", " \n", " def __init__(self):\n", " self.f = []\n", " self.r = []\n", " self.counter = 0\n", " self.maxlen = 0\n", " \n", " def reset_counter(self):\n", " self.counter = 0\n", " \n", " def is_empty(self):\n", " return self.r == [] and self.f == []\n", " \n", " def push(self, x):\n", " self.r.append(x)\n", " self.counter += 1\n", " l = len(self.f) + len(self.r)\n", " if l > self.maxlen: self.maxlen = l\n", " \n", " def pop(self):\n", " if self.f == []:\n", " self.r.reverse()\n", " self.f = self.r\n", " self.counter += len(self.f)\n", " self.r = []\n", " x = self.f.pop()\n", " self.counter += 1\n", " return x" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "### 3.3 Tests" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Testons tout cela. Faisons $n$ opérations d'insertion et de suppression en partant d'une file vide. À chaque itération on choisit aléatoirement une insertion ou une suppression. On ne supprime évidemment que si la file n'est pas vide !" ], "metadata": {} }, { "cell_type": "code", "source": [ "def test_file(n):\n", " f = File()\n", " for k in range(n):\n", " if random.randint(0, 1) == 0 and not f.is_empty():\n", " x = f.pop()\n", " else:\n", " f.push(random.randint(0, 10))\n", " return f.counter, f.maxlen" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "print(test_file(100000))" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Sur l'exemple ci-dessus, on a fait $n=100000$ opérations. La file a eu une longueur maximale de quelques centaines. Si vous réévaluez la cellule ci-dessus, la longueur maximale de la file varie fortement. En revanche, le nombre d'opérations élémentaires reste à peu près constant, égal à environ $\\frac 3 2 n$.\n", "\n", "Comme de mauvais esprits pourraient penser que cela est dû à des appels à `random`, faisons un autre test. Cette fois-ci, faisons $\\frac n 2$ insertions suivies de $\\frac n 2$ suppressions (le contraire serait délicat à faire :-))." ], "metadata": {} }, { "cell_type": "code", "source": [ "def test_file2(n):\n", " f = File()\n", " for k in range(n // 2):\n", " f.push(123)\n", " for k in range(n // 2):\n", " x = f.pop()\n", " return f.counter, f.maxlen" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "test_file2(100000)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Bref, se pourrait-il que notre algorithme ait une complexité amortie constante ? Oui, comme nous allons le montrer." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 3.4 Complexité amortie" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Pour toute file d'attente $s$, posons\n", "\n", "$$\\Phi(s)=|s.r|$$\n", "\n", "où la valeur absolue désigne la longueur de la liste. À la suite d'une insertion ou d'une suppression, $s$ se transforme en une file $s'$ (plus exactement, les champs de $s$ ont été modifiés, mais ne chipotons pas). Posons\n", "\n", "$$c_a(s) = c(s) + \\Phi(s')-\\Phi(s)$$\n", "\n", "où $c(s)$ est le coût réel du passage de $s$ à $s'$. Examinons les différents cas possibles.\n", "\n", "1. On passe de $s$ à $s'$ par une insertion. On a alors $c(s)=1$ et $\\Phi(s')=1+\\Phi(s)$ puisqu'on ajoute un élément à $s.r$. Ainsi,\n", "\n", "$$c_a(s) = 2$$\n", "\n", "2. On passe de $s$ à $s'$ par une suppression, et $s.f$ n'est pas vide. On a alors $c(s)=1$ et $\\Phi(s')=\\Phi(s)$. Ainsi,\n", "\n", "$$c_a(s)=1$$\n", "\n", "3. On passe de $s$ à $s'$ par une suppression, et $s.f$ est la liste vide. On a alors $c(s)=|s.r| + 1$, puisque le renversement coûte $|s.r|$ opérations élémentaires, puis la suppression d'un élément à la fin de $s.f$ coûte une opération. De plus, $\\Phi(s')=0$ et $\\Phi(s)=|s.r|$. Ainsi,\n", "\n", "$$c_a(s)=|s.r|+1-|s.r|=1$$\n", "\n", "__Conclusion__ : Pour toute file $s$ on a $c_a(s)=1$ pour une opération `pop` et $c_a(s)=2$ pour une opération `push`." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Partons d'une file $s_0$ initialement vide et effectuons $n$ opérations, insertion ou suppression. On fabrique successivements $n$ files d'attente $s_1,\\ldots,s_n$. On a\n", "\n", "$$\\sum_{k=0}^{n-1} c_a(s_k)=\\sum_{k=0}^{n-1}\\left(c(s_k)+\\Phi(s_{k+1})-\\Phi(s_k)\\right)$$\n", "\n", "Par téléscopage, et du fait que $\\Phi(s_0)=0$, il vient\n", "\n", "$$\\sum_{k=0}^{n-1} c_a(s_k)=\\Phi(s_{n})+\\sum_{k=0}^{n-1}c(s_k)$$\n", "\n", "ou encore\n", "\n", "$$\\sum_{k=0}^{n-1} c(s_k)=-\\Phi(s_{n})+\\sum_{k=0}^{n-1}c_a(s_k)$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Supposons que l'on ait effectué $p$ `push` (et donc $n-p$ `pop`). On obtient\n", "\n", "$$\\sum_{k=0}^{n-1}c_a(s_k)=2p+(n-p)=n+p$$\n", "\n", "Ainsi, \n", "\n", "$$\\sum_{k=0}^{n-1} c(s_k)=n+p-\\Phi(s_{n})\\le n+p$$\n", "\n", "__Exemple__ : Prenons $n$ pair et $p=\\frac n 2$. On effectue donc autant de `push` que de `pop`, ce qui entraîne que $s_n=[]$, et donc $\\Phi(s_n)=0$. De là, \n", "\n", "$$\\sum_{k=0}^{n-1}c(s_k)=n+\\frac n 2 - 0=\\frac 3 2 n$$ \n", "\n", "On retrouve le facteur $\\frac 3 2$ obtenu dans nos tests." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 3.5 Tracés" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Sans commentaires, voici le tracé du potentiel et des différences de potentiel pour 10000 `push` ou `pop` dans une file initialement vide. En noir, le potentiel. En rouge, les différences de potentiel." ], "metadata": {} }, { "cell_type": "code", "source": [ "def tracer_potentiel2(n):\n", " f = File()\n", " ps = []\n", " for k in range(n):\n", " r = random.randint(0, 1)\n", " if r == 0 and not f.is_empty():\n", " x = f.pop()\n", " else:\n", " f.push(random.randint(0, 10))\n", " ps.append(len(f.r))\n", " qs = [ps[k+1]-ps[k] for k in range(len(ps)-1)]\n", " plt.plot(qs, 'r')\n", " plt.plot(ps, 'k')\n", " plt.grid()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "tracer_potentiel2(10000)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "## 4. Files à deux extrémités" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 4.1 C'est quoi ?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici un exemple qui généralise le précédent. Je me cantonne au domaine des structures de connées \"linéaires\" pour ne pas avoir à décrire du code trop compliqué. \n", "\n", "Une file à deux extrémités est une structure de données du genre précédent mais dans laquelle il est possible d'insérer ou supprimer en tête ou en queue de la file. Ce nom bizarre `Deque` est celui utilisé par tous les langages de programmation classiques (C++, Java, Python, ...). Voici le code de la classe `Deque` (Double Ended Queue). Il ressemble beaucoup à celui de la classe `File`. \n", "\n", "Il va cependant nous falloir être subtils pour les méthodes `pop`. Prenons l'exemple de `pop_rear`, qui supprime l'élément en queue de la file $s$. \n", "\n", "- Si $s.r$ n'est pas vide, aucun problème. Il suffit d'appeler la méthode `pop` de la __liste__ $s.r$, qui s'exécute en $O(1)$.\n", "\n", "- Si $s.r$ est vide, on procède comme suit : on coupe $s.f$ en deux moitiés, on renverse la première moitié que l'on affecte à $s.r$. Puis on ne garde que la deuxième moitié dans $s.f$.\n", "\n", "Une bonne question est : on coupe donc la file en deux moitiés, mais comment décider comment couper en deux ? Où s'arrête la tête et où commence la queue ? Tout cela n'a ni queue ni tête ! Patience ...\n", "\n", "Ça a l'air farfelu mais ça marche, comme nous allons le __prouver__ par une analyse amortie." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 4.2 La classe `Deque`" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici le code de la classe `Deque`. \n", "\n", "- Les méthodes `push_front` et `push_rear` ne présentent aucune difficulté.\n", "- Les méthodes `pop_front` et `pop_rear` sont à méditer. Enfin, il vous suffit de méditer sur l'une des deux, parce qu'on passe de l'une à l'autre en échangeant les \"f\" et les \"r\"." ], "metadata": {} }, { "cell_type": "code", "source": [ "class Deque:\n", " \n", " def __init__(self):\n", " self.f = []\n", " self.r = []\n", " self.counter = 0\n", " self.maxlen = 0\n", " \n", " def reset_counter(self):\n", " self.counter = 0\n", " \n", " def is_empty(self):\n", " return self.r == [] and self.f == []\n", " \n", " def push_rear(self, x):\n", " self.r.append(x)\n", " self.counter += 1\n", " l = len(self.f) + len(self.r)\n", " if l > self.maxlen: self.maxlen = l\n", " \n", " def push_front(self, x):\n", " self.f.append(x)\n", " self.counter += 1\n", " l = len(self.f) + len(self.r)\n", " if l > self.maxlen: self.maxlen = l\n", " \n", " def pop_front(self):\n", " if self.f == []:\n", " n = len(self.r)\n", " self.f = self.r[:(n+1)//2]\n", " self.f.reverse()\n", " self.r = self.r[(n+1)//2:]\n", " self.counter += n\n", " x = self.f.pop()\n", " self.counter += 1\n", " return x\n", " \n", " def pop_rear(self):\n", " if self.r == []:\n", " n = len(self.f)\n", " self.r = self.f[:(n+1)//2]\n", " self.r.reverse()\n", " self.f = self.f[(n+1)//2:]\n", " self.counter += n\n", " x = self.r.pop()\n", " self.counter += 1\n", " return x" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "__Remarque__ : Pourquoi une complexité de $n+1$ opérations dans les méthodes `pop` ? Il s'agit de couper une liste en deux et de renverser l'une des deux moitiés. Prenons l'exemple de `pop_front`. Notre code peut être amélioré. On peut en même temps recopier la première \"moitié\" de $s.r$ dans $s.f$, tout en la renversant. Cela coûte $\\lfloor\\frac{n+1}{2}\\rfloor$ opérations élémentaires. Il faut ensuite ajuster $s.f$ à sa seconde moitié, ce qui n'est pas gratuit ! Cela coûte $n-\\lfloor\\frac{n+1}{2}\\rfloor$ opérations. Au total, $n$ opérations sont suffisantes. Il faut ensuite rajouter l'opération qui enlève un élément à $s.f$.\n", "\n", "Pour les amateurs, le code d'une fonction `couper_renverser` (avec compteurs de \"append\") ressemblerait à cela :" ], "metadata": {} }, { "cell_type": "code", "source": [ "def couper_renverser(s):\n", " count = 0\n", " n = len(s)\n", " p = (n + 1) // 2\n", " s1 = []\n", " for k in range(p - 1, -1, -1):\n", " s1.append(s[k])\n", " count += 1\n", " s2 = []\n", " for k in range(p, n):\n", " s2.append(s[k])\n", " count += 1\n", " return (s1, s2, count)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "couper_renverser([1, 2, 3, 4, 5, 6, 7])" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "couper_renverser([1, 2, 3, 4, 5, 6, 7, 8])" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "### 4.3 Complexité amortie" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Qu'allons-nous prendre cette fois ci comme potentiel ? Pour une file $s$, posons\n", "\n", "$$\\Phi(s)=\\left||s.r|-|s.f|\\right|$$\n", "\n", "où la valeur absolue extérieure est une \"vraie\" valeur absolue et les valeurs absolues intérieures dénotent des longueurs de listes. Il ne devrait pas y avoir de confusion dans ce qui va suivre.\n", "\n", "Pour des raisons de symétrie, les méthodes `push_front` et `push_rear` ont la même complexité amortie, et de même pour les méthodes `pop`." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Commençons par l'analyse de `push_rear`. La file $s$ se transforme en une file $s'$. La complexité de cette opération est 1. De plus, $|s'.r|=|s.r|+1$ et $|s'.f|=|s.f|$. Donc\n", "\n", "$$\\Phi(s')=||s.r|-|s.f|+1|\\le ||s.r|-|s.f||+1=\\Phi(s)+1$$\n", "\n", "Donc\n", "\n", "$$c_a(s)=c(s)+\\Phi(s')-\\Phi(s)\\le 2$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Passons à l'analyse de `pop_rear`. Histoire de ne pas nous noyer dans des parties entières supposons $n$ pair. Le cas où $n$ est impair est laissé au lecteur.\n", "\n", "- Si $s.r$ n'est pas vide, alors $|s'.r|=|s.r|-1$ et $|s'.f|=|s.f|$. Donc\n", "\n", "$$\\Phi(s')=||s.r|-|s.f|-1|\\le ||s.r|-|s.f||+1=\\Phi(s)+1$$\n", "\n", "et comme $c(s)=1$, \n", "\n", "$$c_a(s)\\le 2$$\n", "\n", "- Si $s.r$ est vide, alors $c(s)=|s.f| + 1$. De plus, $\\Phi(s)=|s.f|$ et \n", "\n", "$$\\Phi(s')=||s'.r|-|s'.f||=|\\frac 1 2|s.f|-1-\\frac 1 2 |s.f||=1$$\n", "\n", "Ainsi,\n", "\n", "$$c_a(s)=c(s)+\\Phi(s')-\\Phi(s)\\le 2$$\n", "\n", "Comme pour les files d'attente nous obtenons une complexité amortie en $O(1)$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Faisons un petit test : $n$ insertions et suppressions en tête et/ou en queue, sur une file initialement vide." ], "metadata": {} }, { "cell_type": "code", "source": [ "def test3(n):\n", " s = Deque()\n", " for k in range(n):\n", " r = random.randint(0, 3)\n", " if r == 0: s.push_front(1)\n", " elif r == 1: s.push_rear(1)\n", " elif r == 2 and not s.is_empty(): s.pop_front()\n", " elif r == 3 and not s.is_empty() : s.pop_rear()\n", " #print(s.f, s.r)\n", " return s.counter, s.maxlen" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "test3(100000)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Quelle est la complexité totale ? Avec les notations déjà utilisées pour les files d'attente, nous obtenons\n", "\n", "$$\n", "\\begin{eqnarray*}\n", "\\sum_{k=0}^{n-1}c(s_k)&=&\\sum_{k=0}^{n-1}c_a(s_k)+\\Phi(s_0)-\\Phi(s_n)\\\\\n", "&=&\\sum_{k=0}^{n-1}c_a(s_k)-\\Phi(s_n)\\\\\n", "&\\le& \\sum_{k=0}^{n-1}c_a(s_k)\\\\\n", "&\\le& 2n\n", "\\end{eqnarray*}\n", "$$\n", "\n", "Remarquons pour terminer que notre majorant $2n$ est pessimiste. Les majorations de valeurs absolues du genre $|x-1|$ par $|x|+1$ sont effectivement __très__ pessimistes lorsque $x\\ge 1$ :-). Disons pour faire vite que le 2 du $2n$ est plutôt proche de 1, comme le suggère d'ailleurs notre fonction `test3`. Une analyse plus poussée permettrait sans doute d'effacer le \"pour faire vite\" et de le remplacer par une preuve. Avis aux amateurs ..." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 4.4 Tracés" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Sans commentaires, voici le tracé du potentiel et des différences de potentiel pour 10000 `push` ou `pop` dans une `Deque` initialement vide." ], "metadata": {} }, { "cell_type": "code", "source": [ "def tracer_potentiel3(n):\n", " s = Deque()\n", " ps = []\n", " for k in range(n):\n", " r = random.randint(0, 3)\n", " if r == 0: s.push_front(1)\n", " elif r == 1: s.push_rear(1)\n", " elif r == 2 and not s.is_empty(): s.pop_front()\n", " elif r == 3 and not s.is_empty() : s.pop_rear()\n", " ps.append(abs(len(s.r) - len(s.f)))\n", " qs = [ps[k+1]-ps[k] for k in range(len(ps)-1)]\n", " plt.plot(qs, 'r')\n", " plt.plot(ps, 'k')\n", " plt.grid()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "tracer_potentiel3(10000)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "## 5. Ajout et suppression dans une liste" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Nous discutons dans cette section de la complexité de la \"fonction\" `append` du langage Python. Pour cela, il va nous falloir entrer dans le détail de la façon dont les listes sont implémentées dans notre langage préféré. " ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.1 Les méthodes `append` et `pop` " ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Les listes du langage Python possèdent un certain nombre de __méthodes__. Les voici :" ], "metadata": {} }, { "cell_type": "code", "source": [ "s = [1, 2, 3]\n", "print(s.__dir__())" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Deux de ces méthodes vont nous intéresser : `append` et `pop`." ], "metadata": {} }, { "cell_type": "code", "source": [ "s.append(4)\n", "print(s)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "x = s.pop()\n", "print(x, s)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Quelle est la complexité de ces méthodes ? Pour faire vite, $O(1)$. En réalité il s'agit là d'une __complexité amortie__. Concentrons nous sur `append`, une discussion analogue peut être faite pour `pop`." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.3 La structure interne des listes" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Il existe différentes versions du langage Python. Ce dont je vais parler ici concerne Cython, la version de Python écrite en C. C'est presque certainement celle que vous utilisez vous-mêmes. De façon \"interne\", une liste est représentée par un tableau de pointeurs sur des objets. Prenons un exemple." ], "metadata": {} }, { "cell_type": "code", "source": [ "s = [3, False, \"pomme\"]" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Lors de la création de $s$, on peut imaginer (à tort) que Python réserve (le mot exact est __alloue__) trois cases contiguës dans la mémoire.\n", "\n", "- La case 0 contient l'adresse d'un objet de valeur l'entier 3 (c'est à dire une autre zone de la mémoire dont Python interprète le contenu comme étant l'entier 3).\n", "- La case 1 contient l'adresse d'un objet de valeur le booléen False.\n", "- La case 2 contient l'adresse d'un objet de valeur la chaîne de caractères \"pomme\".\n", "\n", "Et $s$ dans tout ça ? Eh bien $s$ \"connaît\" l'adresse de la case 0. Ainsi, lorsque nous demandons $s[2]$, Python peut renvoyer \"pomme\" en temps $O(1)$ :\n", "\n", "- En prenant l'adresse du début du tableau et en ajoutant 2 (case contiguës !), ou plutôt deux fois la longueur d'une case.\n", "- Puis en renvoyant l'objet qui se trouve à l'adresse contenue dans la case en question.\n", "\n", "Nous voyons donc que l'accès à un élément de $s$ peut se faire en $O(1)$ __parce que les cases du tableau sont contiguës__. Une discussion analogue fonctionne pour l'affectation d'une valeur à une case de $s$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.4 Le fonctionnement de `append` " ], "metadata": {} }, { "cell_type": "code", "source": [ "print(s)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Que se passe-t-il lorsque nous demandons `s.append(3.14)` ? Peut-être que Python rajoute une case contiguë à la case numéro 2 et y met l'adresse d'un objet de valeur le flottant $3.14$ ? Oui, mais non ! Parce que en général cette case est déjà occupée par d'autres données ! Alors que faire ? Il faut réserver quelque part dans la mémoire 4 cases contiguës, et déplacer les éléments de $s$ dans ces cases ... Le seul problème est que si l'on fait cela à chaque ajout d'élément, la complexité de `append` est en $O(n)$ où $n$ est la longueur de la liste. Alors que faire ?\n", "\n", "La solution adoptée par Python est la suivante :\n", "\n", "- Une instruction du genre `s = []` ne réserve aucune place en mémoire.\n", "- Une instruction du genre `s.append(123)`, où $s$ est vide, affecte non pas une mais 4 places en mémoire. Cela nous donne donc un crédit de 3 cases contiguës qui pourront éventuellement être remplies ultérieurement.\n", "- Si $s$ est de longueur 4, `s.append(123)` affecte 8 places en mémoire et déplace les 4 cases de $s$ au nouvel emplacement. On est donc tranquilles pour 4 appels à `append`.\n", "\n", "Et après 4 et 8, qu'y a-t-il me direz-vous ? 16, 32, etc. ? Quels sont les nombres magiques déclenchant un déplacement de toutes les valeurs de $s$ ? Eh bien oui pour 16, mais non pour 32. Voici une fonction vous donnant les $n$ premiers nombres. Pour $n$ grand, chaque nombre est environ égal à $\\frac 9 8\\simeq 1.125$ fois le précédent." ], "metadata": {} }, { "cell_type": "code", "source": [ "def guido(n):\n", " s = [0]\n", " for k in range(n):\n", " y = s[-1] + 1\n", " z = y // 8\n", " if y < 9: z = z + 3\n", " else: z = z + 6\n", " s.append(s[-1] + z + 1)\n", " return s" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "s = guido(20)\n", "print(s)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "s = guido(50)\n", "print([s[k] / s[k-1] for k in range(2, len(s))])" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "__Remarque__ : Le nom de la fonction, `guido`, est un petit clin d'oeil au concepteur du langage Python. S'il lit ce notebook je serais ravi de savoir pourquoi précisément il a choisi ces nombres :-)." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.5 La complexité réelle de `append`" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Quelle est la complexité réelle d'une suite de `append` sur une liste initialement vide ?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici tout d'abord une fonction qui calcule, à partir d'un terme de la suite de Guido, le terme suivant." ], "metadata": {} }, { "cell_type": "code", "source": [ "def g(x):\n", " y = x + 1\n", " z = y // 8\n", " if y < 9: z = z + 3\n", " else: z = z + 6\n", " return x + z + 1" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "x = 0\n", "for k in range(10):\n", " x = g(x)\n", " print(x)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "La fonction `complexites` renvoie la liste $[c_0,\\ldots,c_n]$ où $c_k$ est la complexité réelle du $k$ième appel à `append`. Si $k$ n'est pas un nombre de Guido, une opération élémentaire suffit. Sinon, il y a réallocation et $k+1$ opérations sont nécessaires : recopie de la liste initiale, de longueur $k$, $+$ ajout d'un élément." ], "metadata": {} }, { "cell_type": "code", "source": [ "def complexites(n):\n", " cs = []\n", " x = g(0)\n", " for m in range(n + 1):\n", " if m < x:\n", " cs.append(1)\n", " else:\n", " x = g(x)\n", " cs.append(m + 1)\n", " return cs" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "print(complexites(100))" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "La plupart des complexités valent 1, mais, une fois de temps en temps (devinez quand ?) une réallocation de la liste provoque une complexité importante. Un petit dessin ?" ], "metadata": {} }, { "cell_type": "code", "source": [ "plt.plot(complexites(10000), 'k')\n", "plt.grid()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici un autre graphique très intéressant. À partir de la liste $[c_0,\\ldots,c_n]$ des complexités, calculons $[c'_0,\\ldots,c'_n]$ où\n", "\n", "$$c'_k=\\frac 1 {k+1}\\sum_{j=0}^kc_j$$\n", "\n", "La quantité $c'_k$ est donc la complexité moyenne de `append` pour $k+1$ insertions à partir de la liste vide." ], "metadata": {} }, { "cell_type": "code", "source": [ "def moyennes(s):\n", " s1 = s[:]\n", " n = len(s)\n", " for k in range(1, n):\n", " s1[k] = s1[k] + s1[k - 1]\n", " for k in range(n):\n", " s1[k] = s1[k] / (k + 1)\n", " return s1" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "plt.plot(moyennes(complexites(10000)), 'k')\n", "plt.grid()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Il semblerait que cette complexité moyenne soit majorée ... par 10, peut-être ? Nous ne prouverons pas ce résultat, mais dans le paragraphe suivant nous retrouverons le nombre 10." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.6 La complexité amortie de `append`" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Proposition__ : La complexité amortie de `append` est $O(1)$.\n", "\n", "__Démonstration__ : Hors de question de faire la démonstration pour les valeurs magiques de $n$ de la suite de Guido. Nous allons prouver ce résultat en supposant qu'à chaque fois que la taille de $s$ atteint une puissance de $\\mu$ (où $\\mu>1$), il y a une recopie dans une liste $\\mu$ fois plus longue. Notre suite magique est donc\n", "\n", "$$0,1,\\mu,\\mu^2,\\ldots$$\n", "\n", "Le fait de prendre des valeurs de $\\mu$ non entières, comme par exemple $\\frac 9 8$ est évidemment perturbant. Une démonstration exacte ne peut pas ne pas tenir compte de cela ! Continuons tout de même ainsi. Ce qui suit est donc une démonstration approximative :-).\n", "\n", "__Question__ : On prend $\\mu = \\frac 9 8$. Quel est le plus petit entier $p$ tel que $\\mu^{p+1}-\\mu^p>1$ ?" ], "metadata": {} }, { "cell_type": "code", "source": [ "def taille_min():\n", " mu = 9 / 8\n", " p = 0\n", " while mu ** (p + 1) - mu ** p <= 1:\n", " p += 1\n", " print(p, mu ** p)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "taille_min()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "Multiplier la taille allouée par $\\mu$ ne fait réellement grandir le tableau que pour des tailles de tableau supérieures à 9 (et une puissance de $\\mu$ supérieure à 18). Voici un début de piste pour la compréhension de la \n", "suite de Guido ..." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Revenons à notre démonstration__ : pour toute liste $s$ de longueur $n$ il y a donc en réalité un tableau de longueur $\\mu^p$ alloué en mémoire, où $p$ est le plus petit entier tel que $n\\le \\mu ^p$.\n", "\n", "Posons \n", "\n", "$$\\Phi(s)=\\beta n-\\alpha\\mu^p$$\n", "\n", "où $\\alpha\\ge 1$ et $\\beta>0$ seront choisis plus loin de façon génialement astucieuse.\n", "\n", "Soient $c(s)$ la complexité de l'ajout d'un élément à $s$, et $c_a(s)=c(s)+\\Phi(s')-\\Phi(s)$ où $s'$ est la liste obtenue par l'ajout d'un élément. Deux cas se présentent.\n", "\n", "- Si $n<\\mu^p$, alors $c(s)=1$, $\\Phi(s)=\\beta n -\\alpha\\mu^p$ et $\\Phi(s')=\\beta n + \\beta -\\alpha\\mu^p$. De là,\n", "\n", "$$c_a(s)=\\beta + 1$$\n", "\n", "- Si $n=\\mu^p$, alors $c(s)=n+1$, $\\Phi(s)=\\beta n - \\alpha n$ et $\\Phi(s')=\\beta n + \\beta - \\alpha\\mu n$. De là,\n", "\n", "$$c_a(s)=(n+1) + (\\beta n+\\beta -\\alpha\\mu n)-(\\beta n - \\alpha n)=1+\\beta+(1-\\alpha(\\mu-1))n$$\n", "\n", "Si nous choisissons $\\alpha=\\frac 1 {\\mu - 1}$, nous obtenons $c_a(s)=1+\\beta$, et la complexité amortie est donc bien constante.\n", "\n", "Commment choisir $\\beta$ ? En imposant la condition $\\Phi(s)\\ge 0$. On a $\\mu^{p-1}\\beta \\mu^{p-1}-\\alpha\\mu^p=\\mu^{p-1}(\\beta-\\alpha\\mu)$$\n", "\n", "Clairement, $\\beta=\\alpha\\mu$ est la valeur de choix. Finalement,\n", "\n", "$$\\Phi(s)=\\frac{1}{\\mu-1}(\\mu n-\\mu^{p})$$" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Conséquence__ : Si on effectue $n\\ge 1$ ajouts d'élément à la fin d'une liste $s_0$ initialement vide, on fabrique successivement les listes $s_1,\\ldots,s_n$. La complexité totale de ces $n$ ajouts est\n", "\n", "$$\\sum_{k=0}^{n-1}c(s_k)=\\sum_{k=0}^{n-1}(c_a(s_k)-\\Phi(s_{k+1})+\\Phi(s_k))$$\n", "\n", "Par téléscopage :\n", "\n", "$$\\sum_{k=0}^{n-1}c(s_k)=-\\Phi(s_{n})+\\Phi(s_0)+\\sum_{k=0}^{n-1}c_a(s_k)= (1+\\beta)n + \\Phi(s_0)-\\Phi(s_n)$$\n", "\n", "On a $\\Phi(s_0)=-1$ car $s_0$ est vide, et $\\Phi(s_n)\\ge 0$. Ainsi, en posant $K=1+\\beta=\\frac{2\\mu-1}{\\mu-1}$,\n", "\n", "$$\\sum_{k=0}^{n-1}c(s_k)\\le Kn-1$$\n", "\n", "__Remarqu__ : $K$ n'est rien d'autre que la complexité amortie de `append`." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Exemples__ :\n", "\n", "- Pour $\\mu=101$, on a $K=2.01$.\n", "- Pour $\\mu=2$, on a $K=3$.\n", "- Pour $\\mu=\\frac 9 8$, la valeur asymptotique de la suite de Guido, on a $K=10$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Remarque__ : Clairement, $\\mu=2$ donne une meilleure complexité que $\\mu=\\frac 9 8$. Alors pourquoi le langage Python choisit-il la deuxième solution ? Et pourquoi pas $\\mu=101$ ???\n", "\n", "La complexité \"en temps\" n'est pas la seule contrainte à étudier lorsqu'on élabore un algorithme. Une autre quantité importante est la __complexité en espace__ de l'algorithme. De combien de mémoire l'algorithme a-t-il besoin pour renvoyer le résultat ? Et là, clairement, $\\mu=\\frac 9 8$ est préférable à $\\mu =2$. Quant à $\\mu=101$, il est hors de question d'y penser. Bilan :\n", "\n", "- $\\mu$ grand : insertion rapide, grand gaspillage de mémoire.\n", "- $\\mu$ petit : insertion lente, petit gaspillage de mémoire.\n", "\n", "Le choix de $\\mu$ est donc un choix délicat ... faisons confiance aux concepteurs de Python pour avoir très longuement réfléchi à cette question." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Remarque__ : \n", "\n", "- L'allocation de mémoire n'est pas une opération gratuite. Pour de très grosses listes, cette allocation peut avoir un impact sur la complexité de la fonction `append`. \n", "- Lors du déplacement d'une liste vers un autre emplacement de la mémoire, l'ancien emplacement devient inutilisé et doit être libéré. C'est le rôle du __ramasse-miettes__ (Garbage Collector), qui tourne en tâche de fond lorsqu'un programme Python s'exécute. Cette opération n'est pas non plus gratuite." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.7 Tracé des potentiels" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Voici le tracé du potentiel et des différences de potentiel pour 10000 `append` dans une liste initialement vide." ], "metadata": {} }, { "cell_type": "code", "source": [ "def tracer_potentiel4(n, mu):\n", " ps = [-1]\n", " alpha = 1 / (mu - 1)\n", " for k in range(1, n + 1):\n", " p = math.ceil(math.log(k) / math.log(mu))\n", " ps.append((mu * k - mu ** p) / (mu - 1))\n", " qs = [ps[k + 1] - ps[k] for k in range(n)]\n", " plt.plot(qs, 'r')\n", " plt.plot(ps, 'k')\n", " plt.grid()" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "code", "source": [ "tracer_potentiel4(10000, 9 / 8)" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "### 5.8 Et maintenant ?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Il conviendrait sans doute (ce que je ne ferai pas ici) d'analyser la complexité amortie de `pop`, ainsi que la complexité d'appels multiples à `append` et `pop`, comme nous l'avons fait pour les files.\n", "\n", "__Exercice__ : Le fonctionnement de `pop` est le suivant : chaque fois que la longueur de la liste devient inférieure à la moitié de la taille allouée pour la liste, il y a allocation d'un nouvel espace et déplacement des données. La taille allouée est le plus petit nombre de Guido supérieur à la longueur de la liste. Analysez la méthode `pop`par la méthode du potentiel. Montrez que la complexité amortie de `pop` est $O(1)$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Pour les amateurs__ : Le code source du langage Python (écrit en C) est disponible en ligne. Regardez le code de `append` et `pop`. Il se trouve dans le fichier `Objects/listobject.c`. Regardez en particulier le code de la fonction C `list_resize`. Ce code est commenté, il dit précisément quand ont lieu les réallocations." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "__Bibliographie__ : \n", "\n", "- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms (2nd Edition), MIT Press 2001. Contient un chapitre sur l'analyse amortie.\n", "\n", "- C. Okazaki, Purely Functional Data Structures, Cambridge Uiversity Press 1998. Mine d'informations sur les structures de données non impératives. Ce livre parle de programmation fonctionnelle et s'adresse à des programmeurs connaissant les langages Standard ML et/ou Haskell mais si vous maîtrisez Ocaml vous n'aurez aucun mal à comprendre le code ML. Si vous ne connaissez que Python ce sera plus difficile ..." ], "metadata": {} } ], "metadata": { "kernel_info": { "name": "python3" }, "kernelspec": { "name": "python3", "language": "python", "display_name": "Python 3" }, "language_info": { "name": "python", "version": "3.6.4", "mimetype": "text/x-python", "codemirror_mode": { "name": "ipython", "version": 3 }, "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "file_extension": ".py" }, "nteract": { "version": "0.14.3" } }, "nbformat": 4, "nbformat_minor": 2 }