Testen, ob Listen teilen alle Elemente in python

Möchte ich überprüfen, ob alle der Elemente in einer Liste vorhanden sind, in einer anderen Liste. Ich kann es einfach mit dem code unten, aber ich vermute, es könnte eine library-Funktion, um dies zu tun. Wenn nicht, ist es ein mehr pythonic Verfahren zum erreichen des gleichen Ergebnis.

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

InformationsquelleAutor der Frage fmark | 2010-07-03

208

Kurze Antwort: verwenden Sie not set(a).isdisjoint(b)es ist in der Regel die schnellsten.

Es gibt vier Allgemeine Möglichkeiten, um zu testen, ob zwei Listen a und b teilen alle Elemente. Die erste Möglichkeit ist das konvertieren der beiden Sätze und überprüfen Ihre Schnittmenge, die als solche:
```
bool(set(a) & set(b))
```
Weil sets gespeichert sind, unter Verwendung einer hash-Tabelle in Python, suchen Sie ist O(1) (siehe hier für weitere Informationen über die Komplexität der Operatoren in Python). Theoretisch ist O(n+m) im Durchschnitt für n und m Objekte in Listen a und b. Aber 1) es muss zunächst legt der Listen, die eine nicht unerhebliche Menge an Zeit, und 2) es setzt Voraus, dass Hash-Kollisionen sind spärlich unter Ihre Daten.

Den zweiten Weg, es zu tun ist mit einem generator-Ausdruck performing iteration auf die Listen, wie zum Beispiel:
```
any(i in a for i in b)
```
Dies ermöglicht die Suche in-place, also kein neuer Speicher reserviert für die intermediären Variablen. Auch Kautionen, die auf den ersten finden. Aber die in Betreiber ist immer O(n) auf Listen (siehe hier).

Anderen vorgeschlagenen option ist ein hybridto Durchlaufen der Liste haben, konvertieren Sie die andere in einen setzen, und testen Sie die Mitgliedschaft an diesem Satz, etwa so:
```
a = set(a); any(i in a for i in b)
```
Einem vierten Ansatz ist, um die Vorteile der isdisjoint() Methode der (gefrorenen)setzt (siehe hier), zum Beispiel:
```
not set(a).isdisjoint(b)
```
Wenn die Elemente, die Sie suchen, sind in der Nähe der Anfang des Arrays (z.B. sortiert ist), der generator-Ausdruck ist wichtiger, als die sets Kreuzung Methode haben, um neuen Speicher für die intermediären Variablen:
```
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
```
Hier ist ein graph, der die Ausführungszeit für dieses Beispiel in der Funktion Liste Größe:

Beachten Sie, dass beide Achsen sind logarithmisch. Dies stellt den besten Fall für den generator-Ausdruck. Wie gesehen werden kann, die isdisjoint() Methode ist besser für sehr kleine Liste mit Größen, in der Erwägung, dass der generator-Ausdruck ist besser für größere Liste Größen.

Auf der anderen Seite, als die Suche beginnt mit dem Anfang für die hybrid-und generator-Ausdruck, wenn das freigegebene element systematisch an das Ende des Arrays (oder beide Listen teilt nicht alle Werte), die disjunkt und setzen Kreuzung Ansätze sind dann schneller Weg als der generator-Ausdruck und den hybrid-Ansatz.
```
>>> 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
```
Es ist interessant zu beachten, dass der generator-Ausdruck ist der Weg langsamer, für größere Liste Größen. Dies ist nur für 1000 Wiederholungen, anstatt die 100000 für die in der vorhergehenden Abbildung. Dieses setup auch annähernd gut, wenn die keine Elemente gemeinsam sind, und ist im besten Fall für die disjunkte und setzen Kreuzung nähert.

Hier sind zwei Analyse mit zufälligen zahlen (statt der Takelage der Einrichtung zu Gunsten einer Technik oder einem anderen):

Hohe chance zu teilen: die Elemente werden nach dem Zufallsprinzip entnommen [1, 2*len(a)]. Geringe chance des Teilens: die Elemente werden nach dem Zufallsprinzip entnommen [1, 1000*len(a)].

Bis jetzt, diese Analyse soll die beiden Listen sind von der gleichen Größe. Im Fall von zwei Listen von verschiedenen Größen, zum Beispiel a ist viel kleiner, isdisjoint() ist immer schneller:

Stellen Sie sicher, dass die a Liste ist die kleinere, da sonst die Leistung sinkt. In diesem Versuch werden die a Liste Größe gesetzt wurde konstant zu 5.

