1A.algo - Arbre et Trie (correction)#

Links: notebook, html, python, slides, GitHub

Correction.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Exercice 1 #

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))

Exercice 2 #

import time
debut = time.perf_counter()
for k in mots :
    i = mots.index(k)
fin = time.perf_counter()
print ("recherche simple",fin - debut)

recherche simple 1.4759376217423303

Avec %timeit :

%timeit for k in mots : i = mots.index(k)

1 loop, best of 3: 1.41 s per loop

Exercice 3 : recherche dichotomique #

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)

dichotomie 0.07686653042216562

%timeit for k in mots : i = dicho(mots, k)

10 loops, best of 3: 57.4 ms per loop

Exercice 4 #

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)

simple 0.00046013522672971874 dicho 0.0013958005390772854 ratio 0.32965686274480016  ratio théorique  0.1003433318879937
simple 0.0017960668701348936 dicho 0.0025906126426864517 ratio 0.6932981181904454  ratio théorique  0.5017166594399687
simple 0.014991171476061993 dicho 0.00428319185030368 ratio 3.4999999999997926  ratio théorique  3.3447777295997914
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

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)

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 $N$ le nombre de mots dans la liste :

coût de la recherche simple : $O(N)$
coût de la recherche dichotomique : $O(\ln N)$

Le ratio $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 #

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)

{'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 #

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"))

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 :

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)

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 :

print_trie (build_trie( ["aaa"]) )

a
  a
    a

print_trie (build_trie( ["aaa", "aa"]) )

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.

print_trie (build_trie( ["aaa*"]) )

a
  a
    a
      *

print_trie (build_trie( ["aaa*", "aa*"]) )

Exercice 7 #

Soit $L$ la longueur maximale des mots et $C$ le nombre de lettres distinctes, avec un trie, le coût de la recherche est majoré par : $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).

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)

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

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)

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 $O(\ln n)$ mais en $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.

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)

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 :

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)

['alphabet', 'avant', 'avant après', 'milieu', 'zillion']
value=alphabet
value=avant
value=avant après
value=milieu
value=zillion

Liens

Contenu

Information

Sujet précédent

Sujet suivant