Sprawdź, czy listy współużytkują jakiekolwiek elementy w Pythonie

136

Chcę sprawdzić, czy któryś z elementów jednej listy znajduje się na innej liście. Mogę to zrobić po prostu za pomocą poniższego kodu, ale podejrzewam, że może to być funkcja biblioteki. Jeśli nie, to czy istnieje bardziej pytoniczna metoda osiągnięcia tego samego wyniku.

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
   ....: 
fmark
źródło
Jedyne optymalizacje, jakie przychodzą mi do głowy, spadają, len(...) > 0ponieważ bool(set([]))daje wartość Fałsz. I oczywiście, jeśli na początku trzymasz listy jako zestawy, zaoszczędzisz na kosztach tworzenia zestawów.
msw
Istotne: stackoverflow.com/a/44786707/1959808
Ioannis Filippidis
1
Zauważ, że nie możesz odróżnić Trueod 1i Falseod 0. not set([1]).isdisjoint([True])tak Truesamo jak inne rozwiązania.
Dimali

Odpowiedzi:

330

Krótka odpowiedź : używaj not set(a).isdisjoint(b), generalnie jest najszybsza.

Istnieją cztery typowe sposoby sprawdzenia, czy dwie listy ai budostępnienie dowolnych elementów. Pierwszą opcją jest przekonwertowanie obu na zbiory i sprawdzenie ich przecięcia, jako takie:

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

Ponieważ zestawy są przechowywane w Pythonie przy użyciu tablicy skrótów, wyszukiwanie ich odbywa sięO(1) (zobacz tutaj, aby uzyskać więcej informacji o złożoności operatorów w Pythonie). Teoretycznie jest to O(n+m)średnio dla obiektów ni mna listach ai b. Ale 1) musi najpierw utworzyć zestawy z list, co może zająć dużo czasu, a 2) zakłada, że ​​kolizje haszowania są rzadkie wśród twoich danych.

Drugim sposobem jest użycie wyrażenia generatora wykonującego iterację na listach, takich jak:

any(i in a for i in b)

Pozwala to na wyszukiwanie w miejscu, więc żadna nowa pamięć nie jest przydzielana dla zmiennych pośrednich. Wyskakuje również przy pierwszym znalezieniu. Ale inoperator jest zawsze O(n)na listach (patrz tutaj ).

Inną proponowaną opcją jest hybryda polegająca na iteracji jednej z list, konwersji drugiej w zestawie i przetestowaniu członkostwa w tym zestawie, na przykład:

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

Czwartym podejściem jest wykorzystanie isdisjoint()metody (zamrożonych) zbiorów (patrz tutaj ), na przykład:

not set(a).isdisjoint(b)

Jeśli wyszukiwane elementy znajdują się blisko początku tablicy (np. Są posortowane), preferowane jest wyrażenie generatora, ponieważ metoda intersection zestawów musi przydzielić nową pamięć dla zmiennych pośrednich:

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 wykonywania dla tego przykładu w funkcji rozmiaru listy:

Czas wykonania testu współdzielenia elementu, gdy został udostępniony na początku

Zauważ, że obie osie są logarytmiczne. Stanowi to najlepszy przypadek dla wyrażenia generatora. Jak widać, isdisjoint()metoda jest lepsza dla list o bardzo małych rozmiarach, natomiast wyrażenie generatora jest lepsze dla list o większych rozmiarach.

Z drugiej strony, ponieważ wyszukiwanie rozpoczyna się od początku wyrażenia hybrydy i generatora, jeśli element współdzielony znajduje się systematycznie na końcu tablicy (lub obie listy nie mają wspólnych wartości), wówczas podejścia rozłączne i zestaw przecięć są znacznie szybciej niż wyrażenie 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

Czas wykonania testu współdzielenia elementu po udostępnieniu na końcu

Warto zauważyć, że wyrażenie generatora jest znacznie wolniejsze dla większych list. To tylko dla 1000 powtórzeń, zamiast 100000 dla poprzedniej figury. Ta konfiguracja jest również dobrze przybliżana, gdy żadne elementy nie są współdzielone, i jest najlepszym przypadkiem dla podejść rozłącznych i zestawionych przecięć.

Oto dwie analizy z wykorzystaniem liczb losowych (zamiast fałszować konfigurację na korzyść jednej lub drugiej techniki):

Czas wykonania testu udostępniania elementu dla losowo generowanych danych z dużą szansą na udostępnienie Czas wykonania testu udostępniania elementu dla losowo generowanych danych z dużą szansą na udostępnienie

Duża szansa na udostępnienie: elementy są pobierane losowo [1, 2*len(a)]. Mała szansa na udostępnienie: elementy są pobierane losowo [1, 1000*len(a)].

Do tej pory ta analiza zakładała, że ​​obie listy są tej samej wielkości. W przypadku dwóch list o różnych rozmiarach, na przykład ajest znacznie mniejsza, isdisjoint()jest zawsze szybsza:

