Uji apakah daftar membagikan item apa pun dengan python

Saya ingin memeriksa apakah ada item dalam satu daftar ada di daftar lain. Saya dapat melakukannya hanya dengan kode di bawah ini, tetapi saya menduga mungkin ada fungsi perpustakaan untuk melakukan ini. Jika tidak, apakah ada metode yang lebih pythonic untuk mencapai hasil yang sama.

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

Jawaban singkat : gunakan not set(a).isdisjoint(b), umumnya yang tercepat.

Ada empat cara umum untuk menguji apakah dua daftar adan bberbagi item apa pun. Opsi pertama adalah mengonversi keduanya menjadi set dan memeriksa persimpangannya, seperti:

bool(set(a) & set(b))

Karena set disimpan menggunakan tabel hash di Python, pencarian mereka adalahO(1) (lihat di sini untuk informasi lebih lanjut tentang kompleksitas operator di Python). Secara teoritis, ini O(n+m)rata-rata untuk ndan mobjek dalam daftar adan b. Tapi 1) pertama-tama ia harus membuat set dari daftar, yang dapat mengambil jumlah waktu yang tidak dapat diabaikan, dan 2) itu mengandaikan bahwa tabrakan hashing jarang di antara data Anda.

Cara kedua untuk melakukannya adalah menggunakan ekspresi generator yang melakukan iterasi pada daftar, seperti:

any(i in a for i in b)

Ini memungkinkan untuk mencari di tempat, sehingga tidak ada memori baru yang dialokasikan untuk variabel perantara. Itu juga menyelamatkan pada penemuan pertama. Tetapi inoperator selalu ada O(n)dalam daftar (lihat di sini ).

Opsi lain yang diusulkan adalah hibrida untuk beralih melalui salah satu daftar, mengonversi yang lain dalam satu set dan menguji keanggotaan pada set ini, seperti:

a = set(a); any(i in a for i in b)

Pendekatan keempat adalah mengambil keuntungan dari isdisjoint()metode set (beku) (lihat di sini ), misalnya:

not set(a).isdisjoint(b)

Jika elemen yang Anda cari berada di dekat awal array (misalnya diurutkan), ekspresi generator lebih disukai, karena metode persimpangan set harus mengalokasikan memori baru untuk variabel perantara:

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

Berikut adalah grafik waktu eksekusi untuk contoh ini dalam fungsi ukuran daftar:

Perhatikan bahwa kedua sumbu bersifat logaritmik. Ini mewakili kasus terbaik untuk ekspresi generator. Seperti dapat dilihat, isdisjoint()metode ini lebih baik untuk ukuran daftar yang sangat kecil, sedangkan ekspresi generator lebih baik untuk ukuran daftar yang lebih besar.

Di sisi lain, saat pencarian dimulai dengan awal untuk ekspresi hybrid dan generator, jika elemen bersama secara sistematis di akhir array (atau kedua daftar tidak berbagi nilai apa pun), maka pendekatan persimpangan disjoint dan set kemudian jauh lebih cepat daripada ekspresi generator dan pendekatan hybrid.

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

Sangat menarik untuk dicatat bahwa ekspresi generator jauh lebih lambat untuk ukuran daftar yang lebih besar. Ini hanya untuk 1000 repetisi, bukan 100000 untuk gambar sebelumnya. Pengaturan ini juga mendekati dengan baik ketika ketika tidak ada elemen yang dibagikan, dan merupakan kasus terbaik untuk pemisahan dan mengatur pendekatan persimpangan.

Berikut adalah dua analisis menggunakan angka acak (alih-alih mencurangi pengaturan untuk mendukung satu teknik atau lainnya):

Peluang berbagi yang tinggi: elemen diambil secara acak [1, 2*len(a)] . Peluang berbagi yang rendah: elemen diambil secara acak [1, 1000*len(a)].

Hingga kini, analisis ini seharusnya kedua daftar memiliki ukuran yang sama. Dalam hal dua daftar ukuran yang berbeda, misalnya ajauh lebih kecil, isdisjoint()selalu lebih cepat:

