Recherche rapide par dichotomie dans une liste complexe triée

**tyrtamos** · 12/04/2023, 10h46

Rechercher par dichotomie dans une liste triée est très rapide et bien connu. Pour l'expliquer, on prend souvent l'exemple d'une recherche dans un dictionnaire papier:
- on cherche un mot
- on ouvre le dictionnaire par son milieu: le mot est "avant" ou "après". Par exemple "avant".
- on ouvre la partie "avant" par son milieu: le mot est "avant" ou "après"
- etc...
- jusqu'à ce qu'on trouve la page qui contient le mot.

Cette recherche est très efficace, parce qu'il suffit avec 1000 pages de 10 manipulations seulement, puisque 2**10=1024. On peut même trouver plus tôt si on a de la chance.

On peut vouloir rechercher par dichotomie pour plusieurs raisons. Par exemple:

- trouver si le mot existe ou pas

- si le mot existe, trouver à quel indice de la liste il se trouve

- si le mot n'existe pas, trouver à quel endroit on peut l'insérer dans la liste. Ce qui est intéressant dans cette insertion, c'est que la liste continue à être triée! C'est beaucoup plus efficace que d'ajouter le mot avec append et de re-trier la liste après.

Le module Python qui fait ça s'appelle "bisect". On utilise par exemple la fonction "bisect_left" pour trouver l'indice de présence ou d'insertion d'un élément dans la liste. Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
from bisect import bisect_left
 
seq = [1,2,3,5,5,6,7,8]
 
ib = bisect_left(seq, 3)
# ib==2 puisque 3 existe dans la liste à l'index 2
 
ib = bisect_left(seq, 4)
# ib==3 puisque 4 n'existe pas, on a l'indice d'insertion 3

En cas d'insertion de 4 à l'indice 3 de cette liste, c'est facile:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
seq.insert(3, 4)
# résultat: seq => [1,2,3,4,5,5,6,7,8]

Mais, car il y a un "mais", cette fonction bisect_left n'est valable que pour des listes "simples", c'est à dire que la valeur cherchée doit être de même type que les autres éléments de la liste: nombres, chaînes de caractères, (etc...). Dans le cas d'une liste plus complexe, par exemple une liste de listes (une liste de dictionnaires, etc...), on ne peut pas faire ça pour chercher une des valeurs d'une sous-liste.

Sauf à partir de Python 3.10 qui a ajouté l'argument "key" à ses fonctions de bisect! C'est d'ailleurs le même argument key que pour la fonction de tri (.sort ou sorted), puisqu'il s'agit dans les 2 cas de situer la valeur qui nous intéresse dans l'élément quelconque de la liste: sous-liste, dictionnaire, etc...

Mais avant Python 3.10, on faisait comment? On se fabriquait une fonction de recherche par dichotomie perso! Ce n'est d'ailleurs pas compliqué à faire en Python. Mais, tant qu'à faire, voilà une fonction qui marche pour tout Python 3 (avant ou après 3.10):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys
from bisect import bisect_left
 
def bisect_left2(seq, val, ib=0, ih=None, key=None):
    """Trouve l'indice de présence ou d'insertion de la valeur val dans la
       séquence triée seq. la fonction key permet de retrouver val dans
       l'élément de seq. La séquence seq doit être triée par rapport à val.
       Arguments:
       - seq: séquence (list, tuple) triée selon val
       - val: valeur à rechercher, incluse dans l'élément de seq
       - ib: indice de recherche bas
       - ih: indice de recherche haut
       - key: fonction permettant de retrouver val dans l'élément de seq
       Retour:
       - ib: indice de présence ou d'insertion de l'élément de seq
         contenant val
    """
    # corrige les données si nécessaire
    ib = 0 if ib<0 else ib
    ih = len(seq) if ih is None or ih>len(seq) else ih
    # calcule l'indice de présence ou d'insertion de l'élément contenant val
    if sys.version_info.major==3 and sys.version_info.minor>=10:
        ib = bisect_left(seq, val, lo=ib, hi=ih, key=key)
    else:
        key = (lambda x:x) if key is None else key
        while ib < ih:
            k = (ib + ih) // 2
            if key(seq[k]) < val:
                ib = k + 1
            else:
                ih = k
    return ib

Avec Python >= 3.10, il est en effet intéressant d'utiliser plutôt le module bisect, parce qu'il utilise des fonctions codées en C, donc plus rapides.

Exemple pour une liste de listes, pour laquelle on recherche le 2ème élément de la sous liste:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
seq = [[9,1], [5,2], [7,3], [3,5], [5,5], [1,5], [12,7], [8,8]]
key = lambda x: x[1] # même key pour le tri et la recherche
 
val = 4 # n'existe pas
ib = bisect_left2(seq, val, key=key)
ok = False if ib >= len(seq) else key(seq[ib]) == val
print("valeur:", val, "index:", ib, "Existe déjà" if ok else "N'existe pas")
# affiche: valeur: 4 index: 3 N'existe pas
 