Czas wykonania testu udostępniania elementu na dwóch listach o różnej wielkości, gdy są udostępniane na początku Czas wykonania testu współdzielenia elementu na dwóch listach o różnej wielkości po udostępnieniu na końcu

Upewnij się, że alista jest mniejsza, w przeciwnym razie wydajność spadnie. W tym eksperymencie arozmiar listy został ustawiony jako stały 5.

W podsumowaniu:

  • Jeśli listy są bardzo małe (<10 elementów), not set(a).isdisjoint(b)jest zawsze najszybsze.
  • Jeśli elementy na listach 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 w przypadku dużych list;
  • Przetestuj ustawione przecięcie z not set(a).isdisjoint(b), które jest zawsze szybsze niż bool(set(a) & set(b)).
  • Metoda hybrydowa „iteruj po liście, testuj 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 współdzielenia elementów.

W większości przypadków użycie tej isdisjoint()metody jest najlepszym podejściem, ponieważ wykonanie wyrażenia generatora zajmie znacznie więcej czasu, ponieważ jest bardzo nieefektywne, gdy żadne elementy nie są współużytkowane.

Soravux
źródło
8
To kilka przydatnych danych, które pokazują, że analiza Big-O to nie wszystko i koniec wszystkich rozumowań dotyczących czasu pracy.
Steve Allison,
co z najgorszym scenariuszem? anykończy działanie przy pierwszej wartości innej niż Fałsz. Używając listy, w której jedyna pasująca wartość znajduje się na końcu, otrzymujemy: 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 ... i ma tylko 1000 iteracji.
RobM
2
Dzięki @RobM za informacje. Zaktualizowałem moją odpowiedź, aby to odzwierciedlić i uwzględnić inne techniki zaproponowane w tym wątku.
Soravux
Należy not set(a).isdisjoint(b)sprawdzić, czy dwie listy mają wspólnego członka. set(a).isdisjoint(b)zwraca, Truejeśli dwie listy nie mają wspólnego członka. Odpowiedź należy zredagować?
Guillochon
1
Dzięki za ostrzeżenie, @Guillochon, to naprawione.
Soravux
25
def lists_overlap3(a, b):
    return bool(set(a) & set(b))

Uwaga: powyższe zakłada, że ​​chcesz użyć wartości logicznej jako odpowiedzi. Jeśli potrzebujesz tylko wyrażenia do użycia w ifinstrukcji, po prostu użyjif set(a) & set(b):

John Machin
źródło
5
To jest w najgorszym przypadku O (n + m). Jednak wadą jest to, że tworzy nowy zestaw i nie wyskakuje, gdy wspólny element zostanie znaleziony wcześnie.
Matthew Flaschen,
1
Ciekaw jestem, dlaczego tak jest O(n + m). Domyślam się, że zestawy są implementowane przy użyciu tablic mieszających, a zatem inoperator może pracować w O(1)czasie (z wyjątkiem przypadków zdegenerowanych). Czy to jest poprawne? Jeśli tak, biorąc pod uwagę, że tablice skrótów mają najgorszą wydajność wyszukiwania O(n), czy oznacza to, że w innym niż gorszy przypadku będzie miała O(n * m)wydajność?
fmark
1
@fmark: Teoretycznie masz rację. Praktycznie nikogo to nie obchodzi; przeczytaj komentarze w Objects / dictobject.c w źródle CPythona (zestawy to tylko dykty zawierające tylko klucze, bez wartości) i zobacz, czy możesz wygenerować listę kluczy, które spowodują wydajność wyszukiwania O (n).
John Machin,
Okay, dzięki za wyjaśnienie, zastanawiałem się, czy dzieje się jakaś magia :). Chociaż zgadzam się, że praktycznie nie muszę się tym przejmować, to trywialne jest wygenerowanie listy kluczy, które spowodują O(n)wydajność wyszukiwania;), zobacz pastebin.com/Kn3kAW7u Tylko dla lafs.
fmark
2
Tak, wiem. Dodatkowo właśnie przeczytałem źródło, które mi wskazałeś, które dokumentuje jeszcze więcej magii w przypadku nielosowych funkcji skrótu (takich jak wbudowana). Założyłem, że wymaga to losowości, jak w Javie, co skutkuje potworami, takimi jak ten stackoverflow.com/questions/2634690/… . Muszę sobie ciągle przypominać, że Python to nie Java (dzięki Bogu!).
fmark
10
def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

Jest to asymptotycznie optymalne (najgorszy przypadek O (n + m)) i może być lepsze niż podejście przez skrzyżowanie z powodu anyzwarcia.

Na przykład:

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

zwróci True tak szybko, jak to nastąpi 3 in sb

EDYCJA: Kolejna odmiana (dzięki Dave Kirby):

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

Opiera się to na imapiteratorze, który jest zaimplementowany w C, a nie na zrozumieniu generatora. Używa również sb.__contains__jako funkcji mapowania. Nie wiem, jak duża to różnica w wydajności. Nadal będzie zwarcie.

