Tester si les listes partagent des éléments en python

Je veux vérifier si l' un des éléments d'une liste est présent dans une autre liste. Je peux le faire simplement avec le code ci-dessous, mais je soupçonne qu'il pourrait y avoir une fonction de bibliothèque pour le faire. Sinon, existe-t-il une méthode plus pythonique pour obtenir le même résultat?

In [78]: a = [1, 2, 3, 4, 5]

In [79]: b = [8, 7, 6]

In [80]: c = [8, 7, 6, 5]

In [81]: def lists_overlap(a, b):
   ....:     for i in a:
   ....:         if i in b:
   ....:             return True
   ....:     return False
   ....: 

In [82]: lists_overlap(a, b)
Out[82]: False

In [83]: lists_overlap(a, c)
Out[83]: True

In [84]: def lists_overlap2(a, b):
   ....:     return len(set(a).intersection(set(b))) > 0
   ....: 

Réponse courte : utilisation not set(a).isdisjoint(b), c'est généralement le plus rapide.

Il existe quatre méthodes courantes pour tester si deux listes aet bpartager des éléments. La première option consiste à convertir les deux en ensembles et à vérifier leur intersection, en tant que telle:

bool(set(a) & set(b))

Étant donné que les ensembles sont stockés à l'aide d'une table de hachage en Python, leur recherche estO(1) (voir ici pour plus d'informations sur la complexité des opérateurs en Python). Théoriquement, il s'agit O(n+m)en moyenne de pour net d' mobjets dans les listes aet b. Mais 1) il doit d'abord créer des ensembles à partir des listes, ce qui peut prendre un temps non négligeable, et 2) il suppose que les collisions de hachage sont rares parmi vos données.

La deuxième façon de le faire consiste à utiliser une expression de générateur effectuant une itération sur les listes, telle que:

any(i in a for i in b)

Cela permet de rechercher sur place, donc aucune nouvelle mémoire n'est allouée pour les variables intermédiaires. Il renonce également à la première découverte. Mais l' inopérateur est toujours O(n)sur des listes (voir ici ).

Une autre option proposée est un hybride pour parcourir l'une des listes, convertir l'autre dans un ensemble et tester l'appartenance à cet ensemble, comme ceci:

a = set(a); any(i in a for i in b)

Une quatrième approche consiste à tirer parti de la isdisjoint()méthode des ensembles (figés) (voir ici ), par exemple:

not set(a).isdisjoint(b)

Si les éléments que vous recherchez sont proches du début d'un tableau (par exemple, il est trié), l'expression du générateur est privilégiée, car la méthode d'intersection des ensembles doit allouer une nouvelle mémoire pour les variables intermédiaires:

from timeit import timeit
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000)
26.077727576019242
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000)
0.16220548999262974

Voici un graphique du temps d'exécution de cet exemple en fonction de la taille de la liste:

Notez que les deux axes sont logarithmiques. Cela représente le meilleur cas pour l'expression du générateur. Comme on peut le voir, la isdisjoint()méthode est meilleure pour les très petites tailles de liste, tandis que l'expression du générateur est meilleure pour les plus grandes tailles de liste.

Par contre, comme la recherche commence par le début de l'expression hybride et génératrice, si l'élément partagé est systématiquement à la fin du tableau (ou les deux listes ne partagent aucune valeur), les approches d'intersection disjointes et d'ensemble sont alors beaucoup plus rapide que l'expression du générateur et l'approche hybride.

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
13.739536046981812
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
0.08102107048034668

Il est intéressant de noter que l'expression du générateur est beaucoup plus lente pour les listes de plus grande taille. Ce n'est que pour 1000 répétitions, au lieu des 100000 pour la figure précédente. Cette configuration se rapproche également bien lorsque aucun élément n'est partagé, et est le meilleur cas pour les approches d'intersection disjointes et définies.

Voici deux analyses utilisant des nombres aléatoires (au lieu de truquer la configuration pour favoriser une technique ou une autre):

Forte chance de partage: les éléments sont tirés au hasard [1, 2*len(a)]. Faible chance de partage: les éléments sont tirés au hasard [1, 1000*len(a)].

