porównaj, czy element istnieje na dwóch listach

Question

Jaki byłby najłatwiejszy i najbardziej elegancki sposób sprawdzenia, czy dany element istnieje na dwóch podanych listach. Na przykład mam dwie listy w następujący sposób?

>>>a, b = ['a', 'b', 'g', 'r'], ['e', 'g', 'l', 1, 'w'] 

Teraz na powyższych listach chcę sprawdzić, czy istnieje jakiś element, który istnieje na obu listach. Obecnie robię to w następujący sposób:

def elm_exists(list_a, list_b): 
    for elm in list_a: 
     if elm in list_b: 
      return True 
    return False 

Czy istnieje bardziej elegancki sposób robienia tego?

Answer 1

elementy sprawdzenie a i b z tym:

set(a).intersection(b) 

przykład:

In [44]: nk=set(a).intersection(b) 

In [45]: for x in a: 
    ...:  if x in nk: 
    ...:   print x, 'present in b' 
    ...:  else: 
    ...:   print x, 'absent in b' 
    ...:   
a absent in b 
b absent in b 
g present in b 
r absent in b 

również:

In [47]: timeit(set(a) & set(b)) 
1000000 loops, best of 3: 940 ns per loop 

In [48]: timeit(set(a).intersection(b)) 
1000000 loops, best of 3: 854 ns per loop 

In [49]: timeit([x for x in a if x in b]) 
1000000 loops, best of 3: 1 us per loop 

stąd używać set(a).intersection(b).

Answer 2

to działa:

>>> l1,l2=['a', 'b', 'g', 'r'], ['e', 'g', 'l', 1, 'w'] 
>>> list(set(l1)&set(l2)) 
['g'] 

Answer 3

def elm_exists(lista, listb): 
    return bool(set(lista) & set(listb)) 

Funkcja bool powróci True dla wszystkich bez pustych kontenerów oraz False dla pustych. Ustawione przecięcie (&) zwróci zestaw wspólnych elementów z dwóch zestawów. Zwróć uwagę, że zestawy usuwają wszelkie duplikaty.

Alternatywnie można użyć funkcji set(lista).intersection(listb) w funkcji bool.

Answer 4

>>> y = [1,23,3] 
>>> z = [3,432] 
>>> (3 in y) and (3 in z) 
True 

Answer 5

Nie trzeba konwertować zarówno list s do set s, zaledwie jedną. Myślę, że pomijanie niepotrzebnej konwersji czyni ją bardziej czytelną i elegancką.

Więc albo:

set(a).intersection(b) 

Lub:

s = set(a) 
any(e in s for e in b) 

Ta ostatnia ma tę zaletę, zwarcie, gdy tylko stwierdzi jeden mecz, a lepiej wyrażając logikę i powrocie True lub False zamiast bez falsey lub falsey set, ale jest to dwie linie zamiast jednej, jeśli ci to przeszkadza. Nie mam pojęcia, czy ta korzyść unieważnia koszt wprowadzenia pętli do wyrażenia generatora zamiast do funkcji C.

wyniki wydajności z list s to małe są prawie bez znaczenia, więc spróbujmy to:

In [373]: a=[random.choice(string.ascii_lowercase) for _ in range(10000)] 
In [374]: b=[random.choice(string.ascii_lowercase) for _ in range(10000)] 
In [375]: %timeit(set(a)) 
10000 loops, best of 3: 180 us per loop 
In [376]: s=set(a) # since all versions need to do this 
In [391]: %timeit(s & set(b)) 
1000000 loops, best of 3: 178 us per loop 
In [392]: %timeit(s.intersection(b)) 
1000000 loops, best of 3: 247 us per loop 
In [393]: %timeit(discard(e in s for e in b)) 
1000000 loops, best of 3: 550 ns per loop 
In [394]: %timeit(any(e in s for e in b)) 
1000000 loops, best of 3: 749 ns per loop 
In [395]: %timeit(any(e in a for e in b)) 
1000000 loops, best of 3: 1.42 us per loop 

Aby umieścić numery wszystkich w skali nanosekundy, dodać z powrotem w kosztach set(a) że wszystkie oprócz ostatniego potrzebujesz i porównaj te same testy z trzech wersji Pythona (Apple stock CPython 2.7.2, python.org CPython 3.3.0, Homebrew PyPy 1.9.0/2.7.2, wszystkie 64-bitowe Mac buduje):

    CP272 CP330 PyPy 
s & set(b)  358000 316000 180500 
s.intersection(b) 427000 459000 180900 
discard(genexp) 180550 157341 90094 
any(genexp)  180749 157334 90208 
any(list-genexp) 1420 686 960 

Teraz, gdy o tym myślę, to sprawia, że ​​całkowity sens. Szanse na wczesne zderzenie są bardzo wysokie, więc koszt konwersji całości do zestawu dominuje we wszystkim.

Co oznacza, że ​​potrzebujemy nowego testu z 10000 unikatowych wartości. Powtórzmy test, z tym:

In [29]: a, b = list(range(10000)), list(range(10000)) 
In [30]: random.shuffle(a) 
In [31]: random.shuffle(b) 

        CP272 CP330 PyPy 
s & set(b)  1277000 1168000 1141000 
s.intersection(b) 1165000 1117000 2520000 
discard(genexp) 1699000 1271000 770000 
any(genexp)  389800 344543 320807 
any(list-genexp) 62000 10400 1520 

Są to bardziej uzasadnione. I nadal mają sens. Jeśli porównujesz te same 10000 elementów losowo przetasowane, jak daleko w każdym z nich musisz iść? Nie dość, aby kosztować set - co oznacza jedną z list wartych zrobienia, a tym bardziej obie!

Więc spróbujmy przypadek, w którym nie istnieją mecze:

In [43]: a=list(range(10000, 20000)) 


        CP272  CP330  PyPy 
s & set(b)   751000 770000 733000 
s.intersection(b) 466000 530000 1920000 
discard(genexp)  1246000 985000 749000 
any(genexp)   1269000 966000 893000 
any(list-genexp) 185000000 176000000 5870000 

nie mam pojęcia, jak pypy zrobił ostatni tak szybki, ale poza tym, tu nie ma niespodzianek.

Który z nich jest najlepszy?

Oczywiście, jeśli spodziewasz się wielu kolizji, unikaj tworzenia zestawów, jeśli to możliwe - ale jeśli spodziewasz się kilku kolizji, chcesz zrobić co najmniej jeden zestaw. Jeśli nie masz pojęcia, myślę, że najbezpieczniejszym zakładem jest any(genexp) - w najgorszym wypadku jest to mniej niż 3 razy mniej niż najlepsze, a jeśli jest szansa, że ​​współczynnik kolizji jest wysoki, będzie o wiele szybciej. Ale możesz spojrzeć na liczby i przekonać się samemu.

Lub, lepiej, oczywiście, czas na wszystkie z prawdziwymi danymi testowymi, które spodziewają się spotkać.

Answer 6

To jest inne rozwiązanie,

>>> c = [filter(lambda x: x in b, sublist) for sublist in a] 
>>> filter (lambda a: a != '', c) 
['g']