Jak znaleźć przecięcie listy?

203
a = [1,2,3,4,5]
b = [1,3,5,6]
c = a and b
print c

rzeczywista wydajność: [1,3,5,6] oczekiwana wydajność:[1,3,5]

Jak możemy uzyskać operację logiczną AND (przecięcie listy) na dwóch listach?

csguy11
źródło
6
Problem polega na tym, że a and bdziała tak, jak wspomina to następująca instrukcja z dokumentacji : „ Wyrażenie x and ynajpierw ocenia x; jeśli xjest fałszywe, jego wartość jest zwracana; w przeciwnym razie yjest oceniana, a wynikowa wartość jest zwracana.
Tadeck

Odpowiedzi:

347

Jeśli kolejność nie jest ważna i nie musisz się martwić o duplikaty, możesz użyć ustawienia skrzyżowania:

>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> list(set(a) & set(b))
[1, 3, 5]
Mark Byers
źródło
9
co jeśli a = [1,1,2,3,4,5]i b = [1,1,3,5,6]wtedy skrzyżowanie jest, [1,1,3,5]ale powyższa metoda spowoduje tylko jeden, 1tj. [1, 3, 5]jaki będzie wtedy sposób zapisu?
Nitish Kumar Pal,
6
@NItishKumarPal intersectionjest powszechnie rozumiany jako oparty na ustawieniach . Szukasz nieco innego zwierzęcia - być może będziesz musiał to zrobić ręcznie, sortując każdą listę i łącząc wyniki - i utrzymując dups w łączeniu.
javadba
1
@MarkByers To nie będzie duplikat afaict.
javadba
84

Używanie wyrażeń listowych jest dla mnie dość oczywiste. Nie jestem pewien co do wydajności, ale przynajmniej rzeczy pozostają listami.

[x for x in a if x in b]

Lub „wszystkie wartości x, które są w A, jeśli wartość X jest w B”.

Lodewijk
źródło
1
wydaje się to najbardziej pytoniczne, które utrzymuje porządek. nie jestem pewien, dlaczego nie jest to wyżej oceniane !! dzięki za świetne rozwiązanie!
Bill D
15
To jest rozwiązanie O (n ^ 2), podczas gdy powyższe rozwiązania to O (n)
nareddyt
3
@nareddyt - zrób bzestaw, a będziesz mieć O (n)
jcchuks
2
@jcchuks Zaletą tego rozwiązania jest konieczność zachowania duplikatów. Jeśli możesz być pewien wyjątkowości, lepiej byłoby zastosować zestaw O (n). Jeśli jednak duplikaty nie są możliwe, dlaczego PO mówi nawet o listach na początek? Pojęcie przecięcia listy jest matematycznym absurdem
demongolem
63

Jeśli przekształcisz większą z dwóch list w zestaw, możesz uzyskać skrzyżowanie tego zestawu z dowolnym iterowalnym przy użyciu intersection():

a = [1,2,3,4,5]
b = [1,3,5,6]
set(a).intersection(b)
Brian R. Bondy
źródło
9
Czy to coś innego niżlist(set(a) & set(b))
użytkownik1767754
3
dlaczego ma to znaczenie, która lista jest konwertowana na set (przy założeniu n! ​​= m)? jaka jest zaleta konwersji tylko jednego zestawu?
3pitt
1
Wygląda na to, że byłoby to szybsze
Nathan
29

Zrób zestaw z większego:

_auxset = set(a)

Następnie,

c = [x for x in b if x in _auxset]

zrobi to, co chcesz (zachowując bporządek, a nie a- niekoniecznie zachowa oba ) i zrobi to szybko . (Używanie if x in ajako warunku w zrozumieniu listy również działałoby i pozwalało uniknąć konieczności budowania _auxset, ale niestety w przypadku list o znacznej długości byłoby to znacznie wolniejsze).

Jeśli chcesz posortować wynik, a nie zachowywać kolejność list, jeszcze lepszym sposobem może być:

c = sorted(set(a).intersection(b))
Alex Martelli
źródło
Jest to prawie na pewno wolniejsze niż zaakceptowana odpowiedź, ale ma tę zaletę, że duplikaty nie są tracone.
tripleee
18

