Pour vérifier si deux listes non ordonnées x et y sont identiques, comparer les ensembles convertis avec set(x) == set(y) . Cependant, cela perd toutes les informations sur les éléments dupliqués. Pour considérer les doublons, comparez les listes triées avec sorted(x) == sorted(y) . En raison de l'implémentation efficace de type fusion-sort du sorted() fonction, c'est assez rapide pour les listes presque triées.
Problème :Soit deux listes x et y . Vous voulez retourner True si les deux listes contiennent les mêmes éléments, sinon False . Une variante de ce problème consiste à ignorer les doublons (ce qui rend ce problème beaucoup plus simple).
Exemples :
x = [1, 2, 3, 4, 5] y = [1, 2, 3] # compare(x, y) --> False x = [1, 2, 3, 4, 5] y = [1, 2, 3, 5, 4] # compare(x, y) --> True x = [1, 2, 3, 4, 5] y = [1, 2, 3, 4, 5] # compare(x, y) --> True
Discutons des moyens les plus Pythoniques de résoudre ce problème. Voici un bref aperçu interactif du code :
Exercice :Jetez un coup d'œil sur toutes les méthodes et exécutez le code. Quelles questions vous viennent à l'esprit ? Comprenez-vous chaque méthode ?
Lisez la suite pour en savoir plus sur chaque méthode en détail !
Méthode 1 :Définir la conversion
Cette méthode suppose que vous ignorez les doublons. Ainsi, les listes [1, 1, 1] et [1] sont considérés comme identiques :
###################
# 1. Set Conversion
###################
def method_1(x, y):
return set(x) == set(y)
print(method_1([1, 2, 3], [1, 2]))
# False
print(method_1([1, 2], [2, 1]))
# True La conversion de la liste en un ensemble a une complexité d'exécution linéaire. La comparaison de deux ensembles pour l'égalité a également une complexité d'exécution linéaire (en raison de la complexité d'exécution constante de l'appartenance à un ensemble). Ainsi, dans l'ensemble, la complexité d'exécution de cette méthode est linéaire dans le nombre d'éléments dans la liste plus grande.
Cependant, un ensemble ne contient aucune information sur le nombre de fois que chaque élément est représenté. Pour prendre en compte ces informations, vous aurez besoin d'une structure de données multi-ensembles.
Méthode 2 :Multiset avec compteur de collectes
En Python, certains packages multiset sont capables de prendre en compte le nombre de fois où chaque élément est représenté dans la liste d'origine. L'un d'eux est le collections.Counter classer.
###################
# 2. Collections Counter
###################
import collections
def method_2(x, y):
return collections.Counter(x) == collections.Counter(y)
print(method_2([1, 1, 1], [1, 1]))
# False
print(method_2([1, 2, 3], [2, 1, 3]))
# True Cette méthode est également efficace et masque les détails d'implémentation, ce qui conduit à un degré de découplage plus élevé dans votre application Python. Cependant, vous n'aimerez peut-être pas que cela nécessite d'importer une autre dépendance.
Méthode 3 :Trier
Le tri d'une liste en Python utilise un algorithme très efficace basé sur le mergesort. Cela signifie que si la liste est « presque » triée, la routine de tri est très rapide. Seulement dans le pire cas absolu, la complexité de calcul est O(n log n) pour trier une liste.
Dès que les deux listes sont triées, vous pouvez continuer et utiliser l'opérateur de comparaison élément par élément x==y vérifier l'identité de deux listes ordonnées x et y .
###################
# 3. Sorting
###################
def method_3(x, y):
return sorted(x) == sorted(y)
print(method_2([1, 1, 1], [1, 1]))
# False
print(method_2([1, 2, 3], [2, 1, 3]))
# True Merci d'avoir lu cet article ! Si vous voulez apprendre quelque chose de nouveau chaque jour, rejoignez ma série d'e-mails Python gratuits pour une amélioration continue de Python et de l'informatique.
Vidéo associée
Cette vidéo est liée au problème :vérifier si deux commandés les listes sont identiques.
