Recherche et filtrage

Introduction

Une table de données ne sert à rien si vous ne savez pas en extraire ce qui vous intéresse. La question typique est : « parmi tous ces élèves, lesquels sont en classe 1G2 ? » ou « lesquels ont au moins 17 ans ? » C'est l'opération de recherche — ou filtrage quand on garde toutes les lignes correspondantes plutôt qu'une seule.

Ce cours vous montre comment réaliser ces sélections en Python sur une table représentée comme liste de dictionnaires (cf. cours précédent). [PD03] formalise cette capacité : rechercher les lignes d'une table vérifiant des critères exprimés en logique propositionnelle.

Le principe : parcours linéaire

La méthode élémentaire est la recherche linéaire : on parcourt la table ligne par ligne, et pour chaque ligne on évalue le critère. Si le critère est vrai, la ligne est conservée. Sinon, elle est ignorée. C'est la stratégie qu'on adopte naturellement face à un trousseau de clés sans étiquette : on essaie chaque clé jusqu'à trouver la bonne.

Premier exemple : trouver une ligne unique

Cherchons l'élève dont le nom est "Chloé" :

eleves = [
    {"nom": "Alice",   "age": 16, "classe": "1G2"},
    {"nom": "Bob",     "age": 17, "classe": "1G3"},
    {"nom": "Chloé",   "age": 16, "classe": "1G2"},
    {"nom": "Dimitri", "age": 17, "classe": "1G2"},
    {"nom": "Élodie",  "age": 16, "classe": "1G3"},
]

resultat = None
for eleve in eleves:
    if eleve["nom"] == "Chloé":
        resultat = eleve
        break

print(resultat)
# {'nom': 'Chloé', 'age': 16, 'classe': '1G2'}

Le break permet de s'arrêter dès qu'on a trouvé — inutile de continuer si le nom est unique.

Filtrer : toutes les lignes vérifiant un critère

Pour récupérer toutes les lignes correspondantes, on accumule dans une nouvelle liste :

Sortie :

Alice
Chloé
Dimitri

Version concise avec une compréhension de liste

Le même filtrage s'écrit en une ligne avec une compréhension de liste :

en_1g2 = [eleve for eleve in eleves if eleve["classe"] == "1G2"]

print(len(en_1g2))  # 3
print(en_1g2[0]["nom"])  # Alice

Critères composés (logique propositionnelle)

Un critère peut combiner plusieurs conditions avec les opérateurs logiques and, or et not. C'est ce qu'on appelle de la logique propositionnelle.

and — deux conditions doivent être vraies

# Élèves de 1G2 ET ayant 16 ans
selection = [e for e in eleves if e["classe"] == "1G2" and e["age"] == 16]

for e in selection:
    print(e["nom"], e["age"])
# Alice 16
# Chloé 16

or — au moins une condition doit être vraie

# Élèves de 1G2 OU 1G3 (toutes les classes Première Générale)
selection = [e for e in eleves if e["classe"] == "1G2" or e["classe"] == "1G3"]

print(len(selection))  # 5

not — inverser une condition

# Tous les élèves SAUF ceux de 1G3
selection = [e for e in eleves if not e["classe"] == "1G3"]

print(len(selection))  # 3

Détecter des doublons

Une utilisation classique du filtrage est la détection de doublons sur une colonne. On compare chaque ligne à toutes les autres et on signale celles qui apparaissent plusieurs fois :

eleves = [
    {"nom": "Alice", "age": 16},
    {"nom": "Bob",   "age": 17},
    {"nom": "Alice", "age": 16},
]

noms_vus = []
doublons = []
for e in eleves:
    if e["nom"] in noms_vus:
        doublons.append(e["nom"])
    else:
        noms_vus.append(e["nom"])

print(doublons)  # ['Alice']

Cas particuliers et pièges

• Comparer des chaînes : == est sensible à la casse — "Alice" et "alice" sont différents. Au besoin, comparer après .lower().
• Comparer après conversion : si vous filtrez par âge et que la colonne est encore en chaîne, e["age"] >= 17 lèvera une TypeError. Convertir avant.
• Priorité des opérateurs : not s'applique en premier, puis and, puis or. Au moindre doute, parenthésez : (a and b) or c se lit mieux que a and b or c.

Pour aller plus loin

La recherche dichotomique ([PH04]) permet, sur une table triée, de trouver une ligne en $\mathcal{O}(\log n)$ — beaucoup plus rapide. Pour une recherche par clé fréquente, l'indexation (cours 4) est encore mieux : $\mathcal{O}(1)$.