Kagenmi - stock.adobe.com
Comment supprimer des doublons dans une liste en Python
Ce conseil revient sur différentes méthodes pour supprimer des entrées en double dans une liste Python. La méthode qui exploite la fonction set () est considérée comme la plus efficace.
Un problème courant en informatique et en programmation consiste à déterminer si une liste contient des entrées en double.
Il existe heureusement plusieurs techniques pour éviter ces doublons avec Python. Dans un premier temps, nous allons voir la différence de performance entre une solution triviale et une autre optimisée.
Une première méthode triviale, mais peu efficace à large échelle
La façon la plus simple de résoudre ce problème consiste à comparer chaque élément de la liste. Cette méthode renverra sans aucun doute la bonne réponse et fonctionnera dans des délais raisonnables tant que la taille de la liste demeure contrainte. En revanche, le temps d’exécution augmentera de manière quadratique au fur et à mesure que la taille de la liste augmente.
def check_duplicate_trivial(items):
for idx in range(len(items)):
for inner in range(len(items)):
if inner == idx:
continue # do not compare to itself
if items[inner] == items[idx]:
return True
return False
Il s’agit d’une boucle à l’intérieur d’une boucle – la boucle extérieure est l’index de l’élément que nous comparons, et tous les autres éléments sont indexés à l’aide de la boucle intérieure. Cette implémentation triviale est vraiment inadaptée aux grandes listes – elle multiplie au carré le nombre de comparaisons d’éléments.
Nous pouvons quelque peu améliorer cette méthode. Si la fonction trouve un doublon, elle se termine en retournant à ce point. Dans la majorité des cas, cette méthode sera nettement plus rapide et, au pire, elle continuera à comparer chaque item à tous les autres.
Amélioration de la mise en œuvre : vérifier une liste existante
Comment pouvons-nous améliorer cela et résoudre le problème du nombre de comparaisons qui augmente de manière quadratique avec le nombre d’éléments dans la liste ?
Une autre approche consiste à conserver une deuxième liste d’éléments uniques déjà vus, puis à vérifier cette liste pour voir si l’élément y existe déjà.
def check_duplicate_improved(items):
already_seen = {}
for item in items:
if item in already_seen:
return True
already_seen[item] = 0
return False
Cela signifie que nous ne parcourons la liste principale qu’une seule fois. Nous parcourons la liste des éléments uniques pour chaque entrée de la liste principale, mais même dans le pire des cas, cela réduit considérablement le nombre de comparaisons.
L’algorithme amélioré est beaucoup plus rapide que l’algorithme trivial, mais il reste assez lent au moment de l’exécuter sur une grande liste.
Est-ce que le système pythonique fournit un moyen spécifique pour éviter toutes ces comparaisons ?
La méthode set() est la plus efficace
Oui, nous pouvons utiliser ce que l’on appelle un Set.
Un Set est sauvegardé à l’aide d’une table de hachage. Celle-ci calcule une valeur de hachage pour l’objet et l’utilise comme clé pour le stocker dès son ajout. Les objets peuvent avoir la même valeur de hachage et, dans les ensembles plus importants, il est courant d’utiliser l’algorithme de hachage pour répartir les objets entre les hachages disponibles afin de maintenir des performances constantes.
Le hash peut être considéré comme un pointeur ou une référence directe à la structure de données sous-jacente, ce qui rend la recherche très rapide. C’est ce qui en fait un excellent choix pour transformer les problèmes de recherche d’éléments en problèmes à temps constant.
def check_duplicate_set(items):
hash_bucket = set()
for item in items:
if item in hash_bucket:
return True
hash_bucket.add(item)
return False
Comme la portion de code ci-dessus le montre, nous vérifions si l’élément se trouve dans le Set avant de l’ajouter, et si c’est le cas, nous renvoyons le code. Nous avons maintenant réduit la vérification des doublons à un simple balayage des items d’origine.
Cette fonction peut également être réduite à une seule ligne. Pour ce faire, créez un Set à partir des éléments originaux (les ensembles sont garantis de n’avoir que des entrées uniques) et comparez la taille des deux :
def check_duplicate_distinct(items):
return len(items) != len(set(items))
Ce code est à la fois compact et efficace.
Deux exemples avec des librairies tierces
Il existe également des moyens en dehors du système pythonique, en utilisant la bibliothèque iteration_utilities ou NumPy.
Après avoir installé iteration_utilities avec la commande pip install iteration-utils, il existe deux méthodes :
from iteration_utilities import duplicates
list(duplicates('AABBCCDA'))
['A', 'B', 'C', 'A']
list(duplicates('ABBCcAD', str.lower))
['B', 'c', 'A']
Celle-ci, selon la documentation associée, signalera les doublons, mais les conservera. Il faut utiliser la fonction unique_everseen pour obtenir une liste d’éléments uniques, tout en préservant leur ordre d’origine.
from iteration_utilities import unique_everseen
list(unique_everseen(duplicates('AABBCCDA')))
['A', 'B', 'C']
Il existe aussi un usage détourné de NumPy pour identifier, puis supprimer les entrées en double. Voici la méthode :
import numpy as np
my_list = [1, 2, 2, 3, 4, 4, 5]
unique_array = np.unique(my_list)
unique_list = unique_array.tolist()
La fonction numpy.unique() renvoie dans un tableau NumPy les éléments uniques de la liste, puis la méthode tolist() est utilisé pour convertir ce tableau en liste Python. Pour autant, cette méthode est plus efficace afin de repérer et supprimer des doublons dans des jeux de données.
En Python, pour la plupart des situations où vous souhaitez détecter des doublons dans une liste, la méthode set () est la meilleure à utiliser pour des raisons de performance, d’autant qu’elle ne crée pas de dépendances à une librairie tierce.
