.. _td1acorrectionsession8rst: ==================================== 1A.algo - Arbre et Trie (correction) ==================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/td1a_algo/td1a_correction_session8.ipynb|*` Correction. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Exercice 1 ---------- .. code:: ipython3 import random def mot_alea (l) : l = [ chr(97+random.randint(0,25)) for i in range(l) ] return "".join(l) taille = 20 N = 10000 mots = [ mot_alea(taille) for _ in range (N) ] print(len(mots)) .. parsed-literal:: 10000 Exercice 2 ---------- .. code:: ipython3 import time debut = time.perf_counter() for k in mots : i = mots.index(k) fin = time.perf_counter() print ("recherche simple",fin - debut) .. parsed-literal:: recherche simple 1.4759376217423303 Avec ``%timeit`` : .. code:: ipython3 %timeit for k in mots : i = mots.index(k) .. parsed-literal:: 1 loop, best of 3: 1.41 s per loop Exercice 3 : recherche dichotomique ----------------------------------- .. code:: ipython3 def dicho (mots, x) : a = 0 b = len(mots)-1 while a < b : m = (a+b)//2 t = mots[m] if t < x : b = m-1 elif t == x : return m else : a = m+1 return a mots.sort() debut = time.perf_counter() for k in mots : i = dicho(mots, k) fin = time.perf_counter() print ("dichotomie",fin - debut) .. parsed-literal:: dichotomie 0.07686653042216562 .. code:: ipython3 %timeit for k in mots : i = dicho(mots, k) .. parsed-literal:: 10 loops, best of 3: 57.4 ms per loop Exercice 4 ---------- .. code:: ipython3 import math for N in [10, 100, 1000, 10000, 100000] : mots = [ mot_alea(taille) for _ in range (N) ] tolook = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,1000) ] mots.sort() debut = time.perf_counter() for k in tolook : i = mots.index(k) fin = time.perf_counter() ds = fin-debut debut = time.perf_counter() for k in tolook : i = dicho(mots, k) fin = time.perf_counter() dd = fin-debut print(N, "simple",ds, "dicho",dd, "ratio", ds / max(dd, 1), " ratio théorique ", len(mots)/math.log(len(mots)) * math.log(2)/30) .. parsed-literal:: 10 simple 0.00046013522672971874 dicho 0.0013958005390772854 ratio 0.32965686274480016 ratio théorique 0.1003433318879937 100 simple 0.0017960668701348936 dicho 0.0025906126426864517 ratio 0.6932981181904454 ratio théorique 0.5017166594399687 1000 simple 0.014991171476061993 dicho 0.00428319185030368 ratio 3.4999999999997926 ratio théorique 3.3447777295997914 10000 simple 0.139653179487377 dicho 0.005854322726703387 ratio 23.854711468224224 ratio théorique 25.085832971998425 100000 simple 5.177541637747854 dicho 0.007615751164344431 ratio 679.8464821156667 ratio théorique 200.68666377598748 .. code:: ipython3 for N in [10, 100, 1000, 10000, 100000] : print("N=",N) mots = [ mot_alea(taille) for _ in range (N) ] tolook = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,1000) ] mots.sort() %timeit for k in tolook : i = mots.index(k) %timeit for k in tolook : i = dicho(mots, k) .. parsed-literal:: N= 10 1000 loops, best of 3: 320 µs per loop 1000 loops, best of 3: 1.29 ms per loop N= 100 1000 loops, best of 3: 1.6 ms per loop 100 loops, best of 3: 2.63 ms per loop N= 1000 100 loops, best of 3: 14.1 ms per loop 100 loops, best of 3: 4.03 ms per loop N= 10000 10 loops, best of 3: 144 ms per loop 100 loops, best of 3: 5.63 ms per loop N= 100000 1 loop, best of 3: 5.02 s per loop 100 loops, best of 3: 7.12 ms per loop Soit :math:`N` le nombre de mots dans la liste : - coût de la recherche simple : :math:`O(N)` - coût de la recherche dichotomique : :math:`O(\ln N)` Le ratio :math:`N/\ln N` mesuré en pratique devrait être sensiblement égal au ratio théorique à un facteur multiplication près. Le trie du tableau qui précède la recherche dichotomique n’est pas pris en compte. Plus on effectue de recherche, plus son coût devient marginal. Ce coût explique néanmoins pourquoi on ne fait pas toujours une recherche dichotomique. Exercice 5 : trie ----------------- .. code:: ipython3 def build_trie(mots) : trie = { } for m in mots : r = trie for c in m : if c not in r : r[c] = { } r = r[c] return trie mots = [ "aaa", "aba", "aab", "baa", "bbb", "bba", "bab" ] trie = build_trie(mots) print(trie) .. parsed-literal:: {'a': {'a': {'a': {}, 'b': {}}, 'b': {'a': {}}}, 'b': {'a': {'a': {}, 'b': {}}, 'b': {'a': {}, 'b': {}}}} Quelques explications supplémentaires concernant cette correction : - `Question à propos de trie `__ Exercice 6 : recherche dans un trie ----------------------------------- .. code:: ipython3 def lookup(trie, m) : r = trie for c in m : if c in r : r = r[c] else : return False return True for k in mots : print(k, lookup(trie, k)) print("bcc", lookup(trie, "bcc")) .. parsed-literal:: aaa True aba True aab True baa True bbb True bba True bab True bcc False Pour illustrer la structure d’arbre du trie, on l’affiche avec la fonction suivante : .. code:: ipython3 def print_trie(trie, niveau = 0): for k,v in sorted(trie.items()): print(" " * niveau + k) if len(v) > 0 : print_trie(v, niveau+1) print_trie(trie) .. parsed-literal:: a a a b b a b a a b b a b Il reste un inconvénient à cette représentation. Si on construire le trie pour le mot ``["aaa"]`` ou les mots ``["aa","aaa]"``, on obtient le même trie : .. code:: ipython3 print_trie (build_trie( ["aaa"]) ) .. parsed-literal:: a a a .. code:: ipython3 print_trie (build_trie( ["aaa", "aa"]) ) .. parsed-literal:: a a a Pour éviter cela, le plus simple est de représenter la fin d’un mot comme un caractère à part entière. .. code:: ipython3 print_trie (build_trie( ["aaa*"]) ) .. parsed-literal:: a a a * .. code:: ipython3 print_trie (build_trie( ["aaa*", "aa*"]) ) .. parsed-literal:: a a * a * Exercice 7 ---------- Soit :math:`L` la longueur maximale des mots et :math:`C` le nombre de lettres distinctes, avec un trie, le coût de la recherche est majoré par : :math:`O(L \ln C)`. On reprend le code de l’exercice 5 et on ajoute le code associé au trie. On effectue 10000 recherches au lieu de 1000 pour avoir une meilleure estimation de la différence (pour vous en convaincre, il suffit comparer les temps obtenus par deux exécution de ce même code). .. code:: ipython3 for N in [10, 100, 1000, 10000, 100000, 200000, 400000] : mots = [ mot_alea(taille) for _ in range (N) ] tolook = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,10000) ] trie = build_trie(mots) mots.sort() debut = time.perf_counter() for k in tolook : i = dicho(mots, k) fin = time.perf_counter() dd = fin-debut debut = time.perf_counter() for k in tolook : i = lookup(trie, k) fin = time.perf_counter() dt = fin - debut print(N, "dicho",dd, "trie", dt) .. parsed-literal:: 10 dicho 0.014463042289250438 trie 0.020240390721525614 100 dicho 0.03220732769624135 trie 0.019780683129752674 1000 dicho 0.059169712496739635 trie 0.04887183480633439 10000 dicho 0.05923257483719624 trie 0.04443469436714054 100000 dicho 0.07402190260785346 trie 0.0492733840422801 200000 dicho 0.07787318313937419 trie 0.05416595572353344 400000 dicho 0.0827054582899791 trie 0.06291493955595229 .. code:: ipython3 for N in [10, 100, 1000, 10000, 100000, 200000, 400000] : print("N=",N) mots = [ mot_alea(taille) for _ in range (N) ] tolook = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,10000) ] trie = build_trie(mots) mots.sort() %timeit for k in tolook : i = dicho(mots, k) %timeit for k in tolook : i = lookup(trie, k) .. parsed-literal:: N= 10 100 loops, best of 3: 12.7 ms per loop 100 loops, best of 3: 17.7 ms per loop N= 100 10 loops, best of 3: 26.1 ms per loop 100 loops, best of 3: 17.9 ms per loop N= 1000 10 loops, best of 3: 40.1 ms per loop 10 loops, best of 3: 32.4 ms per loop N= 10000 10 loops, best of 3: 57.1 ms per loop 10 loops, best of 3: 44.5 ms per loop N= 100000 10 loops, best of 3: 97.9 ms per loop 10 loops, best of 3: 54 ms per loop N= 200000 10 loops, best of 3: 77 ms per loop 10 loops, best of 3: 50 ms per loop N= 400000 10 loops, best of 3: 80.8 ms per loop 10 loops, best of 3: 52.7 ms per loop Encore une fois, le temps de construction du trie n’est pas pris en compte. Plus il y a de recherche à effectuer, plus il devient négligeable. Le dictionnaire est un object courant dans la plupart des languages. En python, celui-ci utilise une `table de hachage `__ et le coût d’accès à un élément n’est pas en :math:`O(\ln n)` mais en :math:`O(n)` (voir `time complexity `__). En C++, le dictionnaire (ou `map `__) utilise un arbre binaire et l’accès à un élément a un coût logarithmique : `Standard C++ Containers `__. Plus en détails --------------- La recherche dichotomique est équivalente à celle opérée avec un `arbre binaire de recherche `__ (si ce dernier est `équilibré `__ ou `arbre rouge/noir `__). Ce dernier consiste à classer les éléments par ordre alphabétique. Un arbre est souvent représenté par une classe et non par un dictionnaire comme la dernière partie de cette session le laissait supposer. .. code:: ipython3 class Arbre: def __init__(self, value): self.value = value self.children = [ ] def add_child(self, child): self.children.append(child) def __str__(self): rows = [ "value={0}".format(self.value) ] for c in self.children: s = str(c) lines = [ " " + l for l in s.split("\n") ] rows.extend(lines) return "\n".join(rows) root = Arbre("racine") child1 = Arbre("child 1") child1.add_child ( Arbre("child 2") ) child1.add_child ( Arbre("child 1000") ) root.add_child(child1) root.add_child( Arbre ("child 3") ) print(root) .. parsed-literal:: value=racine value=child 1 value=child 2 value=child 1000 value=child 3 Les arbres sont des graphes particuliers car il ne contiennent pas de cycles. Il est possible de parcourir les noeuds, de les numéroter. Ils sont très utilisés en machine learning avec les `arbres de décisions `__ ou les `random forests `__. Ils sont parfois cachés comme dans le cas de la recherche dichotomique qui peut être implémentée à partir d’une structure d’arbre. Dans le cas de le recherche dichotomique, on suppose que le nombre de noeuds fils est toujours 2. L’ordre alphabétique est le suivant : noeuds fils 1, noeud courant, noeud fils 2. Les deux noeuds fils pourraient être nuls. L’implémentation de l’arbre serait la suivante : .. code:: ipython3 class ArbreDicho: def __init__(self, value): self.value = value self.before = None self.after = None def __str__(self): return "value={0}".format(self.value) def add_before(self, child): self.before = child def add_after(self, child): self.after = child def find(self, word): if self.value == word : return self elif word < self.value : if self.before is None : return None else : return self.before.find(word) else : if self.after is None : return None else : return self.after.find(word) def sorted_list(self): res = [ ] if self.before is not None: res.extend ( self.before.sorted_list() ) res.append(self.value) if self.after is not None: res.extend ( self.after.sorted_list() ) return res # on crée un arbre dont les noeuds vérifient la propriété énoncé plus haut (les mots apparaissent dans le bon ordre) root = ArbreDicho("milieu") root.add_before(ArbreDicho("avant")) root.add_after(ArbreDicho("zillion")) root.before.add_before(ArbreDicho("alphabet")) root.before.add_after(ArbreDicho("avant après")) # on vérifie que c'est bien le cas all = root.sorted_list() assert all == sorted(all) print(all) # on effectue la recherche for a in all: f = root.find(a) print(f) .. parsed-literal:: ['alphabet', 'avant', 'avant après', 'milieu', 'zillion'] value=alphabet value=avant value=avant après value=milieu value=zillion