Outils pour utilisateurs

Outils du site


dichotomie

Recherche rapide par dichotomie dans une liste triée

Dernière modification le 20/4/2009

Principe

Pour comprendre ce qu'est la dichotomie, je vous propose une petite expérience: chercher un mot dans un gros dictionnaire papier de 1024 pages:

  • vous l'ouvrez au milieu: le mot ne s'y trouve pas, mais il est avant (il est donc dans les 512 premières pages).
  • vous ouvrez la moitié de la 1ère moitié: le mot ne s'y trouve pas, mais il est après (il est donc dans les pages 257 à 512).
  • vous ouvrez la moitié de la 2ème moitié, etc…

A chaque fois que vous progressez, le nombre de pages qui reste à examiner est divisé par 2.

Ainsi, dans un dictionnaire de 1024 pages, vous êtes certain de trouver votre page en 10 recherches seulement, puisque 1024/(2**10)=1.

Alors qu'en parcourant le dictionnaire page par page (recherche séquentielle), vous allez feuilleter en moyenne la moitié des pages du dictionnaire, c'est à dire 512. La recherche par dichotomie permet donc de trouver en 10 pages ce qu'il vous faudrait trouver en 512 pages normalement. Et ce différentiel s'accroit quand on augmente le nombre de pages: plus le dictionnaire est gros, plus vous gagnez du temps.

Heureusement, quand on cherche à la main, on n'est pas aussi bête qu'un ordinateur, et intuitivement, on ouvre le dictionnaire à son quart pour chercher une mot commençant par “f”.

Codage de la recherche par dichotomie

Il y a une chose importante à rappeler: la recherche par dichotomie ne marche que si la liste dans laquelle on cherche est déjà triée, et si la recherche est faite selon le même critère de tri.

De ce fait, je vous propose un code qui utilise les mêmes fonctions de comparaison (cmp) et de conversion (key) que les fonctions sort() et sorted() de Python!

Voilà le code proposé pour la recherche de la valeur x dans la liste triée L:

def dichot(x, L, comp=cmp, key=lambda c: c):
    i, j = 0, len(L)-1
    while i<j:
        k=(i+j)//2
        if comp(x,key(L[k]))<=0:
            j = k
        else:
            i = k+1
    return [comp(x,key(L[i])), i]

Si vous voulez une version récursive, la voilà, mais je ne la conseille pas: elle donne le même résultat, mais elle est limitée par la pile de récursion de Python (env. 1000):

def _dichot(x, L, i, j, comp, key):
    if i>=j:
        return [comp(x,key(L[i])), i]
    k=(i+j)//2
    if comp(x,key(L[k])) <= 0:
        return _dichot(x, L, i, k, comp, key)
    else:
        return _dichot(x, L, k+1, j, comp, key)
 
def dichot(x, L, comp=cmp, key=lambda c: c):
    return _dichot(x, L, 0, len(L)-1, comp, key)

Ces fonctions renvoient une liste de 2 valeurs: [critère de réussite, indice dans la liste].

Le critère de réussite r est analogue au résultat de la fonction intégrée r=cmp(v1,v2):

  • r<0 si v1<v2
  • r=0 si v1==v2
  • r>0 si v1>v2

Ce qui donne comme interprétation du résultat:

  • [r=0, i] ⇒ la valeur cherchée x est trouvée à l'indice i
  • [r<0, i] ⇒ la valeur cherchée x n'est pas trouvée, mais se trouve juste avant l'indice i
  • [r>0, i] ⇒ n'apparait qu'avec i=(len(L)-1) ⇒ la valeur cherchée x n'est pas trouvée, mais est supérieure à la dernière valeur de la liste

Si on cherche une valeur qui se trouve à plusieurs exemplaires dans la liste, on trouve l'indice de la 1ère valeur

En ce qui concerne les fonctions de comparaison et de conversion, elles sont identiques à celle qu'on utilise avec les fonctions sort() et sorted(). Seule différence, la fonction éventuellement affectée à key ne corrige que l'élément de la liste, et pas la valeur à chercher, parce que nous avons pleine maitrise de la présentation de la valeur à chercher x et que ce serait une perte de temps de faire cette correction sur x à chaque comparaison.

Voilà un exemple de fonction de comparaison de base (le résultat est ici identique à cmp(v1,v2)):

