#!/usr/bin/env python # coding: utf-8 # # Table of Contents #

1  ALGO1 : Introduction à l'algorithmique
2  Cours Magistral 1
2.1  Listes simplement chaînées
2.1.1  pop/push pour une structure de pile (FILO)
2.1.2  add/remove pour une structure de file (FIFO)
2.2  Listes doublement chaînées
2.2.1  Exemple
2.3  Implémenter une file d'attente avec deux piles
2.4  File de priorité
2.5  Implémentation d'un tas binaire
2.5.1  Naïve : tableau trié !
2.5.2  Intelligente : tas binaire min équilibré
2.6  Tri par tas
2.6.1  Remarques
2.6.2  Tri par tas
2.7  Test numérique de l'efficacité du tri par tas
2.8  Évaluation numérique de la complexité des opérations du tas binaire
2.9  Conclusion
# # [ALGO1 : Introduction à l'algorithmique](https://perso.crans.org/besson/teach/info1_algo1_2019/) # # - [Page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/) : https://perso.crans.org/besson/teach/info1_algo1_2019/ # - Magistère d'Informatique de Rennes - ENS Rennes - Année 2019/2020 # - Intervenants : # + Cours : [Lilian Besson](https://perso.crans.org/besson/) # + Travaux dirigés : [Raphaël Truffet](http://perso.eleves.ens-rennes.fr/people/Raphael.Truffet/) # - Références : # + [Open Data Structures](http://opendatastructures.org/ods-python.pdf) # # Cours Magistral 1 # ## Listes simplement chaînées # ![figures/CM1_SimplyLinkedList.png](figures/CM1_SimplyLinkedList.png) # On utilise une petite classe qui va encapsuler la donnée courante, et le pointeur vers la liste suivante. # In[58]: class ListNode: def __init__(self, data, link=None): self.data = data self.link = link def __str__(self): return "[{}|.-]->{}".format(str(self.data), "" if self.link is None else str(self.link)) # In[111]: example_node = ListNode(0) print(example_node) example_node2 = ListNode(1, link=example_node) print(example_node2) # On peut parcourir $i$ fois cette structure linéaire : # In[118]: def traverse(one_node, i): assert i >= 0 if i == 0: return one_node.data else: return traverse(one_node.link, i-1) # In[121]: [ traverse(example_node, 0) ] # traverse(example_node, 1) [ traverse(example_node2, 1), traverse(example_node2, 0) ] # On implémente les opérations push/pop et add/remove : # In[124]: class LinkedList: def __init__(self): self._head = None self._tail = None self._length = 0 def __len__(self): return self._length def isempty(self): return len(self) == 0 # Methods push/pop for Stack (FIFO) data structure def _addfirst(self, item): self._head = ListNode(item, self._head) # if it has only one element, we make it loop if self._tail is None: self._tail = self._head # but the structure knows it has only element: length = 1 self._length += 1 def push(self, item): """ Insert a new element as the new head, in O(1) time.""" self._addfirst(item) def _removefirst(self): item = self._head.data # get the current head data self._head = self._head.link # compress the head if self._head is None: # if link was None, then list is now empty self._tail = None self._length -= 1 # remove one element return item def pop(self): """ Get and remove the head, in O(1) time.""" return self._removefirst() # Methods add/remove for Queue (FILO) data structure def _addlast(self, item): if self._head is None: # if list is empty, just add at the beginning self._addfirst(item) else: # or create new element, and change tail self._tail.link = ListNode(item) self._tail = self._tail.link self._length += 1 def add(self, item): """ Insert a new element at the end of the list, in O(n) time.""" self._addlast(item) remove = pop def removelast(self): if self._head is self._tail: return self._removefirst() else: currentnode = self._head while currentnode.link is not self._tail: currentnode = currentnode.link item = self._tail.data self._tail = currentnode self._tail.link = None self._length -= 1 return item # Access to i-th element, in O(i) def __getitem__(self, index): if not (0 <= index < len(self)): raise IndexError return traverse(self._head, index) def items(self): n = len(self) return [ self[i] for i in range(len(self)) ] # Method to print the list def __str__(self) -> str: if self.isempty(): return "[]" return str(self._head) # Deux exemples, que l'on visualise encore mieux sur [PythonTutor.com](http://pythontutor.com/live.html#mode=edit). # ### `pop`/`push` pour une structure de pile (FILO) # In[125]: example_list = LinkedList() print(example_list) example_list.push(0) print(example_list) example_list.push(1) print(example_list) example_list.push(2) print(example_list) example_list.push(3) print(example_list) print(example_list.items()) for i in range(len(example_list)): print("{}th value is = {}".format(i, example_list[i])) example_list.pop() print(example_list) example_list.pop() print(example_list) example_list.pop() print(example_list) example_list.pop() print(example_list) # ### `add`/`remove` pour une structure de file (FIFO) # In[129]: example_list = LinkedList() print(example_list) example_list.add(0) print(example_list) example_list.add(1) print(example_list) example_list.add(2) print(example_list) example_list.add(3) print(example_list) print(example_list.items()) for i in range(len(example_list)): print("{}th value is = {}".format(i, example_list[i])) example_list.remove() print(example_list) example_list.remove() print(example_list) example_list.remove() print(example_list) example_list.remove() print(example_list) # ## Listes doublement chaînées # ![figures/CM1_DoublyLinkedList.png](figures/CM1_DoublyLinkedList.png) # On utilise une petite classe qui va encapsuler la donnée courante, et les deux pointeurs vers les listes suivante et précédente. # In[102]: class ListNodeDoublyLinked: def __init__(self, data, prev = None, link = None): self.data = data self.prev = prev self.link = link if prev is not None: self.prev.link = self if link is not None: self.link.prev = self def __str__(self): return "[{}]{}".format(str(self.data), "" if self.link is None else "<->{}".format(str(self.link))) # In[130]: class DoublyLinkedList: def __init__(self): self._head = None self._tail = None self._length = 0 def isempty(self): return self._length == 0 def __len__(self): return self._length # Add an element, in O(1) def _addbetween(self, item, before, after): node = ListNodeDoublyLinked(item, before, after) if after is self._head: self._head = node if before is self._tail: self._tail = node self._length += 1 def addfirst(self, item): """ Insert a new element as the beginning of the list, in O(1) time.""" self._addbetween(item, None, self._head) def addlast(self, item): """ Insert a new element as the end of the list, in O(1) time.""" self._addbetween(item, self._tail, None) # Remove an element, in O(1) def _remove(self, node): before, after = node.prev, node.link if node is self._head: self._head = after else: before.link = after if node is self._tail: self._tail = before else: after.prev = before self._length -= 1 return node.data def removefirst(self): """ Remove and return the beginning of the list, in O(1) time.""" return self._remove(self._head) def removelast(self): """ Remove and return the end of the list, in O(1) time.""" return self._remove(self._tail) # Access to i-th element, in O(i) def __iadd__(self, other): if other._head is None: return if self._head is None: self._head = other._head else: self._tail.link = other._head other._head.prev = self._tail self._tail = other._tail self._length = self._length + other._length # Clean up the other list. other.__init__() return self # Access to i-th element, in O(i) def __getitem__(self, index): if not (0 <= index < len(self)): raise IndexError return traverse(self._head, index) def items(self): n = len(self) return [ self[i] for i in range(len(self)) ] # Method to print the list def __str__(self) -> str: if self.isempty(): return "[]" return str(self._head) # Un exemple, que l'on visualise encore mieux sur [PythonTutor.com](http://pythontutor.com/live.html#mode=edit). # ### Exemple # In[131]: example_list = DoublyLinkedList() print(example_list) example_list.addfirst(0) print(example_list) example_list.addfirst(1) print(example_list) example_list.addfirst(2) print(example_list) example_list.addlast(100) print(example_list) example_list.addlast(101) print(example_list) example_list.addlast(102) print(example_list) print(list(example_list)) example_list.removefirst() print(example_list) example_list.removelast() print(example_list) example_list.removefirst() print(example_list) example_list.removelast() print(example_list) example_list.removefirst() print(example_list) example_list.removelast() print(example_list) # ## Implémenter une file d'attente avec deux piles # - On va utiliser deux piles (des `list` de Python) # In[109]: # https://github.com/jilljenn/tryalgo/blob/master/tryalgo/our_queue.py class Queue: """A FIFO queue - Complexity: + all operators in amortized constant time, + except __str__ which is linear """ def __init__(self): self.in_stack = [ ] # tail self.out_stack = [ ] # head def __len__(self): return len(self.in_stack) + len(self.out_stack) def push(self, obj): self.in_stack.append(obj) def pop(self): if not self.out_stack: # head is empty self.out_stack = self.in_stack[::-1] self.in_stack = [] return self.out_stack.pop() def __str__(self): return str(self.out_stack[::-1] + self.in_stack) # In[110]: queue = Queue() queue.push(0) print(queue) queue.push(1) print(queue) queue.push(2) print(queue) queue.push(3) print(queue) queue.pop() print(queue) queue.pop() print(queue) queue.pop() print(queue) # ## File de priorité # A propos… # ## Implémentation d'un tas binaire # ### Naïve : tableau trié ! # # On conserve le tableau trié en insérant chaque nouvel élément par une insertion à sa bonne position (avec des inversions locales), comme dans le tri par tas. # In[187]: def swap(array, i, j): array[i], array[j] = array[j], array[i] # In[198]: class OurNaiveHeap: """ min naive heap * heap: is the actual heap, containing the sorted value * n: size of the heap Complexity: init O(n^2), len O(1), other operations O(n) in all cases """ def __init__(self, items=None): self.heap = [] # index 0 will be ignored if items is not None: for x in items: self.push(x) def __len__(self): return len(self.heap) def push(self, x): """Insert new element x in the heap.""" # add a new element self.heap.append(x) # then insert it, from the end, to its correct location position = len(self) - 1 while position > 0 and self.heap[position - 1] > self.heap[position]: swap(self.heap, position - 1, position) position -= 1 def pop(self): """Remove and return smallest element""" # move heap[0] to heap[n] and copy heap[1:n] to heap[0:n-1] for position in range(len(self) - 1): swap(self.heap, position, position + 1) smallest_element = self.heap.pop() # remove last element return smallest_element # ### Intelligente : tas binaire min équilibré # In[199]: class OurHeap: """ min heap * heap: is the actual heap, heap[1] = index of the smallest element * rank: inverse of heap with rank[x]=i iff heap[i]=x * n: size of the heap :complexity: init O(n log n), len O(1), other operations O(log n) in expectation and O(n) in worst case, due to the usage of a dictionary """ def __init__(self, items=None): self.heap = [None] # index 0 will be ignored if items is not None: for x in items: self.push(x) def __len__(self): return len(self.heap) - 1 def push(self, x): """Insert new element x in the heap.""" i = len(self.heap) self.heap.append(x) # add a new leaf self.up(i) # maintain heap order def pop(self): """Remove and return smallest element""" root = self.heap[1] x = self.heap.pop() # remove last leaf if self: # if heap is not empty self.heap[1] = x # put last leaf to root self.down(1) # maintain heap order return root def up(self, i): """The value of heap[i] has decreased. Maintain heap invariant.""" x = self.heap[i] while i > 1 and x < self.heap[i // 2]: self.heap[i] = self.heap[i // 2] i //= 2 self.heap[i] = x # insertion index found def down(self, i): """the value of heap[i] has increased. Maintain heap invariant.""" x = self.heap[i] n = len(self.heap) while True: left = 2 * i # climb down the tree right = left + 1 if (right < n and self.heap[right] < x and self.heap[right] < self.heap[left]): self.heap[i] = self.heap[right] i = right elif left < n and self.heap[left] < x: self.heap[i] = self.heap[left] i = left else: self.heap[i] = x # insertion index found return # ## Tri par tas # Dès que l'on a une implémentation d'un tas (min), on peut facilement trier un tableau `T` de la façon suivante : # # - Entrée : un tableau `T` de taille `n` # - Créer tas `mon_tas` # - Pour chaque valeur `T[i]` dans le tableau `T` : # + entasser `T[i]` dans `mon_tas` # - Créer un tableau `T_trie` de même taille que `T` (`n`) # - Initialiser `i = 0` # - Tant que `mon_tas` n'est pas vide : # + extraire le minimum du tas : `nouveau_min_du_tas <- extraireMin(mon_tas)` # + placer ce minimum à la `i`ème position dans le nouveau tableau : `T_trie[i] = nouvea_min_du_tas` # + `i += 1` # - Sortie : Le tableau `T_trie` est le tableau `T` trié par ordre croissant. # # ### Remarques # - L'avantage du tri par tas est que l'on peut aussi effectuer toutes ces opérations *en place* (i.e., en utilisant le tableau `T` et pas de mémoire supplémentaire). # - On utilise un tri max pour trier en ordre décroissant, ou alors on renverse juste le tableau `T_trie` à la fin. # ### Tri par tas # L'algorithme est indépendent de la structure de tas que l'on utilise ! # In[208]: def heapSort(array, heapStructure=OurHeap): n = len(array) heap = heapStructure() for i in range(n): heap.push(array[i]) sorted_array = [ None ] * n # taille n i = 0 while heap: # while not empty sorted_array[i] = heap.pop() i += 1 return sorted_array def insertionSort(array): return heapSort(array, heapStructure=OurNaiveHeap) # In[201]: example_array = [10, 9, 19] sorted(example_array) heapSort(example_array) insertionSort(example_array) # In[237]: example_array = list(range(2019)) + list(range(2019)) # twice the numbers from 0 to 2018 import random random.shuffle(example_array) get_ipython().run_line_magic('timeit', 'sorted(example_array)') get_ipython().run_line_magic('timeit', 'heapSort(example_array)') get_ipython().run_line_magic('timeit', 'insertionSort(example_array)') # ## Test numérique de l'efficacité du tri par tas # In[160]: import matplotlib as mpl mpl.rcParams['figure.figsize'] = (10, 7) mpl.rcParams['figure.dpi'] = 120 import seaborn as sns sns.set(context="notebook", style="whitegrid", palette="hls", font="sans-serif", font_scale=1.1) import matplotlib.pyplot as plt # In[145]: import random random.seed(1234) # On va générer des tableaux aléatoires : # In[146]: def random_array_of_int(max_int=10000, length=1000): return [ random.randint(0, max_int) for _ in range(length) ] # In[147]: random_array_of_int(max_int=20, length=10) # On peut facilement mesurer le temps d'exécution d'une fontion de tri, sur des tableaux aléatoires # In[171]: import timeit # In[215]: try: from tqdm import tqdm_notebook except ImportError: def tqdm_notebook(iterator, *args, **kwargs): return iterator # In[216]: def time_a_sort_function(sort_function, sort_function_name, values_n, number=1000, max_int=1000000): return [ timeit.timeit("{}(random_array_of_int(max_int={}, length={}))".format(sort_function_name, max_int, n), globals={ 'random_array_of_int': random_array_of_int, sort_function_name: sort_function, }, number=number, ) for n in tqdm_notebook(values_n) ] # Comparons notre tri par tas avec la fonction `sorted()` de Python : # In[309]: small_values_n = [10, 100, 500] + list(range(1000, 5000, 1000)) big_values_n = list(range(6000, 100000, 4000)) # very_big_values_n = list(range(100000, 5000000, 100000)) values_n = small_values_n + big_values_n #+ very_big_values_n # In[310]: times_sorted = time_a_sort_function(sorted, "sorted", values_n, number=100) # In[311]: times_heapSort = time_a_sort_function(heapSort, "heapSort", values_n, number=100) # In[312]: times_insertionSort = time_a_sort_function(insertionSort, "insertionSort", small_values_n, number=20) # In[313]: plt.figure() plt.xlabel("Taille du tableau d'entrée $n$") plt.ylabel("Temps en secondes") plt.title("Comparaison des tris builtin, par tas ou par insertion") plt.plot(values_n, times_sorted, "d-", label="Builtin", lw=5, ms=12) plt.plot(values_n, times_heapSort, "o-", label="Par tas", lw=5, ms=12) plt.plot(small_values_n, times_insertionSort, ">-", label="Par insertion", lw=5, ms=12) plt.legend() plt.show() # Attention : Trier des nombres tout petit peut être effectué en temps linéaire (*bin sort*) : # In[136]: get_ipython().run_line_magic('timeit', 'sorted(random_array_of_int(max_int=10, length=100))') get_ipython().run_line_magic('timeit', 'sorted(random_array_of_int(max_int=10, length=1000))') get_ipython().run_line_magic('timeit', 'sorted(random_array_of_int(max_int=10, length=10000))') # In[148]: get_ipython().run_line_magic('timeit', 'sorted(random_array_of_int(max_int=1000, length=100))') get_ipython().run_line_magic('timeit', 'sorted(random_array_of_int(max_int=1000, length=1000))') get_ipython().run_line_magic('timeit', 'sorted(random_array_of_int(max_int=1000, length=10000))') # ## Évaluation numérique de la complexité des opérations du tas binaire # # On peut évaluer, sur des exemples, la complexité des opérations d'ajout et d'extraction du maximum que l'on a implémenté dans notre structure de tas binaire. # On a montré qu'elles sont toutes les deux en $\mathcal{O}(\log(n))$, mais peut-on le vérifier empiriquement ? # In[314]: import numpy as np # In[315]: def times_push_and_pop(values_n, number1=100, number2=100, max_int=1000_000): # create a random array for each value of n times_push = np.array([ np.mean([ timeit.timeit( "heap.push(random.randint(-{}, {}))".format(max_int, max_int), globals={ 'random_array_of_int': random_array_of_int, 'heap': heap, 'random': random, }, number=number1, ) / number1 for _ in range(number2) for heap in [ OurHeap(random_array_of_int(max_int=max_int, length=n)) ] ]) for n in tqdm_notebook(values_n, desc="push") ]) times_push_and_pop = np.array([ np.mean([ timeit.timeit( "heap.push(random.randint(-{}, {})); heap.pop()".format(max_int, max_int), globals={ 'random_array_of_int': random_array_of_int, 'heap': heap, 'random': random, }, number=number1, ) / number1 for _ in range(number2) for heap in [ OurHeap(random_array_of_int(max_int=max_int, length=n)) ] ]) for n in tqdm_notebook(values_n, desc="push & pop") ]) times_pop = times_push_and_pop - times_push return times_push, times_pop # In[316]: times_push_and_pop([10, 100, 1000], number1=100, number2=1000) # In[317]: def visualisation_temps_push_and_pop(values_n, **kwargs): times_push, times_pop = times_push_and_pop(values_n, **kwargs) plt.figure() plt.xlabel("Taille du tableau d'entrée $n$") plt.ylabel("Temps en micro-secondes") plt.title("Temps des opérations ajouterMax et retirerMax") plt.plot(values_n, 1e6 * times_push, "d-", label="ajouterMax", lw=5, ms=12) plt.plot(values_n, 1e6 * times_pop, "o-", label="retirerMax", lw=5, ms=12) plt.legend() plt.show() # In[319]: visualisation_temps_push_and_pop( [ 100, 500, 1000, 2000, 3000, 4000, 5000, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000, #110000, 120000, 130000, 140000, 150000, 160000, 170000, 180000, 190000, 200000, #300000, 400000, 500000, 600000, 700000, 800000, 900000, #1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 7000000, 8000000, 9000000, ], number1=100, number2=1000, ) # In[320]: visualisation_temps_push_and_pop( [ 100, 500, 1000, 2000, 3000, 4000, 5000, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000, 110000, 120000, 130000, 140000, 150000, 160000, 170000, 180000, 190000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, #1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 7000000, 8000000, 9000000, ], number1=20, number2=100, ) # ## Conclusion # # C'est bon pour aujourd'hui !