Initiation à la programmation ENSAE 1A

seance11_trie_cor.tex

construction aléatoire d'un mot


import random
def mot_alea (l) :
    l = [ chr(97+random.randint(0,25)) for i in range(l) ]
    return "".join(l)
		
taille  = 20
N       = 100000
mots    = [ mot_alea(10) for _ in range (N) ]

mesure du temps recherche simple


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

mesure du temps recherche dichotomique


# 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 == m :
            return 
        else :
            a = m+1
    return a

mots.sort()

debut = time.clock()
for k in cherche :
    i = dicho(mots, k)
fin = time.clock()
print ("dichotomie",fin - debut)

construction du 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

rechercher dans le trie


def lookup(trie, m) :
    r = trie
    for c in m :
        if c in r :
            r = r[c]
        else :
            return False
    return True

mesurer du temps pour le trie


debut = time.clock()
for k in cherche :
    i = lookup(trie, k)
fin = time.clock()

programme pour mesurer les différents temps de recherche

import random, time

def mot_alea (l) :
    l = [ chr(97+random.randint(0,25)) for i in range(l) ]
    return "".join(l)
    
for N in [100,200,500,1000,2000,5000,10000,20000,50000,100000,200000] :
    for taille in [5,10,20,50,100] :
        n       = 1000
        mots    = [ mot_alea(10) for _ in range (N) ]
        cherche = [ mot_alea(10) for _ in range(0,n) ]
        mots   += cherche

        if True :
            # 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 == m :
                        return 
                    else :
                        a = m+1
                return a

            mots.sort()

            debut = time.clock()
            for k in cherche :
                i = dicho(mots, k)
            fin = time.clock()
            print ("dichotomie\t",N,"\t",taille,"\t",(fin - debut)/len(cherche))
            
        if True :
            # recherche dichotomique
            dico = { m:0 for m in mots }

            debut = time.clock()
            for k in cherche :
                i = dico[k]
            fin = time.clock()
            print ("dictionnaire\t",N,"\t",taille,"\t",(fin - debut)/len(cherche))
            
        if True :
            # 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
                
            def lookup(trie, m) :
                r = trie
                for c in m :
                    if c in r :
                        r = r[c]
                    else :
                        return False
                return True
                
            trie = build_trie(mots)
            
            debut = time.clock()
            for k in cherche :
                assert lookup(trie, k)
            fin = time.clock()
            print ("trie\t",N,"\t",taille,"\t",(fin - debut)/len(cherche))
            
        if False :
            # recherche simple
            debut = time.clock()
            for k in cherche :
                i = mots.index(k)
            fin = time.clock()
            print ("recherche simple\t",N,"\t",taille,"\t",(fin - debut)/len(cherche))