Test si les listes partagent des articles en python

je veux vérifier si tout des éléments dans une liste 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. Si non, est-il plus pythonic méthode pour atteindre 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
   ....:
86
demandé sur fmark 2010-07-03 06:15:15

9 réponses

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

il y a quatre façons courantes de vérifier si deux listes a et b partagent des articles. La première option est de convertir les deux ensembles et de vérifier leur intersection, comme tel: 

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

parce que les ensembles sont stockés en utilisant une table de hachage en Python, la recherche est O(1) (voir ici) pour plus d'informations sur la complexité des opérateurs en Python). Théoriquement, c'est O(n+m) en moyenne pour n et m objets dans les listes a et b . Mais 1) il doit d'abord créer des ensembles des listes, ce qui peut prendre une quantité non négligeable de temps, et 2) Il suppose que les collisions de hachage sont clairsemées parmi vos données.

la deuxième façon de le faire est d'utiliser une expression génératrice effectuant une itération sur le listes, telles que: 

any(i in a for i in b)

cela permet de rechercher en place, de sorte qu'aucune nouvelle mémoire n'est attribuée pour les variables intermédiaires. Il sort aussi à la première découverte. mais l'opérateur in est toujours O(n) sur les listes (voir ici ).

une autre option proposée est un hybridto iterate à travers l'une de la liste, convertir l'autre dans un ensemble et tester pour l'adhésion sur cet ensemble, comme si: 

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

une quatrième approche consiste à tirer parti de la méthode isdisjoint() des ensembles (congelé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 generator est favorisé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 pour cet exemple en fonction de la taille de la liste:

Element sharing test execution time when shared at the beginning

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

d'autre part, comme la recherche commence avec le début des expressions hybrid et generator, si l'élément partagé est systématiquement à la fin du tableau (ou si les deux listes ne partagent aucune valeur), les approches disjoint et set intersection sont alors beaucoup plus rapides que l'expression generator et l'approche hybrid. 

>>> 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

Element sharing test execution time when shared at the end

il est intéressant de noter que l'expression du générateur est beaucoup plus lente pour les gros liste des tailles. Cela est seulement pour 1000 répétitions, au lieu de 100000 pour le chiffre précédent. Cette configuration se rapproche aussi bien quand aucun élément n'est partagé, et est le meilleur cas pour les approches disjoint et set intersection.

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

Element sharing test execution time for randomly generated data with high chance of sharing Element sharing test execution time for randomly generated data with high chance of sharing

grande chance de partage: les éléments sont sélectionnés au hasard à partir de [1, 2*len(a)] . Faible chance de partage: les éléments sont tirés au hasard de [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 a est beaucoup plus petit, isdisjoint() est toujours plus rapide:

Element sharing test execution time on two differently sized lists when shared at the beginning Element sharing test execution time on two differently sized lists when shared at the end

s'assurer que la liste a est la plus petite, sinon la performance diminue. Dans cette expérience, la taille de la liste a a été fixée à 5 .

en résumé:

  • si les listes sont très petites (< 10 éléments), not set(a).isdisjoint(b) est toujours le plus rapide.
  • si les éléments des listes sont triés ou avoir une structure régulière dont vous pouvez profiter, l'expression de générateur any(i in a for i in b) est la plus rapide sur les grandes tailles de liste;
  • Tester le niveau de l'intersection avec not set(a).isdisjoint(b) , ce qui est toujours plus rapide que le bool(set(a) & set(b)) .
  • L'hybride "itérer sur la liste de, essai sur set" 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 d'autres approches quand il s'agit de listes sans partage d'éléments.

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

206
répondu Soravux 2017-02-15 15:01:07 
def lists_overlap3(a, b):
    return bool(set(a) & set(b))

Note: ce qui précède suppose que vous voulez un booléen comme réponse. Si vous n'avez besoin que d'une expression à utiliser dans une instruction if , utilisez simplement if set(a) & set(b):

23
répondu John Machin 2010-07-03 02:21:39 
def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

c'est asymptotiquement optimal (worst case O(n + m)), et pourrait être meilleur que l'approche d'intersection en raison de any court-circuitage.

par exemple: 

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

retournera vrai dès qu'il arrivera à 3 in sb

EDIT: une Autre variante (merci à Dave Kirby): 

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

cela s'appuie sur l'itérateur de imap , qui est mis en œuvre dans C, plutôt qu'une compréhension génératrice. Il utilise également sb.__contains__ comme fonction de cartographie. Je ne sais pas combien de performance de la différence que cela fait. Il sera toujours en court-circuit.

10
répondu Matthew Flaschen 2010-07-03 23:35:24

vous pouvez également utiliser any avec la compréhension de liste: 

any([item in a for item in b])
4
répondu Ioachim 2010-07-03 02:23:42

en python 2.6 ou plus tard vous pouvez faire: 

return not frozenset(a).isdisjoint(frozenset(b))
3
répondu Toughy 2012-11-13 10:49:47

vous pouvez utiliser l'expression n'importe quelle fonction intégrée /w un générateur: 

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

comme John et Lie l'ont fait remarquer, cela donne des résultats incorrects quand pour chaque Je partagé par les deux listes bool(i) == False. Il devrait être: 

return any(i in b for i in a)
2
répondu Anthony Conyers 2010-07-03 13:47:19

cette question est assez ancienne, mais j'ai remarqué que pendant que les gens se disputaient sets vs listes, que personne ne pensait à les utiliser ensemble. Suivant L'exemple de Soravux,

Pire des 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 même plus rapide que l'itération à travers deux listes est itération à travers une liste pour voir si elle est dans un ensemble, ce qui a du sens depuis la vérification si un nombre est dans un ensemble prend le temps constant tandis que la vérification par itération à travers une liste prend le temps proportionnel à la longueur de la liste.

ainsi, ma conclusion est que itérer à travers une liste, et vérifier si elle est dans un ensemble .

1
répondu binoche9 2014-10-08 22:09:27

si vous ne vous souciez pas de ce que l'élément de chevauchement pourrait être, vous pouvez simplement vérifier le len de la liste combinée vs. les 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) retourne True, s'il n'y a pas de chevauchement.

1
répondu domoarigato 2015-03-10 16:11:06

je vais jeter un autre avec un style de programmation fonctionnelle: 

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

explication: 

map(lambda x: x in a, b)

renvoie une liste de booléens où les éléments de b se trouvent dans a . Cette liste est ensuite passée à any , qui renvoie simplement True si l'un des éléments est True .

1
répondu cs01 2016-11-09 18:08:56