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
....:
list
python
intersection
fmark
źródło
źródło
len(...) > 0
ponieważ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.True
od1
iFalse
od0
.not set([1]).isdisjoint([True])
takTrue
samo jak inne rozwiązania.Odpowiedzi:
Krótka odpowiedź : używaj
not set(a).isdisjoint(b)
, generalnie jest najszybsza.Istnieją cztery typowe sposoby sprawdzenia, czy dwie listy
a
ib
udostępnienie dowolnych elementów. Pierwszą opcją jest przekonwertowanie obu na zbiory i sprawdzenie ich przecięcia, jako takie: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 toO(n+m)
średnio dla obiektówn
im
na listacha
ib
. 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
in
operator jest zawszeO(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:
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
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):
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
a
jest znacznie mniejsza,isdisjoint()
jest zawsze szybsza:Upewnij się, że
a
lista jest mniejsza, w przeciwnym razie wydajność spadnie. W tym eksperymenciea
rozmiar listy został ustawiony jako stały5
.W podsumowaniu:
not set(a).isdisjoint(b)
jest zawsze najszybsze.any(i in a for i in b)
jest najszybsze w przypadku dużych list;not set(a).isdisjoint(b)
, które jest zawsze szybsze niżbool(set(a) & set(b))
.a = set(a); any(i in a for i in b)
jest generalnie wolniejsza niż inne metody.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.źródło
any
koń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.not set(a).isdisjoint(b)
sprawdzić, czy dwie listy mają wspólnego członka.set(a).isdisjoint(b)
zwraca,True
jeśli dwie listy nie mają wspólnego członka. Odpowiedź należy zredagować?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
if
instrukcji, po prostu użyjif set(a) & set(b):
źródło
O(n + m)
. Domyślam się, że zestawy są implementowane przy użyciu tablic mieszających, a zatemin
operator może pracować wO(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ść wyszukiwaniaO(n)
, czy oznacza to, że w innym niż gorszy przypadku będzie miałaO(n * m)
wydajność?O(n)
wydajność wyszukiwania;), zobacz pastebin.com/Kn3kAW7u Tylko dla lafs.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
any
zwarcia.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
imap
iteratorze, 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.źródło
any(itertools.imap(sb.__contains__, a))
który powinien być jeszcze szybszy, ponieważ unika używania funkcji lambda.Możesz również użyć
any
ze zrozumieniem listy:any([item in a for item in b])
źródło
[]
) i działałoby szybciej i zużywałoby mniej pamięci, ale czas nadal byłby O (n * m).W Pythonie 2.6 lub nowszym możesz:
return not frozenset(a).isdisjoint(frozenset(b))
źródło
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)
źródło
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)
.x
przecięcia są takie, jakimibool(x)
sąFalse
.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 .
źródło
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,00913715362548828jeśli nie obchodzi cię, jaki może być nakładający się element, możesz po prostu sprawdzić
len
połą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ę.źródło
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
b
znajdują się wa
. Ta lista jest następnie przekazywana doany
, który po prostu zwraca,True
jeśli jakieś elementy sąTrue
.źródło
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
źródło