Oto trochę kodu Python 2 / Python 3, który generuje informacje o taktowaniu zarówno dla metod opartych na listach, jak i na zestawach, służących do znalezienia przecięcia dwóch list.

Algorytmy rozumienia czystej listy to O (n ^ 2), ponieważ inna liście jest wyszukiwanie liniowe. Algorytmy oparte na zestawie to O (n), ponieważ wyszukiwanie zestawu to O (1), a tworzenie zestawu to O (n) (a konwersja zestawu na listę to także O (n)). Tak więc dla wystarczająco dużego n algorytmy oparte na zestawie są szybsze, ale w przypadku małych n nakłady związane z tworzeniem zestawu powodują, że są one wolniejsze niż algorytmy kompresji z czystej listy.

#!/usr/bin/env python

''' Time list- vs set-based list intersection
    See http://stackoverflow.com/q/3697432/4014959
    Written by PM 2Ring 2015.10.16
'''

from __future__ import print_function, division
from timeit import Timer

setup = 'from __main__ import a, b'
cmd_lista = '[u for u in a if u in b]'
cmd_listb = '[u for u in b if u in a]'

cmd_lcsa = 'sa=set(a);[u for u in b if u in sa]'

cmd_seta = 'list(set(a).intersection(b))'
cmd_setb = 'list(set(b).intersection(a))'

reps = 3
loops = 50000

def do_timing(heading, cmd, setup):
    t = Timer(cmd, setup)
    r = t.repeat(reps, loops)
    r.sort()
    print(heading, r)
    return r[0]

m = 10
nums = list(range(6 * m))

for n in range(1, m + 1):
    a = nums[:6*n:2]
    b = nums[:6*n:3]
    print('\nn =', n, len(a), len(b))
    #print('\nn = %d\n%s %d\n%s %d' % (n, a, len(a), b, len(b)))
    la = do_timing('lista', cmd_lista, setup) 
    lb = do_timing('listb', cmd_listb, setup) 
    lc = do_timing('lcsa ', cmd_lcsa, setup)
    sa = do_timing('seta ', cmd_seta, setup)
    sb = do_timing('setb ', cmd_setb, setup)
    print(la/sa, lb/sa, lc/sa, la/sb, lb/sb, lc/sb)

wynik

n = 1 3 2
lista [0.082171916961669922, 0.082588911056518555, 0.0898590087890625]
listb [0.069530963897705078, 0.070394992828369141, 0.075379848480224609]
lcsa  [0.11858987808227539, 0.1188349723815918, 0.12825107574462891]
seta  [0.26900982856750488, 0.26902294158935547, 0.27298116683959961]
setb  [0.27218389511108398, 0.27459001541137695, 0.34307217597961426]
0.305460649521 0.258469975867 0.440838458259 0.301898526833 0.255455833892 0.435697630214

n = 2 6 4
lista [0.15915989875793457, 0.16000485420227051, 0.16551494598388672]
listb [0.13000702857971191, 0.13060092926025391, 0.13543915748596191]
lcsa  [0.18650484085083008, 0.18742108345031738, 0.19513416290283203]
seta  [0.33592700958251953, 0.34001994132995605, 0.34146714210510254]
setb  [0.29436492919921875, 0.2953648567199707, 0.30039691925048828]
0.473793098554 0.387009751735 0.555194537893 0.540689066428 0.441652573672 0.633583767462

n = 3 9 6
lista [0.27657914161682129, 0.28098297119140625, 0.28311991691589355]
listb [0.21585917472839355, 0.21679902076721191, 0.22272896766662598]
lcsa  [0.22559309005737305, 0.2271728515625, 0.2323150634765625]
seta  [0.36382699012756348, 0.36453008651733398, 0.36750602722167969]
setb  [0.34979605674743652, 0.35533690452575684, 0.36164689064025879]
0.760194128313 0.59330170819 0.62005595016 0.790686848184 0.61710008036 0.644927481902

n = 4 12 8
lista [0.39616990089416504, 0.39746403694152832, 0.41129183769226074]
listb [0.33485794067382812, 0.33914685249328613, 0.37850618362426758]
lcsa  [0.27405810356140137, 0.2745978832244873, 0.28249192237854004]
seta  [0.39211201667785645, 0.39234519004821777, 0.39317893981933594]
setb  [0.36988520622253418, 0.37011313438415527, 0.37571001052856445]
1.01034878821 0.85398540833 0.698928091731 1.07106176249 0.905302334456 0.740927452493