Pastikan adaftar tersebut lebih kecil, jika tidak kinerjanya menurun. Dalam percobaan ini, aukuran daftar ditetapkan menjadi5 .

Singkatnya:

• Jika daftar sangat kecil (<10 elemen), not set(a).isdisjoint(b)selalu yang tercepat.
• Jika elemen dalam daftar diurutkan atau memiliki struktur reguler yang dapat Anda manfaatkan, ekspresi generator any(i in a for i in b)adalah yang tercepat pada ukuran daftar besar;
• Tes persimpangan dengan set not set(a).isdisjoint(b), yang selalu lebih cepat dari bool(set(a) & set(b)).
• Hibrid "iterate through list, test on set" a = set(a); any(i in a for i in b)umumnya lebih lambat daripada metode lain.
• Ekspresi generator dan hibrida jauh lebih lambat daripada dua pendekatan lain ketika datang ke daftar tanpa berbagi elemen.

Dalam kebanyakan kasus, menggunakan isdisjoint()metode adalah pendekatan terbaik karena ekspresi generator akan membutuhkan waktu lebih lama untuk dieksekusi, karena sangat tidak efisien ketika tidak ada elemen yang dibagikan.

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

Catatan: di atas mengasumsikan bahwa Anda menginginkan boolean sebagai jawabannya. Jika yang Anda butuhkan adalah ekspresi untuk digunakan dalam ifpernyataan, cukup gunakanif set(a) & set(b):

def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

Ini asimptotik optimal (kasus terburuk O (n + m)), dan mungkin lebih baik daripada pendekatan persimpangan karena anyhubungan arus pendek.

Misalnya:

lists_overlap([3,4,5], [1,2,3])

akan mengembalikan True segera setelah tiba 3 in sb

EDIT: Variasi lain (dengan terima kasih kepada Dave Kirby):

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

Ini bergantung pada imapiterator, yang diimplementasikan dalam C, daripada pemahaman generator. Ini juga digunakan sb.__contains__sebagai fungsi pemetaan. Saya tidak tahu seberapa besar perbedaan kinerja ini. Itu masih akan mengalami arus pendek.

Anda juga bisa menggunakan anydengan pemahaman daftar:

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

Dengan python 2.6 atau yang lebih baru, Anda dapat melakukan:

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

Anda dapat menggunakan ekspresi generator fungsi / fungsi bawaan apa saja:

def list_overlap(a,b): 
     return any(i for i in a if i in b)

Seperti yang ditunjukkan oleh John dan Lie, ini memberikan hasil yang salah ketika untuk setiap saya dibagikan oleh dua daftar, bool (i) == Salah. Harus:

return any(i in b for i in a)

Pertanyaan ini cukup lama, tetapi saya perhatikan bahwa sementara orang-orang berdebat set vs daftar, bahwa tidak ada yang berpikir untuk menggunakannya bersama-sama. Mengikuti contoh Soravux,

Kasus terburuk untuk daftar:

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

Dan kasus terbaik untuk daftar:

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

Jadi, bahkan lebih cepat daripada iterasi melalui dua daftar adalah iterasi daftar untuk melihat apakah itu dalam set, yang masuk akal karena memeriksa apakah nomor dalam set membutuhkan waktu yang konstan sementara memeriksa dengan iterasi melalui daftar membutuhkan waktu sebanding dengan panjang Daftar.

Jadi, kesimpulan saya adalah bahwa iterate melalui daftar, dan periksa apakah sudah di set .

jika Anda tidak peduli apa elemen yang tumpang tindih mungkin, Anda cukup memeriksa lendaftar gabungan vs daftar digabungkan sebagai satu set. Jika ada elemen yang tumpang tindih, set akan lebih pendek:

len(set(a+b+c))==len(a+b+c) mengembalikan True, jika tidak ada tumpang tindih.

Saya akan melempar yang lain dengan gaya pemrograman fungsional:

any(map(lambda x: x in a, b))

Penjelasan:

map(lambda x: x in a, b)

mengembalikan daftar boolean di mana elemen bditemukan di a. Daftar itu kemudian diteruskan ke any, yang hanya mengembalikan Truejika ada elemen True.