Comment puis-je vérifier si une liste est un sous-ensemble d'une autre ?

Question

Je dois vérifier si une liste est un sous-ensemble d'une autre - un retour booléen est tout ce que je recherche.

Le test d'égalité sur la plus petite liste après une intersection est-il le moyen le plus rapide de le faire ? Les performances sont de la plus haute importance étant donné le nombre d'ensembles de données qui doivent être comparés.

Ajout de faits supplémentaires sur la base des discussions :

1. L'une ou l'autre de ces listes sera-t-elle la même pour de nombreux tests ? Oui, car l'une d'entre elles est une table de consultation statique.

2. Doit-il s'agir d'une liste ? Non, la table de consultation statique peut être tout ce qui est le plus performant. La table dynamique est un dict dont nous extrayons les clés pour effectuer une recherche statique.

Quelle serait la solution optimale compte tenu du scénario ?

Answer 1

>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

Answer 2

Utilisez set.issubset

Exemple :

a = {1,2}
b = {1,2,3}
a.issubset(b) # True

a = {1,2,4}
b = {1,2,3}
a.issubset(b) # False

---

La fonction performante que Python fournit pour cela est set.issubset . Il présente toutefois quelques restrictions qui ne permettent pas de savoir si c'est la réponse à votre question.

Une liste peut contenir des éléments plusieurs fois et a un ordre spécifique. Ce n'est pas le cas d'un ensemble. De plus, les ensembles ne fonctionnent que sur hachable objets.

S'agit-il d'un sous-ensemble ou d'une sous-séquence (ce qui signifie que vous aurez besoin d'un algorithme de recherche de chaînes) ? L'une ou l'autre des listes sera-t-elle la même pour de nombreux tests ? Quels sont les types de données contenus dans la liste ? Et d'ailleurs, est-il nécessaire que ce soit une liste ?

Votre autre poste intersecter un dict et une liste a rendu les types plus clairs et a obtenu une recommandation pour utiliser les vues de clés de dictionnaire pour leur fonctionnalité de type ensemble. Dans ce cas, on savait que cela fonctionnait car les clés de dictionnaire se comportent comme un ensemble (à tel point qu'avant d'avoir des ensembles en Python, nous utilisions des dictionnaires). On peut se demander comment le problème est devenu moins spécifique en trois heures.

Answer 3

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

all(x in two for x in one)

Explication : Le générateur crée des booléens en parcourant la liste en boucle. one vérifier si cet élément est dans la liste two . all() renvoie à True si chaque élément est véridique, sinon False .

Il y a également un avantage que all retourner Faux à la première occurrence d'un élément manquant plutôt que de devoir traiter chaque élément.

Answer 4

En supposant que les éléments sont hachables

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

Si vous ne vous souciez pas des éléments en double, par exemple. [1, 2, 2] y [1, 2] alors utilisez simplement :

>>> set([1, 2, 2]).issubset([1, 2])
True

Le test d'égalité sur la plus petite liste après une intersection est-il le moyen le plus rapide de le faire ?

.issubset sera le moyen le plus rapide de le faire. Vérification de la longueur avant l'essai issubset n'améliorera pas la vitesse parce que vous avez toujours O(N + M) éléments à itérer et à vérifier.

Answer 5

Une autre solution serait d'utiliser un intersection .

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

L'intersection des ensembles contiendrait set one

(OR)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)