n = 5 15 10
lista [0.56792402267456055, 0.57422614097595215, 0.57740211486816406]
listb [0.47309303283691406, 0.47619009017944336, 0.47628307342529297]
lcsa  [0.32805585861206055, 0.32813096046447754, 0.3349759578704834]
seta  [0.40036201477050781, 0.40322518348693848, 0.40548801422119141]
setb  [0.39103078842163086, 0.39722800254821777, 0.43811702728271484]
1.41852623806 1.18166313332 0.819398061028 1.45237674242 1.20986133789 0.838951479847

n = 6 18 12
lista [0.77897095680236816, 0.78187918663024902, 0.78467702865600586]
listb [0.629547119140625, 0.63210701942443848, 0.63321495056152344]
lcsa  [0.36563992500305176, 0.36638498306274414, 0.38175487518310547]
seta  [0.46695613861083984, 0.46992206573486328, 0.47583580017089844]
setb  [0.47616910934448242, 0.47661614418029785, 0.4850609302520752]
1.66818870637 1.34819326075 0.783028414812 1.63591241329 1.32210827369 0.767878297495

n = 7 21 14
lista [0.9703209400177002, 0.9734041690826416, 1.0182771682739258]
listb [0.82394003868103027, 0.82625699043273926, 0.82796716690063477]
lcsa  [0.40975093841552734, 0.41210508346557617, 0.42286920547485352]
seta  [0.5086359977722168, 0.50968098640441895, 0.51014018058776855]
setb  [0.48688101768493652, 0.4879908561706543, 0.49204087257385254]
1.90769222837 1.61990115188 0.805587768483 1.99293236904 1.69228211566 0.841583309951

n = 8 24 16
lista [1.204819917678833, 1.2206029891967773, 1.258256196975708]
listb [1.014998197555542, 1.0206191539764404, 1.0343101024627686]
lcsa  [0.50966787338256836, 0.51018595695495605, 0.51319599151611328]
seta  [0.50310111045837402, 0.50556015968322754, 0.51335406303405762]
setb  [0.51472997665405273, 0.51948785781860352, 0.52113485336303711]
2.39478683834 2.01748351664 1.01305257092 2.34068341135 1.97190418975 0.990165516871

n = 9 27 18
lista [1.511646032333374, 1.5133969783782959, 1.5639569759368896]
listb [1.2461750507354736, 1.254518985748291, 1.2613379955291748]
lcsa  [0.5565330982208252, 0.56119203567504883, 0.56451296806335449]
seta  [0.5966339111328125, 0.60275578498840332, 0.64791703224182129]
setb  [0.54694414138793945, 0.5508568286895752, 0.55375313758850098]
2.53362406013 2.08867620074 0.932788243907 2.76380331728 2.27843203069 1.01753187594

n = 10 30 20
lista [1.7777848243713379, 2.1453688144683838, 2.4085969924926758]
listb [1.5070111751556396, 1.5202279090881348, 1.5779800415039062]
lcsa  [0.5954139232635498, 0.59703707695007324, 0.60746097564697266]
seta  [0.61563014984130859, 0.62125110626220703, 0.62354087829589844]
setb  [0.56723213195800781, 0.57257509231567383, 0.57460403442382812]
2.88774814689 2.44791645689 0.967161734066 3.13413984189 2.6567803378 1.04968299523

Wygenerowano przy użyciu jednordzeniowego komputera 2GHz z 2 GB pamięci RAM z uruchomionym Pythonem 2.6.6 w systemie Linux Debian (z Firefoxem działającym w tle).

Liczby te są jedynie orientacyjnymi wskazówkami, ponieważ na rzeczywiste prędkości różnych algorytmów wpływa w różny sposób proporcja elementów znajdujących się na obu listach źródeł.

PM 2 Ring
źródło
11
a = [1,2,3,4,5]
b = [1,3,5,6]
c = list(set(a).intersection(set(b)))

Powinien działać jak sen. I jeśli możesz, używaj zestawów zamiast list, aby uniknąć zmiany tego typu!

Alex Hart
źródło
Jeśli i b są duże to jest szybsze niż innych odpowiedzi
javadba
5