Jusqu'à présent, cette analyse supposait que les deux listes étaient de la même taille. Dans le cas de deux listes de tailles différentes, par exemple aest beaucoup plus petite, isdisjoint()c'est toujours plus rapide:

Assurez-vous que la aliste est la plus petite, sinon les performances diminuent. Dans cette expérience, la ataille de la liste a été définie constante sur 5.

En résumé:

• Si les listes sont très petites (<10 éléments), not set(a).isdisjoint(b)c'est toujours le plus rapide.
• Si les éléments des listes sont triés ou ont une structure régulière dont vous pouvez tirer parti, l'expression du générateur any(i in a for i in b)est la plus rapide sur les grandes tailles de liste;
• Testez l'intersection définie avec not set(a).isdisjoint(b), qui est toujours plus rapide que bool(set(a) & set(b)).
• L'hybride "itérer dans la liste, tester sur le plateau" a = set(a); any(i in a for i in b)est généralement plus lent que les autres méthodes.
• L'expression du générateur et l'hybride sont beaucoup plus lents que les deux autres approches lorsqu'il s'agit de listes sans partage d'éléments.

Dans la plupart des cas, l'utilisation de la isdisjoint()méthode est la meilleure approche car l'expression du générateur prendra beaucoup plus de temps à s'exécuter, car elle est très inefficace lorsqu'aucun élément n'est partagé.

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

Remarque: ce qui précède suppose que vous voulez un booléen comme réponse. Si tout ce dont vous avez besoin est une expression à utiliser dans une ifinstruction, utilisez simplementif set(a) & set(b):

def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

Ceci est asymptotiquement optimal (pire des cas O (n + m)), et pourrait être meilleur que l'approche d'intersection en raison du anycourt-circuit de de.

Par exemple:

lists_overlap([3,4,5], [1,2,3])

retournera True dès qu'il aura atteint 3 in sb

EDIT: Une autre variation (avec merci à Dave Kirby):

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

Cela repose sur imapl'itérateur de s, implémenté en C, plutôt que sur une compréhension du générateur. Il utilise également sb.__contains__comme fonction de mappage. Je ne sais pas quelle différence de performance cela fait. Il sera toujours en court-circuit.

Vous pouvez également utiliser anyavec la compréhension de liste:

any([item in a for item in b])

En python 2.6 ou version ultérieure, vous pouvez faire:

return not frozenset(a).isdisjoint(frozenset(b))

Vous pouvez utiliser toute expression de générateur de fonction / wa intégrée:

def list_overlap(a,b): 
     return any(i for i in a if i in b)

Comme John et Lie l'ont souligné, cela donne des résultats incorrects lorsque pour chaque i partagé par les deux listes bool (i) == False. Ça devrait être:

return any(i in b for i in a)

Cette question est assez ancienne, mais j'ai remarqué que pendant que les gens disputaient des ensembles contre des listes, personne n'a pensé à les utiliser ensemble. À l'exemple de Soravux,

Pire cas pour les listes:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
100.91506409645081
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
19.746716022491455
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
0.092626094818115234

Et le meilleur cas pour les listes:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=list(range(10000))", number=100000)
154.69790101051331
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000)
0.082653045654296875
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000)
0.08434605598449707

Donc, encore plus rapide que d'itérer dans deux listes, il faut itérer dans une liste pour voir si elle fait partie d'un ensemble, ce qui est logique car vérifier si un nombre est dans un ensemble prend un temps constant tandis que la vérification en itérant dans une liste prend un temps proportionnel à la longueur de la liste.

Ainsi, ma conclusion est de parcourir une liste et de vérifier si elle fait partie d'un ensemble .

si vous ne vous souciez pas de ce que pourrait être l'élément qui se chevauche, vous pouvez simplement vérifier la lenliste combinée par rapport aux listes combinées comme un ensemble. S'il y a des éléments qui se chevauchent, l'ensemble sera plus court:

len(set(a+b+c))==len(a+b+c) renvoie True, s'il n'y a pas de chevauchement.

Je vais en ajouter un autre avec un style de programmation fonctionnel:

any(map(lambda x: x in a, b))

Explication:

map(lambda x: x in a, b)

renvoie une liste de booléens où bse trouvent les éléments de a. Cette liste est ensuite passée à any, qui renvoie simplement Truesi des éléments le sont True.