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

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

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:

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 ajest znacznie mniejsza, isdisjoint()jest zawsze szybsza:

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.

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

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.

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

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

W Pythonie 2.6 lub nowszym możesz:

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

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)

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 .

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

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.

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