In der Zusammenfassung:
- Wenn die Listen sind sehr klein (< 10 Elemente), not set(a).isdisjoint(b) ist immer die Schnellste.
- Wenn die Elemente in der Liste sortiert oder haben eine regelmäßige Struktur, die Sie nutzen können, den generator-Ausdruck any(i in a for i in b) ist der Schnellste auf der großen Liste Größen;
- Test-set Kreuzung mit not set(a).isdisjoint(b)die ist immer schneller als bool(set(a) & set(b)).
- Hybrid "Durchlaufen der Liste "test set" a = set(a); any(i in a for i in b) ist in der Regel langsamer als andere Methoden.
- Der generator-Ausdruck und der hybrid sind viel langsamer als die beiden anderen Ansätze, wenn es um Listen, ohne die Elemente.
In den meisten Fällen, mithilfe der isdisjoint() Methode ist die beste Ansatz, da die generator-Ausdruck dauert viel länger ausführen, da es sehr ineffizient, wenn keine Elemente gemeinsam sind.

InformationsquelleAutor der Antwort Soravux
23
```
def lists_overlap3(a, b):
    return bool(set(a) & set(b))
```
Hinweis: die oben geht davon aus, dass Sie möchten, dass ein boolean als Antwort. Wenn alles, was Sie brauchen, ist ein Ausdruck, der in eine if - Anweisung, verwenden Sie einfach if set(a) & set(b):

InformationsquelleAutor der Antwort John Machin
10
```
def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)
```
Dies ist asymptotisch optimal (worst-case O(n + m)), und könnte besser sein, als der Schnittpunkt Ansatz aufgrund der any's Kurzschluss.

E. g.:
```
lists_overlap([3,4,5], [1,2,3])
```
True zurück, sobald es bekommt 3 in sb

EDIT: eine Andere Variante (mit Dank an Dave Kirby):
```
def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))
```
Diese stützt sich auf die imap's iterator implementiert in C#, sondern eine generator-comprehension. Es nutzt auch sb.__contains__ als mapping-Funktion. Ich weiß nicht, wie viel performance-Unterschied macht. Es wird immer noch Kurzschluss.

InformationsquelleAutor der Antwort Matthew Flaschen
4

Könnten Sie auch any mit list-comprehension:
```
any([item in a for item in b])
```
InformationsquelleAutor der Antwort Ioachim
3

In python 2.6 oder höher, die Sie tun können:
```
return not frozenset(a).isdisjoint(frozenset(b))
```
InformationsquelleAutor der Antwort Toughy
2

Können Sie die integrierten in-Funktion /w-einen generator-Ausdruck:
```
def list_overlap(a,b): 
     return any(i for i in a if i in b)
```
Als John und Lüge haben darauf hingewiesen, dies gibt falsche Ergebnisse, wenn für alle i, die gemeinsam von den beiden Listen bool(i) == False. Es sollte sein:
```
return any(i in b for i in a)
```
InformationsquelleAutor der Antwort Anthony Conyers

Diese Frage ist ziemlich alt, aber ich bemerkte, dass, während die Menschen gestritten haben, legt gegenüber Listen, die niemand daran gedacht, mit Ihnen zusammen. Folgende Soravux Beispiel,

Schlimmsten Fall für Listen:

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

Und im besten Fall für Listen:

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

Also noch schneller als das Durchlaufen von zwei Listen wird die Iteration aber eine Liste, um zu sehen, wenn Sie in einem Satz, das macht Sinn, da die überprüfung, ob eine Zahl in einer Menge in konstanter Zeit während der Prüfung durch das Durchlaufen einer Liste braucht Zeit proportional zur Länge der Liste.

So, mein Fazit ist, dass iterieren durch eine Liste, und überprüfen, ob es in einem Satz.

InformationsquelleAutor der Antwort binoche9

1

wenn Sie nicht kümmern, was das überlappende element sein könnte, können Sie einfach überprüfen den len des kombinierten Liste vs. die Listen kombiniert als set. Wenn es gibt überlappende Elemente, die gesetzt werden kürzer:

len(set(a+b+c))==len(a+b+c) gibt True zurück, wenn es keine überschneidung.

InformationsquelleAutor der Antwort domoarigato
1

Werf ich noch einen in mit einem funktionalen Programmierung Stil:
```
any(map(lambda x: x in a, b))
```
Erklärung:
```
map(lambda x: x in a, b)
```
gibt eine Liste boolescher Werte, wobei die Elemente von b finden sich in a. Diese Liste wird dann an anydie gibt einfach True wenn alle Elemente True.

InformationsquelleAutor der Antwort cs01

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.