def comp(v1,v2):
    if v1<v2:
        return -1
    if v1>v2:
        return 1
    return 0

Et voilà un exemple de fonction de conversion de base (key):

def conv(v):
    return v

Avec ces 2 fonctions, l'appel à la fonction dichot deviendrait:

R = dichot(x, L, comp, conv)

Tests de vérification

Voilà comment vous pouvez vérifier que ça marche:

# liste de nombres entiers triés
L = [0, 2, 4, 4, 4, 6, 6, 8, 9, 9, 9, 9]
print L
 
# liste de valeurs à chercher successivement
V = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for x in V:
    print u"cherché=%2d:" % x, u"résultat:", dichot(x, L)
print
 
# ce qui affiche:
cherché=-1: résultat: [-1, 0]
cherché= 0: résultat: [0, 0]
cherché= 1: résultat: [-1, 1]
cherché= 2: résultat: [0, 1]
cherché= 3: résultat: [-1, 2]
cherché= 4: résultat: [0, 2]
cherché= 5: résultat: [-1, 5]
cherché= 6: résultat: [0, 5]
cherché= 7: résultat: [-1, 7]
cherché= 8: résultat: [0, 7]
cherché= 9: résultat: [0, 8]
cherché=10: résultat: [1, 11]

Comme on a codé la fonction de recherche avec les mêmes fonctions de comparaison et de conversion que sort(), on va donner un exemple avec une liste de liste:

L = [[5,3,4], [8,2,6], [9,4,1], [2,1,0], [5,4,7]]

On va trier cette liste selon la 2ème valeur des sous-listes (p. ex. le 3 de [5,3,4]), et on va chercher par dichotomie des valeurs.

# fonction de comparaison utilisable pour le tri et pour la recherche dans la liste triée
def comp(v1, v2):
    return cmp(v1[1],v2[1])
 
# liste d'origine non triée
L = [[5,3,4], [8,2,6], [9,4,1], [2,1,0], [5,4,7]]
 
# tri de la liste en fonction de la 2ème valeur de chaque sous-liste (par exemple le 3 de [5,3,4])
L.sort(comp)
print L
# affiche: [[2, 1, 0], [8, 2, 6], [5, 3, 4], [9, 4, 1], [5, 4, 7]]
 
# recherche de valeurs issues de la liste V
V = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for x in V:
    print u"cherché=%2d:" % x, u"résultat:", dichot([0,x,0], L, comp)
 
# affiche:
cherché=-1: résultat: [-1, 0]
cherché= 0: résultat: [-1, 0]
cherché= 1: résultat: [0, 0]
cherché= 2: résultat: [0, 1]
cherché= 3: résultat: [0, 2]
cherché= 4: résultat: [0, 3]
cherché= 5: résultat: [1, 4]
cherché= 6: résultat: [1, 4]
cherché= 7: résultat: [1, 4]
cherché= 8: résultat: [1, 4]
cherché= 9: résultat: [1, 4]
cherché=10: résultat: [1, 4]

On peut faire de la même manière en triant/recherchant, par exemple, une liste d'objets python sous forme de classes.

On peut aussi faire tout cela sans rien changer à la liste d'origine et en utilisant un fichier d'index.

Tests de performance

Pour se donner une base de comparaison, on va créer une fonction de recherche séquentielle, ayant les mêmes fonctionnalités et qui donne, bien entendu, le même résultat.

def seq(x, L, comp=cmp, key=lambda c: c):
    i, j = 0, len(L)-1
    for i in xrange(0,j+1):
        r = comp(x,key(L[i]))
        if r==0:
            return [0,i]
        if r<0:
            return [-1,i]
    return [1,j]

Et voilà le code d'essai:

import random
import time
 
lg = 1000000
L = [random.randint(1000,9999) for i in xrange(0,lg)]
L.sort()
 
t1 = 0
t2 = 0
n=100
 
for n in range(0,n):
    x = random.randint(1000,9999)
 
    t = time.clock()
    r,i = dichot(x,L)
    t1 += time.clock()-t
 
    t = time.clock()
    r,i = seq(x,L)
    t2 += time.clock()-t
 
print t2/t1, t1/n

Avec ce code, on peut paramétrer:

  • lg = longueur de la liste
  • n = nombre d'essais de recherche avec tirage au hasard de la valeur à chercher