val = 5 # existe
ib = bisect_left2(seq, val, key=key)
ok = False if ib >= len(seq) else key(seq[ib]) == val
print("valeur:", val, "index:", ib, "Existe déjà" if ok else "N'existe pas")
# affiche: valeur: 5 index: 3 Existe déjà

Pour l'insertion, c'est la même chose que précédemment, à part qu'on insère une sous-liste, et pas seulement la valeur recherchée! Par exemple pour la valeur 4 qui n'existe pas et qu'on insère à l'index 3, on insère en fait une sous-liste comme [12, 4]:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
seq.insert(3, [12, 4])
# résultat: [[9,1], [5,2], [7,3], [12, 4], [3,5], [5,5], [1,5], [12,7], [8,8]]

On voit cependant que la valeur booléenne "ok" pour "présent ou pas" nécessite un petit calcul pas si simple que ça. Alors, on peut proposer une fonction qui retourne en plus cette valeur:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def dichot(seq, val, key=None):
    """Trouve l'indice de présence ou d'insertion de la valeur val dans la
       séquence triée seq. la fonction key permet de retrouver val dans
       l'élément de seq. La séquence seq doit être triée par rapport à val.
       Fonction à utiliser avec Python version >= 10
       Arguments:
       - seq: séquence (list, tuple) triée selon val
       - val: valeur à rechercher, incluse dans l'élément de seq
       - key: fonction permettant de retrouver val dans l'élément de seq
       Retour:
       - si ok==True: ib est l'indice de l'élément de seq contenant val
       - si ok==False: ib est l'indice d'insertion de l'élément de seq
         contenant val.
    """
    # calcule key pour une séquence simple (retourne l'argument donné)
    key = (lambda x:x) if key is None else key
 
    # calcule l'indice de présence ou d'insertion de l'élément contenant val
    ib, ih = 0, len(seq)
    ib = bisect_left2(seq, val, ib=ib, ih=ih, key=key)
 
    # calcule ok qui représente l'existence ou non de val dans seq
    ok = False if ib >= len(seq) else key(seq[ib]) == val
 
    return ok, ib

Le même exemple que ci-dessus, sera donc plus simple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
seq = [[9,1], [5,2], [7,3], [3,5], [5,5], [1,5], [12,7], [8,8]]
key = lambda x: x[1]
 
val = 4 # n'existe pas
ok, ib = dichot(seq, val, key=key)
print("valeur:", val, "index:", ib, "Existe déjà" if ok else "N'existe pas")
# affiche: valeur: 4 index: 3 N'existe pas
 
val = 5 # existe déjà
ok, ib = dichot(seq, val, key=key)
print("valeur:", val, "index:", ib, "Existe déjà" if ok else "N'existe pas")
# affiche: valeur: 5 index: 3 Existe déjà

On peut aller plus loin, dans le cas où une même valeur peut être rencontrée plusieurs fois. On obtiendra alors l'indice de la 1ère valeur et celui de la dernière:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def dichots(seq, val, key=None):
    """Trouve l'indice de présence ou d'insertion de la valeur val contenue
       dans les éléments de la séquence triée seq. la fonction key permet
       de retrouver val dans les éléments de seq. La séquence seq doit être
       triée par rapport à val.
       Fonction à utiliser avec Python version < 10
       Arguments:
       - seq: séquence (list, tuple) triée selon val
       - val: valeur à rechercher, incluse dans l'élément de seq
       - key: fonction permettant de retrouver val dans l'élément de seq
       Retour:
       - si ok==True: ib est l'indice du 1er élément de seq contenant val, et
         ih celui du dernier. Si ib==ih, val est unique dans seq.
       - si ok==False: ib est l'indice d'insertion de l'élément de seq
         contenant val. Dans ce cas, ih (==ib) n'a aucune signication.
    """
    # calcule key pour une séquence simple (retourne l'argument donné)
    key = (lambda x:x) if key is None else key
 
    # calcule l'indice de présence ou d'insertion
    ib, ih = 0, len(seq)
    ib = bisect_left2(seq, val, ib=ib, ih=ih, key=key)
 
    # calcule ok qui représente l'existence ou non de val dans seq
    ok = False if ib >= len(seq) else key(seq[ib]) == val
 
    # calcule en cas de doublon: ih est l'indice du dernier val
    ih = ib
    if ok:
        for ih in range(ib+1, len(seq)):
            if key(seq[ih]) != val:
                ih -= 1
                break
 
    return ok, ib, ih

Même exemple que plus haut:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
seq = [[9,1], [5,2], [7,3], [3,5], [5,5], [1,5], [12,7], [8,8]]
key = lambda x: x[1]
 
val = 4 # n'existe pas
ok, ib, ih = dichots(seq, val, key=key)
print("valeur:", val, "ib:", ib, "ih", ih, "Existe déjà" if ok else "N'existe pas")
# affiche: valeur: 4 ib: 3 ih 3 N'existe pas
 
val = 5 # existe en plusieurs exemplaires
ok, ib, ih = dichots(seq, val, key=key)
print("valeur:", val, "ib:", ib, "ih", ih, "Existe déjà" if ok else "N'existe pas")
# affiche: valeur: 5 ib: 3 ih 5 Existe déjà