Bagaimana cara menemukan persimpangan daftar?

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

output aktual: [1,3,5,6] output yang diharapkan:[1,3,5]

Bagaimana kita bisa mencapai operasi boolean DAN (persimpangan daftar) pada dua daftar?

csguy11
sumber
6
Masalahnya di sini adalah yang a and bberfungsi seperti pernyataan berikut dari dokumentasi menyebutkannya: " Ekspresi x and ypertama mengevaluasi x; jika xsalah, nilainya dikembalikan; jika tidak, ydievaluasi dan nilai yang dihasilkan dikembalikan. "
Tadeck

Jawaban:

348

Jika pesanan tidak penting dan Anda tidak perlu khawatir tentang duplikat maka Anda dapat menggunakan set persimpangan:

>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> list(set(a) & set(b))
[1, 3, 5]
Mark Byers
sumber
9
bagaimana jika a = [1,1,2,3,4,5]dan b = [1,1,3,5,6]kemudian persimpangan [1,1,3,5]tetapi dengan metode di atas itu akan menghasilkan hanya satu 1yaitu [1, 3, 5]apa yang akan menjadi cara menulis untuk melakukannya?
Nitish Kumar Pal
6
@NItishKumarPal intersectionbiasanya dipahami sebagai berbasis set . Anda mencari hewan yang sedikit berbeda - dan Anda mungkin perlu melakukannya secara manual dengan mengurutkan setiap daftar dan menggabungkan hasilnya - dan menyimpan dups dalam penggabungan.
javadba
1
@MarkByers Ini tidak akan memiliki duplikat afaict.
javadba
85

Menggunakan daftar pemahaman adalah hal yang sangat jelas bagi saya. Tidak yakin tentang kinerja, tetapi setidaknya hal-hal tetap daftar.

[x for x in a if x in b]

Atau "semua nilai x yang ada di A, jika nilai X ada di B".

Lodewijk
sumber
1
ini tampaknya yang paling pythonic yang menjaga ketertiban. tidak yakin mengapa ini tidak lebih tinggi !! Terima kasih atas solusi hebatnya!
Bill D
15
Ini adalah solusi O (n ^ 2), sedangkan solusi di atas adalah O (n)
nareddyt
3
@nareddyt - buat bsatu set dan Anda akan memiliki O (n)
jcchuks
2
@ jcchuks Keuntungan dari solusi ini adalah jika Anda perlu mempertahankan duplikat. Jika Anda bisa yakin akan keunikannya, maka solusi yang ditetapkan O (n) akan lebih baik. Namun, jika duplikat tidak memungkinkan, mengapa OP bahkan berbicara tentang daftar? Gagasan persimpangan daftar adalah absurditas matematis
demongolem
63

Jika Anda mengonversi yang lebih besar dari dua daftar menjadi satu set, Anda bisa mendapatkan persimpangan set itu dengan iterable menggunakan intersection():

a = [1,2,3,4,5]
b = [1,3,5,6]
set(a).intersection(b)
Brian R. Bondy
sumber
9
Apakah ini berbeda dari list(set(a) & set(b))
user1767754
3
mengapa penting daftar mana yang akan dikonversi ke set (dengan asumsi n! = m)? apa keuntungan dari hanya mengkonversi satu ke set?
3pitt
1
Sepertinya ini akan lebih cepat
Nathan
29

Buat satu set yang lebih besar:

_auxset = set(a)

Kemudian,

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

akan melakukan apa yang Anda inginkan (melestarikan b pemesanan, bukan a- tidak dapat selalu mempertahankan keduanya ) dan melakukannya dengan cepat . (Menggunakan if x in asebagai kondisi dalam pemahaman daftar juga akan bekerja, dan menghindari kebutuhan untuk membangun _auxset, tetapi sayangnya untuk daftar panjang substansial akan jauh lebih lambat).

Jika Anda ingin hasilnya diurutkan, alih-alih mempertahankan urutan daftar, cara yang lebih rapi mungkin:

c = sorted(set(a).intersection(b))
Alex Martelli
sumber
Ini hampir pasti lebih lambat dari jawaban yang diterima tetapi memiliki keuntungan bahwa duplikat tidak hilang.
tripleee
18

Berikut adalah beberapa kode Python 2 / Python 3 yang menghasilkan informasi waktu untuk metode berbasis daftar dan set untuk menemukan persimpangan dua daftar.

Algoritma pemahaman daftar murni adalah O (n ^ 2), karena inpada daftar adalah pencarian linier. Algoritme berbasis set adalah O (n), karena pencarian pencarian adalah O (1), dan pembuatan kreasi adalah O (n) (dan mengonversi satu set ke daftar juga O (n)). Jadi untuk n yang cukup besar , algoritma set-based lebih cepat, tetapi untuk n kecil overhead pembuatan set membuatnya lebih lambat daripada algoritma comp murni daftar.

#!/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)

keluaran

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

Dihasilkan menggunakan mesin inti tunggal 2GHz dengan RAM 2GB yang menjalankan Python 2.6.6 pada Debian rasa Linux (dengan Firefox berjalan di latar belakang).

Angka-angka ini hanya panduan kasar, karena kecepatan aktual dari berbagai algoritma dipengaruhi secara berbeda oleh proporsi elemen yang ada di kedua daftar sumber.

PM 2Ring
sumber
11
a = [1,2,3,4,5]
b = [1,3,5,6]
c = list(set(a).intersection(set(b)))

Seharusnya bekerja seperti mimpi. Dan, jika Anda bisa, gunakan set bukannya daftar untuk menghindari semua jenis ini berubah!

Alex Hart
sumber
Jika a dan b besar maka ini lebih cepat dari jawaban lain
javadba
5

Cara fungsional dapat dicapai dengan menggunakan filterdan lambdaoperator.

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

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

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

[2, 4, 6]

Sunting: Memfilter x yang ada di list1 dan list, mengatur perbedaan juga dapat dicapai dengan menggunakan:

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

Edit2: python3 filtermengembalikan objek filter, mengenkapsulasi dengan listmengembalikan daftar output.

Saftophobia
sumber
Harap gunakan tautan edit untuk menjelaskan cara kerja kode ini dan jangan hanya memberikan kode, karena penjelasan lebih mungkin membantu pembaca di masa mendatang. Lihat juga Cara Menjawab . sumber
Jed Fox
1
Dengan Python3, ini mengembalikan objek filter. Anda perlu mengatakan list(filter(lambda x:x in list1, list2))untuk mendapatkannya sebagai daftar.
Adrian W
1

Ini adalah contoh ketika Anda membutuhkan Setiap elemen dalam hasil akan muncul sebanyak yang ditampilkan di kedua array.

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
sumber
1

Mungkin terlambat tapi saya hanya berpikir saya harus berbagi untuk kasus di mana Anda diminta untuk melakukannya secara manual (tunjukkan kerja - haha) ATAU ketika Anda membutuhkan semua elemen untuk muncul sebanyak mungkin atau ketika Anda juga membutuhkannya untuk menjadi unik .

Harap perhatikan bahwa tes juga telah ditulis untuk itu.



    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
sumber
0

Jika, menurut Boolean AND, maksud Anda adalah item yang muncul di kedua daftar, misalnya persimpangan, maka Anda harus melihat pada Python setdan frozensettipe.

Tim McNamara
sumber
0

Anda juga dapat menggunakan penghitung! Itu tidak mempertahankan pesanan, tetapi akan mempertimbangkan duplikat:

>>> 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]
Tanpa nada
sumber