Sprawdź, czy listy udostępniają jakiekolwiek elementy w pythonie

Question

Chcę sprawdzić, czy dowolne pozycji na jednej liście są obecne na innej liście. Mogę to zrobić po prostu za pomocą poniższego kodu, ale podejrzewam, że może to być funkcja biblioteczna. Jeśli nie, to jest bardziej pytona metoda osiągnięcia tego samego rezultatu.

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

Answer 1

Krótka odpowiedź: użyj not set(a).isdisjoint(b), to zwykle najszybszy.

Istnieją cztery popularne sposoby testowania, czy dwie listy a i b udostępniają jakiekolwiek elementy. Pierwsza opcja jest przekształcenie zarówno do zestawów i sprawdzić ich przecięcia, jako takich:

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

Ponieważ zestawy są przechowywane przy użyciu tabeli mieszania w Pythonie, szukając ich jest O(1) (patrz here uzyskać więcej informacji na temat złożoności operatorzy w Pythonie). Teoretycznie jest to O(n+m) średnio dla obiektów n i m na listach a i b. Ale 1) musi najpierw utworzyć zestawy z list, które mogą trwać niezauważalnie długo i 2) zakłada, że ​​kolizje mieszania są rzadkie wśród danych.

Drugi sposób to zrobić jest użycie wyrażenia generatora wykonywania iteracji na listach, takich jak:

any(i in a for i in b) 

Pozwala to, aby szukać w miejscu, więc żadna nowa pamięć jest alokowana do zmiennych pośredniczących. Dotyczy to również pierwszego znaleziska. Ale operator in jest zawsze O(n) na listach (patrz).

Innym proponowanym rozwiązaniem jest iterate hybridto przez jeden z listy, przekształcić drugi w zbiorze oraz testu dla członkostwa na tym zestawie, tak jak poniżej:

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

Czwarte podejście do skorzystania z metoda isdisjoint() z (mrożone) zestawów (patrz here), na przykład:

not set(a).isdisjoint(b) 

Jeśli elementy Wyszukiwane są blisko początku tablicy (np to jest posortowana), wyrażenie generator jest faworyzowany, jak zestawy przecinają mnie TZT trzeba przydzielić nową pamięć dla zmiennych pośredniczących:

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 

Oto wykres czasu wykonania dla tego przykładu, w zależności od wielkości listy:

Należy zauważyć, że obie osie są logarytmiczna. Jest to najlepszy przypadek dla wyrażenia generatora. Jak widać, metoda isdisjoint() jest lepsza dla bardzo małych rozmiarów list, podczas gdy wyrażenie generatora jest lepsze dla większych rozmiarów list.

Z drugiej strony, gdy wyszukiwanie rozpoczyna się od początku wyrażenia hybrydowego i generatora, jeśli element wspólny jest systematycznie na końcu tablicy (lub obie listy nie współdzielą żadnych wartości), rozłączne i ustawione podejścia skrzyżowania są wtedy znacznie szybsze niż ekspresja generatora i podejście hybrydowe.

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

Ciekawostką jest, aby pamiętać, że wyrażenie generator jest sposób wolniej lista większych rozmiarach. To jest tylko dla 1000 powtórzeń, zamiast 100000 dla poprzedniej figury. Ta konfiguracja jest również dobrze przybliżona, gdy nie są udostępniane żadne elementy, i jest najlepszym rozwiązaniem dla podejść rozłącznych i zestawionych przecięć.

Oto dwa analiza za pomocą liczb losowych (zamiast olinowanie konfigurację do faworyzowania jednej techniki lub inny):

wysoka szansa dzielenia: Elementy są losowo z [1, 2*len(a)]. Niska szansa na udostępnienie: elementy są losowo pobierane z [1, 1000*len(a)].

Do tej pory ta analiza zakładała, że ​​obie listy mają ten sam rozmiar.W przypadku dwóch list o różnych rozmiarach, na przykład a jest znacznie mniejsze, isdisjoint() zawsze jest szybsze:

Upewnij się, że lista a jest mniejszy, w przeciwnym razie wydajność spada. W tym eksperymencie rozmiar listy a ustalono jako stały na 5.

Podsumowując:

• Jeśli listy są bardzo małe (< 10 elementów), not set(a).isdisjoint(b) zawsze jest najszybszy.
• Jeśli elementy na liście są posortowane lub mają regularną strukturę, z której można skorzystać, wyrażenie generatora any(i in a for i in b) jest najszybsze na dużych rozmiarach list;
• Sprawdź zestaw skrzyżowania z not set(a).isdisjoint(b), który zawsze jest szybszy niż bool(set(a) & set(b)).
• Hybrydowa "lista iteracji, test na zestawie" a = set(a); any(i in a for i in b) jest generalnie wolniejsza niż inne metody.
• Wyrażenie generatora i hybryda są znacznie wolniejsze niż dwa inne podejścia, jeśli chodzi o listy bez elementów współużytkowania.

W większości przypadków najlepszym rozwiązaniem jest użycie metody isdisjoint(), ponieważ wyrażenie generatora będzie trwało dłużej, ponieważ jest bardzo nieefektywne, gdy nie są udostępniane żadne elementy.

Answer 2

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

Uwaga: powyższy zakłada, że ​​chcesz logiczną jako odpowiedź. Jeśli wszystko, co potrzebne jest wyrazem używać w instrukcji if, wystarczy użyć if set(a) & set(b):

Answer 3

Można też użyć any z listowego:

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

Answer 4

Można użyć dowolnego zbudowany w funkcji/wa generatora wyrażenie:

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

Jak John i Lie podkreśliło to daje niepoprawne wyniki, gdy dla każdego i dzielone przez dwie listy bool (i) == false. Powinno być:

return any(i in b for i in a) 

Answer 5

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

asymptotycznie to optymalne (najgorszy przypadek O (n + m)), i może być lepszy niż podejście przecięcia z powodu any jest zwierającego.

Np

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

powróci prawda tak szybko, jak to robi się 3 in sb

EDIT: Kolejna wariacja (ze dzięki Dave Kirby):

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

ta opiera się na imap iterator, który jest zaimplementowany w C, a nie generatora. Używa również funkcji mapowania jako sb.__contains__. Nie wiem, jak wiele to powoduje. Nadal będzie trwało zwarcie.

Answer 6

W Pythonie 2.6 lub nowszej można zrobić:

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

Answer 7

To pytanie jest dość stare, ale zauważyłem, że podczas gdy ludzie kłócili się z setami kontra listami, nikt nie pomyślał o ich użyciu. Poniższy przykład Soravux, w

Najgorszy przypadek na listach:

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

A najlepszym przypadku list:

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

Więc nawet szybciej niż iteracja dwóch list jest iteracja choć lista aby sprawdzić, czy jest w zbiorze, co ma sens, ponieważ sprawdzenie, czy liczba jest w zbiorze, zajmuje stały czas, podczas gdy sprawdzanie poprzez iterację listy zajmuje czas proporcjonalny do długości listy.

Tak więc, mój wniosek jest taki, że iteruje listę i sprawdza, czy jest w zestawie.

Answer 8

Jeśli nie obchodzi Cię, co może się pokrywać, możesz po prostu sprawdzić len połączonej listy w porównaniu do list połączonych jako zestaw. Jeśli zachodzą na siebie elementy, zestaw będzie krótszy:

len(set(a+b+c))==len(a+b+c) zwraca True, jeśli nie ma nakładania się.

Answer 9

dorzucę jeszcze jeden wz funkcjonalnym stylu programowania:

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

Objaśnienie:

map(lambda x: x in a, b) 

zwraca listę logicznych gdzie elementy b znajdują się w a. Ta lista jest następnie przekazywana do any, która po prostu zwraca True, jeśli jakiekolwiek elementy są True.