Et ce code affiche comme résultats:

  • t2/t1 = rapport des temps de recherche séquentielle sur temps de recherche dichotomique
  • t1/n = temps moyen en secondes de recherche dichotomique

Les résultats sont impressionnants:

  • déjà avec une liste de 1000 (mille) éléments, la recherche par dichotomie est environ 30 fois plus rapide que la recherche séquentielle. Si ce n'est pas plus fort, c'est que nous avons “chargé la mule” dans les 2 cas (avec comp et key), ce qui diminue le différentiel de temps.
  • avec une liste de 1000000 (1 million) éléments, la recherche par dichotomie est environ 12000 (douze mille) fois plus rapide que la recherche séquentielle, avec des temps de recherche <1/10000 de secondes…

Recherche dans un fichier sur disque

Pour faire l'essai, on va créer une fonction qui va créer un fichier en accès direct ayant les caractéristiques suivantes:

  • fichier = nom du fichier
  • lg = nombre d'éléments qui sont des nombres entiers triés
  • lge = longueur de chaque enregistrement sur disque
  • i1 = nombre entier le plus petit du fichier
  • i2 = nombre entier le plus grand du fichier
import random
import time
 
def creafic(fichier, lg, lge, I1, I2):
    # fabrication de la liste à enregistrer
    L = [random.randint(I1, I2) for i in xrange(0,lg)]
 
    # tri de la liste
    L.sort()
 
    # creation du fichier sur disque
    f = open(fichier, 'wb')
    esp = ' '*lge
    for i in range(0, len(L)):
        f.seek(i*lge)
        v = "%s" % L[i]
        f.write(v + esp[:lge-len(v)])
    f.close()
 
fichier = "datas.fad"
lg = 1000000
lge = 5
I1 = 1000
I2 = 9999
 
t = time.clock()
creafic(fichier, lg, lge, I1, I2)
t = time.clock()-t
print u"création du fichier:", fichier, lg, lge, I1, I2, "en", t, "secondes"

Par exemple, avec creafic(“datas.fad”, 1000000, 5, 1000, 9999), on crée un fichier d'environ 5 Mo qui contiendra 1000000 d'entiers triés compris entre 1000 et 9999, placés dans des enregistrements de 5 octets. Cette création prend environ 20 secondes.

On va maintenant créer une fonction de lecture d'un enregistrement connaissant son indice, ainsi qu'une liste des indices croissants tel que I[i]=i:

def litdata(i):
    global f, lge
    f.seek(i*lge)
    return int(f.read(lge).strip())
 
I = [i for i in xrange(0,lg)]

Vous pouvez vérifier la validité du fichier sur disque comme suit. Mais ne le faites pas pour le fichier d'1000000 de valeurs: cela demanderait trop de temps d'affichage.

# verification
f = open(fichier, 'rb')
for i in I:
    print litdata(i)
print
f.close()

On va utiliser maintenant les fonctions de recherche précédentes: dichot() pour la recherche dichotomique et seq() pour les recherches séquentielles.

Et voilà le code d'essai, qui va calculer une valeur au hasard, va la trouver par les 2 méthodes (dichot et seq), et va comparer les temps de réponse. Le programme est prévu pour s'exécuter en boucle afin de stabiliser les résultats. Il doit donc être arrêté avec Ctle-C:

f = open(fichier, 'rb')
t1 = 0
t2 = 0
c = 0
while True:
    try:
        c += 1 
        x = random.randint(I1-1, I2+1)
 
        t = time.clock()
        r1,i1 = dichot(x, I, key=litdata)
        t1 += time.clock()-t
 
        t = time.clock()
        r2,i2 = seq(x, I, key=litdata)
        t2 += time.clock()-t
 
        print x, [r1, i1], [r2, i2], litdata(i1), litdata(i2), t2/t1, t1/c
    except:
        break
f.close()

Ce qui affiche, par exemple:

9097 [0, 900121] [0, 900121] 9097 9097 17305.7813651 0.000167109172573
4026 [0, 337762] [0, 337762] 4026 4026 17271.2771325 0.000167086643643
5159 [0, 463844] [0, 463844] 5159 5159 17267.2479243 0.000167060928584
8676 [0, 853399] [0, 853399] 8676 8676 17356.9558071 0.000167023901043

