{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Files de priorité\n", "\n", "Marc Lorenzi\n", "\n", "11 janvier 2019" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Introduction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.1 De quoi allons-nous parler ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "De nombreux problèmes algorithmiques stockent un ensemble de données et effectuent des opérations sur ces données. Quel genre d'opérations ? Cela dépend du problème. \n", "\n", "Nous allons dans ce notebook nous intéresser aux problèmes pour lesquels, à chaque donnée, est associée une __priorité__. Qu'entendons-nous par priorité ? Une priorité est un élément d'un ensemble totalement ordonné. Pour prendre un exemple concret, les données de notre problème sont des tâches que doit exécuter un système d'exploitation. Certaines tâches sont urgentes (le curseur de la souris doit bouger), d'autres un peu moins (une fenêtre doit s'ouvrir), d'autres beaucoup moins (le système doit se mettre à jour). On affecte aux tâches extrêmement urgentes la priorité 1, à celles qui le sont un peu moins la priorité 2, ..., à la tâche qui consiste à préparer un café la priorité 50 (ou 0, cela dépend). \n", "\n", "Un autre exemple ? Les données sont les sommets d'un graphe, les priorités sont leurs distances à un sommet fixé. Bref, Disposer de structures de données permettant le stockage d'objets possédant une priorité est peut-être intéressant.\n", "\n", "Discuter en l'air d'une structure de type \"ensembliste\", c'est bien. Se demander quelles opérations nous aurons à faire sur cette structure est l'étape suivante." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans ce qui va suivre, les opérations que l'on désire effectuer sont les suivantes :\n", "\n", "- Créer un nouvel ensemble.\n", "- Tester si un ensemble est vide.\n", "- Récupérer dans un ensemble un objet de priorité minimale.\n", "- Insérer dans un ensemble un objet $x$ ayant la priorité $p$.\n", "- Supprimer d'un ensemble un objet de priorité minimale ET le renvoyer.\n", "\n", "Et également\n", "\n", "- Diminuer dans un ensemble la priorité d'un objet." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Une structure de données permettant d'effectuer ces opérations est appelée une __file de priorité__, ou __tas__. Pour être franc, les puristes considèrent le concept de file de priorité comme __abstrait__ et la structure de tas comme une certaine implémentation __concrète__ de ce type abstrait de données, celle que nous verrons à la section 3. Je vais tenter dans ce qui suit d'être puriste :-). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Remarque__ : \n", "\n", "- Dans une file de priorité, plusieurs objets peuvent avoir la même priorité. Vous verrez parfois dans ce qui suit des phrases comme \"UN objet de priorité minimale\".\n", "\n", "- En revanche, si un objet possède plusieurs priorités différentes, c'est le chaos. Nous voulons à tout prix pouvoir parler de LA priorité de l'objet $x$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.2 Listes aléatoires" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour tester nos fonctions, il sera bien utile de pouvoir créer des listes aléatoires. Voici une fonction renvoyant une permutation aléatoire des entiers entre 0 et $n-1$. Cette fonction utilise l'algorithme de Fisher-Yates. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def random_list(n):\n", " s = list(range(n))\n", " for i in range(n):\n", " j = random.randint(i, n - 1)\n", " s[i], s[j] = s[j], s[i]\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "random_list(10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3 Files \"aléatoires\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour créer une file \"aléatoire\", on part d'une file initialement vide et on insère dans la file des objets aléatoires. Pourquoi ces guillemets ? Parce que je ne sais pas mettre une probabilité sur l'ensemble des tas, puis prouver que la fonction `file_aleatoire` renvoie une file donnée avec une certaine probabilité.\n", "\n", "Pourquoi n'avais-je pas mis de guillemets à \"liste aléatoire\" ? Parce je tiens à la disposition de qui le désire la __preuve__ que l'algorithme de Fisher-Yates décrit plus haut renvoie effectivement une permutation aléatoire de la liste $[0,1,\\ldots,n-1]$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def file_aleatoire(n):\n", " prios = random_list(n)\n", " objets = random_list(n)\n", " f = nouvelle_file()\n", " for i in range(n): inserer(f, objets[i], prios[i])\n", " return f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Évidemment nous ne pouvons pas exécuter cette fonction puisque nous n'avons encore écrit aucune fonction sur les files de priorité." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Une implémentation naïve" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Représentons une file de priorité par une simple liste tout en vrac, un tas d'objets quoi ! Les éléments de notre liste seront des couples $(x, p)$ où $x$ est un objet et $p$ est un entier, la __priorité__ de l'objet $x$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Créer une nouvelle file et tester si une file est vide est immédiat. Ces deux opérations se font en complexité $O(1)$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def nouvelle_file(): return []\n", "\n", "def est_vide(f): return len(f) == 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Insérer un objet $x$ avec la priorité $p$ est aussi immédiat et se fait en complexité $O(1)$. On utilise la méthode `append` du type `list` en priant Guido Van Rossum, créateur de Python, pour que cette opération soit en $O(1)$.\n", "\n", "__Remarque__ : Ce n'est en fait pas tout à fait vrai. Bien que l'implémentation des listes en Python soit un sujet fascinant, nous admettrons dans la suite que `append` est en $O(1)$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inserer(f, x, p): f.append((x, p))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Maintenant nous pouvons créer des files \"aléatoires\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f = file_aleatoire(100)\n", "print(f)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Trouver un objet de priorité minimale ne pose pas non plus de problème. On nous demande de trouver le \"plus petit\" élément d'une liste. Mais remarquons que cette fois-ci la complexité de l'opération est $O(n)$, où $n$ est la taille de la liste.\n", "\n", "__Petit aparté__ : Euh, au fait, dans une file, on stocke les couples $(x,p)$ ou les couples $(p, x)$ ? Vous avez déjà oublié ? Moi aussi. Imaginez un peu ce qui va se passer lorsque vous relirez votre code Python dans 2 ans. Ou pire, lorsque quelqu'un d'autre le lira parce que vous, vous aurez changé de boulot et que votre successeur doit écrire un patch pour votre programme ?\n", "\n", "Maizalor, que faire ? Facile ! On définit deux petites fonctions.\n", "\n", "__Règle absolue__ : les nombres magiques tu n'utiliseras point. Tout le monde sera d'accord pour dire que `prio(t[k])` est plus lisible que `t[k][1]` (ou `[0]`, j'ai déjà oublié)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def data(y): return y[0]\n", "def prio(y): return y[1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def top(f):\n", " n = len(f)\n", " if n == 0: raise Exception('File vide')\n", " else:\n", " m = 0\n", " for k in range(n):\n", " if prio(f[k]) < prio(t[m]): m = k\n", " return t[m]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour supprimer de la file un objet de priorité minimale :\n", "\n", "- On trouve d'abord l'indice de l'objet en question.\n", "- On décale tous les éléments de la liste à droite de cet d'objet d'un cran vers la gauche.\n", "- On supprime le dernier élément de la liste (eh oui, on a un élément de moins).\n", "\n", "La complexité en pire cas de cette fonction que nous appellerons `pop` est clairement $O(n)$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def pop(f):\n", " n = len(f)\n", " if n == 0: raise Exception('File vide')\n", " else:\n", " m = 0\n", " for k in range(n):\n", " if prio(f[k]) < prio(f[m]): m = k\n", " y = f[m]\n", " for k in range(m, n - 1):\n", " f[k] = f[k + 1]\n", " f.pop() # Le `pop` du type liste !\n", " return y" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f = file_aleatoire(10)\n", "print(f)\n", "x, p = pop(f)\n", "print(x, p)\n", "print(f)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour diminuer la priorité d'un objet $x$ :\n", "\n", "- On trouve $x$ dans la liste. Ici, c'est la fonction `data` qui entre en jeu.\n", "- On ajuste sa priorité.\n", "\n", "Ici encore, complexité en pire cas en $O(n)$. Remarquons que notre fonction marche aussi très bien pour __augmenter__ la priorité de l'objet !" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def diminuer_prio(f, x, p):\n", " n = len(f)\n", " k = 0\n", " while k < n and data(f[k]) != x: k = k + 1\n", " if k == n:\n", " raise Exception('%s non trouvé' % x)\n", " else:\n", " f[k] = (x, p)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f = file_aleatoire(10)\n", "print(f)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "diminuer_prio(f, 8, -1)\n", "print(f)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : On décide de représenter un tas par une liste __triée__ par priorités croissantes. Écrivez les fonctions `inserer`, `top`, `pop` et `diminuer_prio`. Que deviennent les complexités de ces fonctions ? Qu'a-t-on gagné ? Qu'a-t-on perdu ?\n", "\n", "__Réponses et comparatif__ :\n", "\n", "Fonction ...... Listes en vrac ...... Listes triées\n", "\n", "`inserer` ...... $O(1)$ ...... $O(n)$\n", "\n", "`top` ...... $O(n)$ ...... $O(1)$\n", "\n", "`pop` ...... $O(n)$ ...... $O(n)$\n", "\n", "`diminuer_prio` ...... $O(n)$ ...... $O(n)$\n", "\n", "Bref, trier les listes n'est pas forcément souhaitable, et certainement pas souhaitable si on a beaucoup d'insertions à faire." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Une implémentation beaucoup plus efficace" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1 Arbres binaires presque complets" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous allons maintenant représenter un tas par ... un arbre, que nous allons implémenter comme ... une liste :-)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Définition__ : Un arbre binaire est __presque complet__ lorsque tous les niveaux de l'arbre sont remplis, sauf le dernier, pour lequel seuls les noeuds les plus à gauche du niveau contiennent une information. Les noeuds les plus à droite du dernier niveau peuvent être vides.\n", "\n", "Pour représenter un tel arbre on peut utiliser une liste $t$.\n", "\n", "- $t[0]$ est la racine de l'arbre.\n", "- $t[1]$ est le fils gauche de la racine.\n", "- $t[2]$ est le fils droit de la racine.\n", "- $t[3]$ est le fils gauche du fils gauche de la racine.\n", "- $t[4]$ est le fils droit du fils gauche de la racine.\n", "- $t[5]$ est le fils gauche du fils droit de la racine.\n", "- $t[6]$ est le fils droit du fils droit de la racine.\n", "- euh, normalement vous avez compris ...\n", "\n", "__Exercice__ : Dessinez un arbre binaire presque complet ayant 10 noeuds. Numérotez chaque noeud par son indice dans la liste qui représente l'arbre. Maintenant vous avez forcément compris.\n", "\n", "__Réponse__ : Au cas où vous n'avez toujours pas compris, il faut écrire les nombres de 0 à 9 de la gauche vers la droite et du haut vers le bas.\n", "\n", "__Exemple__ : la liste $t=[0, 1, 2, 3]$ peut être vue comme un arbre presque complet.\n", "\n", "- À la racine on trouve $0$.\n", "- Le fils gauche est $1$, le fils droit est $2$. \n", "- Le dernier niveau contient un unique noeud, le fils gauche du fils gauche de la racine, qui vaut $3$. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Plus généralement, le fils gauche (s'il existe) du noeud stocké en position $k$ dans la liste $t$ est le noeud stocké en position $2k+1$, le fils droit est stocké en position $2k+2$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def fils_gauche(n): return 2 * n + 1\n", "def fils_droit(n): return 2 * n + 2\n", "def pere(n): return (n - 1) // 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : Expliquez la fonction `pere`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Soit $t$ un arbre binaire presque complet possédant $n$ noeuds. La hauteur de $t$ est $h(t)=\\lfloor\\lg(n+1)\\rfloor$ où $\\lg$ est le logarithme en base 2. \n", "\n", "On convient ici que la hauteur de l'arbre vide est 0, et que la hauteur d'un arbre ayant un unique noeud est 1.\n", "\n", "__Démonstration__ : Une \"vraie\" preuve se ferait par récurrence sur la hauteur. Mais je préfère une explication plus \"physique\". Soit $k=\\lfloor\\lg(n+1)\\rfloor$. On a $2^k\\le n + 1<2^{k+1}$. \n", "\n", "Pour $j=0,\\ldots,k-1$, le niveau $j$ de l'arbre $t$ contient $2^j$ noeuds. Cela donne au total \n", "\n", "$$\\sum_{j=0}^{k-1}2^j=2^k-1$$\n", "\n", "noeuds. Il reste donc encore des noeuds à placer donc nous avons au moins encore un niveau dans l'arbre. Combien précisément nous reste-t-il de noeuds à placer ? Eh bien \n", "\n", "$$n-2^k+1<2^{k+1}-2^k=2^k$$\n", "\n", "Ils tiennent donc tous sur le $k$ième niveau de l'arbre. Notre arbre est bien de hauteur $k$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Définition__ : Soit $t$ un arbre binaire presque complet. On dit que $t$ est un tas lorsque\n", "\n", "- $t$ est vide, ou bien\n", "- Le fils gauche et le fils droit de $t$ sont eux-mêmes des tas, et les \"valeurs\" de leurs noeuds sont supérieures à la \"valeur\" de la racine de $t$.\n", "\n", "La dernière condition équivaut à\n", "\n", "- Pour tout noeud de $t$, le fils gauche et le fils droit de ce noeud ont une \"valeur\" supérieure à celle du noeud." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrivons une fonction qui prend une liste de couples $(x, p)$ (objet, priorité) en paramètre et renvoie `True` si cette liste représente un arbre binaire presque complet, les \"valeurs\" des noeuds étant bien entendu les valeurs de la priorité $p$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def verifier_tas(t):\n", " n = len(t)\n", " if n == 0: return True\n", " else:\n", " for k in range(n):\n", " fg = fils_gauche(k)\n", " fd = fils_droit(k)\n", " if fg < n and prio(t[k]) > prio(t[fg]): return False\n", " if fd < n and prio(t[k]) > prio(t[fd]): return False\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Remarque__ : `prio((a, b))`, c'est $a$ ou c'est $b$ :-) ? Sans importance, un grand merci à la fonction `prio`\n", " !!!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Euh, je me suis avancé un peu vite. Pour tester il faut savoir ..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t = [('a', 0), ('b', 1) , ('c', 2), ('d', 3)]\n", "verifier_tas(t)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "verifier_tas([('a', 0), ('b', 3) , ('c', 1), ('d', 2)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Trouver un objet de plus petite priorité dans un tas est alors immédiat : il s'agit de sa racine." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def top(t): \n", " if len(t) == 0: raise Exception('Tas vide')\n", " else: return t[0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "top(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.2 Insérer un objet" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour insérer un objet $x$ dans le tas $t$, représenté par une liste, on l'ajoute avec sa priorité en fin de liste. Évidemment, un tel ajout a de fortes chances d'être incompatible avec la structure de tas ! On fait donc remonter $x$ dans l'arbre jusqu'à la bonne position : on compare la priorité de $x$ avec celle de son père et on procède à un éventuel échange si le père de $x$ a une priorité plus grande que celle de $x$. Puis on recommence avec le père et le grand-père de $x$, etc. C'est la fonction `bubble_up` qui se charge de faire remonter $x$ à la bonne position." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inserer(t, x, p):\n", " t.append((x, p))\n", " bubble_up(t, len(t) - 1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def bubble_up(t, k):\n", " while k > 0 and prio(t[k]) < prio(t[pere(k)]):\n", " t[k], t[pere(k)] = t[pere(k)], t[k]\n", " k = pere(k)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : la complexité en pire cas de `inserer` est $O(\\log n)$ où $n$ est le nombre de noeuds de $t$.\n", "\n", "__Démonstration__ : la fonction `bubble_up` effectue une série de comparaisons sur les ancêtres d'un noeud. Le nombre d'ancêtres étant majoré par la hauteur de $t$, `inserer` effectue au plus $h(t)$ comparaisons, d'où le résultat.." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `file_aleatoire` que nous avons écrite il y a un certain temps utilise maintenant la nouvelle fonction `inserer`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t = file_aleatoire(10)\n", "print(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notre fonction d'insertion fabrique-t-elle bien des tas ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "verifier_tas(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.4 Supprimer un objet de priorité minimale" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour supprimer un objet $x$ de plus petite priorité (la racine) dans le tas $t$ :\n", "\n", "- On remplace la racine de $t$ sa feuille la plus à droite.\n", "- On supprime la feuille en question.\n", "- La racine viole alors peut-être la structure de tas : on l'échange si nécessaire avec celui de ses deux fils qui a la plus petite priorité, puis on recommence avec le fils concerné, etc. \n", "\n", "La fonction `bubble_down` réalise le troisième point." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def pop(t):\n", " n = len(t)\n", " if n == 0: raise Exception('Tas vide')\n", " else:\n", " x = t[0]\n", " t[0] = t[n - 1]\n", " t.pop()\n", " bubble_down(t, 0)\n", " return x" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def bubble_down(t, k):\n", " while True:\n", " i = k\n", " fg = fils_gauche(k)\n", " if fg < len(t) and prio(t[fg]) < prio(t[i]): i = fg\n", " fd = fils_droit(k)\n", " if fd < len(t) and prio(t[fd]) < prio(t[i]): i = fd\n", " if i == k: break\n", " t[i], t[k] = t[k], t[i]\n", " k = i" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t = file_aleatoire(10)\n", "print(t)\n", "x, p = pop(t)\n", "print(x, p)\n", "print(t)\n", "print(verifier_tas(t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : la complexité en pire cas de `pop` est $O(\\log n)$ où $n$ est le nombre de noeuds de $t$.\n", "\n", "__Démonstration__ : la fonction `bubble_down` effectue une série de comparaisons sur un chemin dans l'arbre qui part de la racine. Le nombre de noeuds sur un tel chemin étant majoré par la hauteur de $t$, la fonction effectue au plus $2h$ comparaisons où $h$ est la hauteur de l'arbre, d'où le résultat." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.5 Diminuer la priorité d'un objet" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'est là que le bât blesse : si nous voulons diminuer la priorité de l'objet $x$ dans le tas $t$ il va d'abord falloir trouver $x$. Mais où est-il ? Le mieux que l'on puisse faire est d'écrire une fonction de complexité $O(n)$, ce qui est __insoutenable__. \n", "\n", "__Règle__ : Un algorithme c'est comme un troupeau de moutons. La vitesse du troupeau c'est celle du mouton à 3 pattes.\n", "\n", "Toutes les opérations sur les tas se font en complexité logarithmique ... sauf le mouton à 3 pattes `diminuer_priorite`. Il va donc falloir revoir notre structure de données :-(. Rassurez-vous, nous n'allons pas tout revoir ; nous allons juste compléter la structure que nous avons déjà.\n", "\n", "Avant de nous atteler à cette tâche, petite digression : une application inattendue des tas est un algorithme de tri, appelé ... le __tri par tas__." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Le tri par tas" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.1 Comment ça marche ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soit $s$ une liste que l'on désire trier par ordre croissant.\n", "\n", "- On insère les éléments de $s$ comme priorités d'objets quelconques dans un tas $t$ initialement vide (les objets en eux-mêmes n'ont pas d'intérêt).\n", "- On extrait un à un du tas les éléments de $t$ et on insère leur priorité dans une liste initialement vide.\n", "\n", "L'opération d'extraction récupère à chaque itération le plus petit élément du tas. On obtient donc une liste triée." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def tri_tas(s):\n", " t, s1 = [], []\n", " for p in s: inserer(t, None, p)\n", " while not(est_vide(t)): s1.append(prio(pop(t)))\n", " return s1" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "s = random_list(100)\n", "print(s)\n", "s1 = tri_tas(s)\n", "print(s1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : La fonction `tri_tas` a une complexité en $O(n\\log n)$ où $n$ est le nombre d'objets à trier.\n", "\n", "__Démonstration__ : À la $k$ième itération de la boucle des insertions, le tas possède $k$ noeuds. La $k$ième insertion effectue donc au plus $\\lfloor\\lg(k+1)\\rfloor\\le \\lg(k+1)$ comparaisons. Le nombre total de comparaisons est donc majoré par \n", "\n", "$$\\sum_{k=0}^{n-1}\\lg(k+1)=\\sum_{k=1}^{n}\\lg(k)\\sim n\\lg n$$\n", "\n", "La boucle des extractions s'étudie de la même façon, avec un nombre de comparaisons majoré par \n", "\n", "$$\\sum_{k=0}^{n-1}2\\lg(k+1)\\sim 2n\\lg n$$\n", "\n", "Ainsi, le nombre total de comparaisons effectué par `tri_tas` est majoré par \n", "\n", "$$C_n\\sim 3n\\lg n$$\n", "\n", "Le tri par tas est donc un algorithme de tri efficace. L'implémentation que nous avons donnée ci-dessus fait des recopies de données (création d'un tas, objets inutiles), mais ceci peut être évité pour améliorer la \"constante cachée\" dans la complexité de l'algorithme. Je n'en parlerai pas ici." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Représentation finale des tas" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous y voilà. Nous allons écrire une __classe__ `Tas`. L'idée pour pouvoir efficacement diminuer la priorité d'un objet est de savoir OÙ se trouve l'objet dans le tas. Un objet $t$ de la classe `Tas` possède donc un __dictionnaire__, son champ `dico`. Si $x$ est un objet du tas, alors `t.dico[x]` est l'indice de l'objet $x$ dans la liste qui stocke les objets du tas.\n", "\n", "Plutôt que de stocker une liste de couples, un objet de la classe `Tas` possède \n", "- un champ `data` qui contient les objets du tas\n", "- un champ `prio` qui contient les priorités des objets.\n", "\n", "L'essentiel du code ci-dessous est une recopie de ce qui a déjà été fait dans le notebook avec quelques adaptations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.1 Le code" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La classe `Tas` possède un certain nombre de méthodes.\n", "\n", "- `__init__` est le constructeur. Il permet de créer un nouveau tas, vide.\n", "- `echanger` échange dans le tas les objets situés aux indices $i$ et $j$. La fonction se charge d'échanger les objets et les priorités, et de mettre à jour le dictionnaire.\n", "- `top` renvoie un objet de plus petite priorité, ainsi que sa priorité.\n", "- `pop` supprime un objet de priorité minimale et le renvoie.\n", "- `inserer` insère un objet $x$ avec la priorité $p$.\n", "- `diminuer_prio` diminue la priorité de l'objet $x$ à la valeur $p$.\n", "\n", "- Il y a aussi, bien entendu, les méthodes `bubble_up` et `bubble_down`, analogues aux fonctions du même nom déjà étudiées plus haut.\n", "\n", "- Enfin, les méthodes `verifier_tas` et `verifier_dico` permettent à un tas de s'auto-vérifier. Est-il bien un tas ? Son dictionnaire est-il cohérent ? Ces deux méthodes ont une complexité en $O(n)$, où $n$ est le nombre d'objets du tas. Elles sont censées renvoyer tout le temps `True`. Ou alors c'est que nous nous sommes trompés quelque part !\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La différence essentielle entre ces méthodes de la classe `Tas` et les fonctions que nous avons déjà écrites plus haut réside dans le fait que le dictionnaire doit garder la trace de la positions des objets. Chaque fois qu'un objet $x$ est placé à la position $i$, on affecte à `dico[x]` la valeur $i$. Si un échange d'objets est effectué, deux valeurs du dictionnaire doivent être modifiées.\n", "\n", "Je ne commenterai pas le code ci-dessous, sauf pour ce qui concerne la méthode `diminuer_prio`. Comment diminuer la priorité de l'objet $x$ à la valeur $p$ ?\n", "\n", "- On trouve la position $i$ de $x$ grâce au dictionnaire.\n", "- Si la priorité de $x$ est déjà inférieure à $p$, on lève une exception.\n", "- Sinon, on met la priorité de $x$ à $p$. Évidemment la structure de tas est provisoirement défaillante, mais un appel à `bubble_up` la rétablit en complexité $O(\\log n)$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Tas:\n", " \n", " def __init__(self):\n", " self.prio = []\n", " self.data = []\n", " self.dico = {}\n", " \n", " def __len__(self): return len(self.data)\n", " \n", " def echanger(self, i, j):\n", " self.prio[i], self.prio[j] = self.prio[j], self.prio[i]\n", " self.data[i], self.data[j] = self.data[j], self.data[i]\n", " self.dico[self.data[i]] = i\n", " self.dico[self.data[j]] = j\n", " \n", " def top(self): return (self.data[0], self.prio[0])\n", " \n", " def pop(self):\n", " n = len(self)\n", " if n == 0: raise Exception('Tas vide')\n", " else:\n", " p = self.prio[0]\n", " x = self.data[0]\n", " del self.dico[x]\n", " self.prio[0] = self.prio[n - 1]\n", " self.data[0] = self.data[n - 1]\n", " if len(self) > 1: self.dico[self.data[0]] = 0\n", " self.data.pop()\n", " self.prio.pop()\n", " self.bubble_down(0)\n", " return (p, x)\n", "\n", " def bubble_down(self, k):\n", " while True:\n", " i = k\n", " fg = fils_gauche(k)\n", " if fg < len(self) and self.prio[fg] < self.prio[i]: i = fg\n", " fd = fils_droit(k)\n", " if fd < len(self) and self.prio[fd] < self.prio[i]: i = fd\n", " if i == k: break\n", " self.echanger(i, k)\n", " k = i\n", " \n", " def inserer(self, x, p):\n", " self.prio.append(p)\n", " self.data.append(x)\n", " self.dico[x] = len(self) - 1\n", " self.bubble_up(len(self) - 1)\n", " \n", " def bubble_up(self, k):\n", " while k > 0 and self.prio[k] < self.prio[pere(k)]:\n", " self.echanger(k, pere(k))\n", " k = pere(k)\n", " \n", " def diminuer_prio(self, x, p):\n", " ix = self.dico[x]\n", " if self.prio[ix] < p:\n", " raise Exception('Priorité trop grande')\n", " else:\n", " self.prio[ix] = p\n", " self.bubble_up(ix)\n", " \n", " def verifier_tas(self):\n", " n = len(self)\n", " if n == 0: return True\n", " else:\n", " for k in range(n):\n", " fg = fils_gauche(k)\n", " fd = fils_droit(k)\n", " if fg < n and self.prio[k] > self.prio[fg]: return False\n", " if fd < n and self.prio[k] > self.prio[fd]: return False\n", " return True\n", " \n", " def verifier_dico(self):\n", " for x in t.dico:\n", " if t.data[t.dico[x]] != x: return False\n", " for i in range(len(self)):\n", " if t.dico[t.data[i]] != i: return False\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : Rajoutez à la classe `Tas` une méthode `augmenter_prio`. Puis écrivez une méthode `modifier_prio` qui appelle, selon les cas, la méthode `diminuer_prio` ou la méthode `augmenter prio`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.2 Tests" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vérifions que tout fonctionne. Créons des tas aléatoires et demandons leur de s'auto-vérifier." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def tas_aleatoire(n):\n", " s = random_list(n)\n", " s1 = random_list(n)\n", " t = Tas()\n", " for k in range(n):\n", " t.inserer(s1[k], s[k])\n", " return t" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def afficher_tas(t):\n", " print('indice objet prio')\n", " for k in range(len(t)):\n", " print('%-7d%-6s%-4s' % (k, t.data[k], t.prio[k]))\n", " print(t.dico)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "N = 10\n", "t = tas_aleatoire(N)\n", "print(t.verifier_tas(), t.verifier_dico())\n", "afficher_tas(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : Quelle est ci-dessus la plus grande valeur de $N$ pour laquelle la création d'un tas aléatoire demande moins de 10 secondes ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t = tas_aleatoire(10)\n", "t.diminuer_prio(2, -1)\n", "print(t.verifier_tas(), t.verifier_dico())\n", "afficher_tas(t)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t.pop()\n", "print(t.verifier_tas(), t.verifier_dico())\n", "afficher_tas(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : Évaluez la cellule ci-dessus jusqu'à ce que le tas soit vide. Puis évaluez encore une fois pour lever l'exception \"Tas vide\"." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3 Complexité des opérations de tas" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Admettons que les opérations sur les dictionnaires Python s'effectuent en complexité $O(1)$. C'est effectivement le cas dans des circonstances \"normales\" que je ne détaillerai pas. Dans ce cas, la méthode `echanger` a une complexité en $O(1)$. Il s'ensuit les complexités en pire cas ci-dessous (où $n$ est le nobre d'objets dans le tas) :\n", "\n", "- `__init__` : $O(1)$.\n", "- `echanger` : $O(1)$.\n", "- `top` : $O(1)$\n", "- `pop` : $O(\\log n)$\n", "- `inserer` : $O(\\log n)$\n", "- `diminuer_prio` : $O(\\log n)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.4 Peut-on faire mieux ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La réponse est __oui__, en utilisant des types d'arbres plus sophistiqués que les arbres binaires presque complets. Le lecteur intéressé pourra entre autres se documenter sur\n", "- les tas binomiaux\n", "- les tas de Fibonacci" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }