#!/usr/bin/env python # coding: utf-8 # # Table of Contents #
# # [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 !