Le résultat est époustouflant: on trouve une valeur au hasard parmi un million de valeurs sur disque en moins d'1/1000 secondes, et c'est 17000 fois plus rapidement qu'avec la méthode séquentielle…

Ça vous suffit comme performance? :-D

NB: je ne connais pas l'impact des buffers disques sur ce résultat (essai fait sur Windows XP SP3 en raid 1). Cependant, le temps est le même quand on prend successivement une petite valeur (1500), une moyenne (5000) et une grande (9500).

Recherche indexée dans un fichier sur disque

On se propose ici de rechercher des valeurs par dichotomie avec un fichier disque non trié, et sans charger ce fichier en mémoire. On va donc créer un fichier d'index qui, lui, sera en mémoire, et qui permettra de retrouver triées les données du fichier sur disque. Grâce à ce fichier d'index, on va pouvoir chercher n'importe quelle valeur par dichotomie avec le même niveau de performance!

On va d'abord créer un fichier d'essai comme précédemment, mais sans l'avoir trié avant de d'enregistrer les valeurs:

import random
import time
 
def creafic(fichier, lg, lge, i1, i2):
    # fabrication de la liste à enregistrer
    L = [random.randint(i1, i2) for i in xrange(0,lg)]
 
    # creation du fichier sur disque
    f = open(fichier, 'wb')
    esp = ' '*lge
    for i in range(0, len(L)):
        f.seek(i*lge)
        v = "%s" % L[i]
        f.write(v + esp[:lge-len(v)])
    f.close()
 
fichier = "datas.fad"
lg = 1000000
lge = 5
I1 = 1000
I2 = 9999
 
t = time.clock()
creafic(fichier, lg, lge, I1, I2)
t = time.clock()-t
print u"création du fichier:", fichier, lg, lge, I1, I2, "en", t, "secondes"

La création de ce fichier d'1 million d'entiers tirés au hasard prend environ 20 secondes.

Maintenant, on va créer un fichier d'index et trier ce fichier pour retrouver les données du fichier sur disque dans l'ordre numérique croissant:

def litdata(i):
    global f, lge
    f.seek(i*lge)
    return int(f.read(lge).strip())
 
I = [i for i in xrange(0,lg)]
f = open(fichier, 'rb')
t = time.clock()
I.sort(key=litdata)
t = time.clock()-t
f.close()
print u"fichier d'index créé et trié en ", t, "secondes"

La création de ce fichier d'index a pris environ 7 secondes. Grâce à ce fichier, on peut retrouver toutes les données du fichier sur disques dans l'ordre numérique croissante.

Si vous voulez le vérifier, vous pouvez afficher les données du disque dans cet ordre comme suit. Mais ne le faites pas pour le fichier de 1000000 de valeurs: cela demandera trop de temps pour l'affichage.

f = open(fichier, 'rb')
for i in I:
    print litdata(i)
print
f.close()

On va utiliser maintenant les fonctions de recherche précédentes: dichot() pour la recherche dichotomique et seq() pour les recherches séquentielles.

f = open(fichier, 'rb')
t1 = 0
t2 = 0
c = 0
while True:
    try:
        c += 1 
        x = random.randint(I1-1, I2+1)
 
        t = time.clock()
        r1,i1 = dichot(x, I, key=litdata)
        t1 += time.clock()-t
 
        t = time.clock()
        r2,i2 = seq(x, I, key=litdata)
        t2 += time.clock()-t
 
        print x, [r1, i1], [r2, i2], litdata(I[i1]), litdata(I[i2]), t2/t1, t1/c
    except:
        break
f.close()

Le code ci-dessus (qu'on arrête avec Ctrl-C) affiche les résultats comme suit:

8317 [0, 813361] [0, 813361] 8317 8317 17537.9140573 0.000173003674181
8476 [0, 830810] [0, 830810] 8476 8476 17587.4199338 0.000173009098294
4398 [0, 377556] [0, 377556] 4398 4398 17571.9584712 0.000172991006654
5537 [0, 504304] [0, 504304] 5537 5537 17575.2446774 0.000172973807046

Ce qui montre une performance quasi identique au test précédent: le passage par une liste d'index n'a donc pas ralenti sensiblement le temps de recherche: la recherche dichotomique sur disque, avec ou sans index, est vraiment une méthode performante!


Amusez-vous bien!

dichotomie.txt · Dernière modification: 2009/04/20 09:06 par tyrtamos

Outils de la page