Matthew Flaschen
źródło
1
Wszystkie pętle w podejściu skrzyżowanym są w kodzie C; w Twoim podejściu jest jedna pętla, która obejmuje kod Pythona. Wielką niewiadomą jest to, czy puste skrzyżowanie jest prawdopodobne, czy mało prawdopodobne.
John Machin,
2
Możesz także użyć tego, any(itertools.imap(sb.__contains__, a))który powinien być jeszcze szybszy, ponieważ unika używania funkcji lambda.
Dave Kirby,
Dzięki, @Dave. :) Zgadzam się, że usunięcie lambdy to wygrana.
Matthew Flaschen,
4

Możesz również użyć anyze zrozumieniem listy:

any([item in a for item in b])
Ioachim
źródło
6
Mógłbyś, ale czas to O (n * m), podczas gdy czas dla podejścia do punktu przecięcia to O (n + m). Możesz to również zrobić BEZ rozumienia listy (stracić []) i działałoby szybciej i zużywałoby mniej pamięci, ale czas nadal byłby O (n * m).
John Machin,
1
Chociaż twoja duża analiza O jest prawdziwa, podejrzewam, że w przypadku małych wartości ni m czas potrzebny na zbudowanie bazowych tabel mieszających będzie miał znaczenie. Duże O ignoruje czas potrzebny na obliczenie skrótów.
Anthony Conyers,
2
Budowanie „tablicy hashy” jest amortyzowane O (n).
John Machin,
1
Rozumiem, ale stała, którą wyrzucasz, jest dość duża. Nie ma to znaczenia dla dużych wartości n, ale ma znaczenie dla małych.
Anthony Conyers,
3

W Pythonie 2.6 lub nowszym możesz:

return not frozenset(a).isdisjoint(frozenset(b))
Twardy
źródło
1
Wygląda na to, że jako pierwszy argument nie trzeba podawać zestawu ani zestawu zamrożonego. Próbowałem ze stringiem i zadziałało (tj .: jakakolwiek iterowalna zrobi).
Aktau
2

Możesz użyć dowolnego wbudowanego wyrażenia generatora funkcji / wa:

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

Jak zauważyli John i Lie, daje to niepoprawne wyniki, gdy dla każdego i współdzielonego przez obie listy bool (i) == False. Powinno być:

return any(i in b for i in a)
Anthony Conyers
źródło
1
Wzmocnienie komentarza Lie Ryan: da zły wynik dla każdego elementu x, który znajduje się w przecięciu, gdzie bool(x)jest Fałsz. W przykładzie Lie Ryan x wynosi 0. Jedyną poprawką jest to, any(True for i in a if i in b)co jest lepiej napisane, jak już widać any(i in b for i in a).
John Machin,
1
Korekta: da zły wynik, gdy wszystkie elementy xprzecięcia są takie, jakimi bool(x)False.
John Machin,
1

To pytanie jest dość stare, ale zauważyłem, że kiedy ludzie dyskutowali o zestawach z listami, nikt nie pomyślał o użyciu ich razem. Idąc za przykładem Soravux,

Najgorszy przypadek dla list:

>>> 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 najlepszy przypadek dla 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 szybsze niż iterowanie po dwóch listach jest iteracja przez listę w celu sprawdzenia, czy jest w zestawie, co ma sens, ponieważ sprawdzenie, czy liczba znajduje się w zestawie, zajmuje ciągły czas, podczas gdy sprawdzenie przez iterację listy zajmuje czas proporcjonalny do długości Lista.

Dlatego dochodzę do wniosku, że należy powtórzyć listę i sprawdzić, czy jest w zestawie .

binoche9
źródło
1
Korzystanie z isdisjoint()metody na (zamrożonym) zestawie, jak wskazano przez @Toughy, jest jeszcze lepsze: 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,00913715362548828
Aktau
1

jeśli nie obchodzi cię, jaki może być nakładający się element, możesz po prostu sprawdzić lenpołączoną listę w porównaniu z listami połączonymi jako zestaw. Jeśli elementy nakładają się na siebie, zestaw będzie krótszy:

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

domoarigato
źródło
Jeśli pierwsza wartość nakłada się, nadal konwertuje całą listę na zestaw, bez względu na to, jak duży.
Peter Wood
1

Dorzucę kolejny z funkcjonalnym stylem programowania:

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

Wyjaśnienie:

map(lambda x: x in a, b)

zwraca listę logicznych gdzie elementy bznajdują się w a. Ta lista jest następnie przekazywana do any, który po prostu zwraca, Truejeśli jakieś elementy są True.

cs01
źródło
-1

Jeśli chcesz sprawdzić, czy cała lista znajduje się na liście, możesz również to zrobić.

index = 0
for a in list_one:
    for _ in list_two: 
        if a == list_two[index]:
            print("match")
            index += 1
        else:
            print("this list did not match at index" + str(index))
            index += 1
Santiago Palomares
źródło