Funkcjonalny sposób można osiągnąć za pomocą filteri lambdaoperatora.

list1 = [1,2,3,4,5,6]

list2 = [2,4,6,9,10]

>>> list(filter(lambda x:x in list1, list2))

[2, 4, 6]

Edycja: Filtruje x, który istnieje zarówno na list1, jak i na liście, ustawioną różnicę można również osiągnąć za pomocą:

>>> list(filter(lambda x:x not in list1, list2))
[9,10]

Edycja2: python3 filterzwraca obiekt filtru, hermetyzując go, listzwraca listę wyników.

Saftofobia
źródło
Proszę użyć linku edycyjnego, aby wyjaśnić, jak działa ten kod, a nie tylko podać kod, ponieważ wyjaśnienie może pomóc przyszłym czytelnikom. Zobacz także Jak odpowiedzieć . źródło
Jed Fox
1
W przypadku Python3 zwraca obiekt filtru. Musisz powiedzieć, list(filter(lambda x:x in list1, list2))aby uzyskać go jako listę.
Adrian W
1

Jest to przykład, kiedy potrzebujesz Każdy element w wyniku powinien pojawić się tyle razy, ile pokazuje w obu tablicach.

def intersection(nums1, nums2):
    #example:
    #nums1 = [1,2,2,1]
    #nums2 = [2,2]
    #output = [2,2]
    #find first 2 and remove from target, continue iterating

    target, iterate = [nums1, nums2] if len(nums2) >= len(nums1) else [nums2, nums1] #iterate will look into target

    if len(target) == 0:
            return []

    i = 0
    store = []
    while i < len(iterate):

         element = iterate[i]

         if element in target:
               store.append(element)
               target.remove(element)

         i += 1


    return store
Arturo Morales Rangel
źródło
1

Może być późno, ale pomyślałem, że powinienem podzielić się tym przypadkiem, w którym musisz to zrobić ręcznie (pokaż działanie - haha) LUB gdy potrzebujesz, aby wszystkie elementy pojawiały się tyle razy, ile to możliwe, lub gdy potrzebujesz, aby były unikalne .

Uprzejmie informujemy, że zostały również napisane testy.



    from nose.tools import assert_equal

    '''
    Given two lists, print out the list of overlapping elements
    '''

    def overlap(l_a, l_b):
        '''
        compare the two lists l_a and l_b and return the overlapping
        elements (intersecting) between the two
        '''

        #edge case is when they are the same lists
        if l_a == l_b:
            return [] #no overlapping elements

        output = []

        if len(l_a) == len(l_b):
            for i in range(l_a): #same length so either one applies
                if l_a[i] in l_b:
                    output.append(l_a[i])

            #found all by now
            #return output #if repetition does not matter
            return list(set(output))

        else:
            #find the smallest and largest lists and go with that
            sm = l_a if len(l_a)  len(l_b) else l_b

            for i in range(len(sm)):
                if sm[i] in lg:
                    output.append(sm[i])

            #return output #if repetition does not matter
            return list(set(output))

    ## Test the Above Implementation

    a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
    exp = [1, 2, 3, 5, 8, 13]

    c = [4, 4, 5, 6]
    d = [5, 7, 4, 8 ,6 ] #assuming it is not ordered
    exp2 = [4, 5, 6]

    class TestOverlap(object):

        def test(self, sol):
            t = sol(a, b)
            assert_equal(t, exp)
            print('Comparing the two lists produces')
            print(t)

            t = sol(c, d)
            assert_equal(t, exp2)
            print('Comparing the two lists produces')
            print(t)

            print('All Tests Passed!!')

    t = TestOverlap()
    t.test(overlap)
anabeto93
źródło
0

Jeśli przez Boolean AND masz na myśli elementy, które pojawiają się na obu listach, np. Skrzyżowanie, powinieneś spojrzeć na Pythona seti frozensettypy.

Tim McNamara
źródło
0

Możesz także użyć licznika! Nie zachowuje kolejności, ale weźmie pod uwagę duplikaty:

>>> from collections import Counter
>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> d1, d2 = Counter(a), Counter(b)
>>> c = [n for n in d1.keys() & d2.keys() for _ in range(min(d1[n], d2[n]))]
>>> print(c)
[1,3,5]
Atonalny
źródło