Cukup banyak saya perlu menulis sebuah program untuk memeriksa apakah daftar memiliki duplikat dan jika itu menghapusnya dan mengembalikan daftar baru dengan barang-barang yang tidak digandakan / dihapus. Inilah yang saya miliki tetapi jujur saya tidak tahu harus berbuat apa.
def remove_duplicates():
t = ['a', 'b', 'c', 'd']
t2 = ['a', 'c', 'd']
for t in t2:
t.append(t.remove())
return t
python
algorithm
list
duplicates
intersection
Neemaximo
sumber
sumber
Jawaban:
Pendekatan umum untuk mendapatkan koleksi barang yang unik adalah menggunakan a
set
. Set unordered koleksi yang berbeda objek. Untuk membuat satu set dari setiap iterable, Anda bisa meneruskannya keset()
fungsi bawaan. Jika nanti Anda membutuhkan daftar nyata lagi, Anda dapat meneruskan set kelist()
fungsi yang sama.Contoh berikut harus mencakup apa pun yang Anda coba lakukan:
Seperti yang Anda lihat dari hasil contoh, urutan asli tidak dipertahankan . Seperti disebutkan di atas, set sendiri adalah koleksi yang tidak terurut, sehingga urutannya hilang. Saat mengonversi satu set kembali ke daftar, perintah sewenang-wenang dibuat.
Mempertahankan ketertiban
Jika pesanan penting bagi Anda, maka Anda harus menggunakan mekanisme yang berbeda. Solusi yang sangat umum untuk ini adalah dengan mengandalkan
OrderedDict
untuk menjaga urutan kunci selama penyisipan:Dimulai dengan Python 3.7 , kamus internal dijamin untuk menjaga urutan penyisipan juga, jadi Anda juga dapat menggunakannya secara langsung jika Anda menggunakan Python 3.7 atau lebih baru (atau CPython 3.6):
Perhatikan bahwa ini mungkin memiliki overhead menciptakan kamus pertama, dan kemudian membuat daftar darinya. Jika Anda tidak benar-benar perlu mempertahankan pesanan, Anda sering lebih baik menggunakan satu set, terutama karena itu memberi Anda lebih banyak operasi untuk dikerjakan. Lihat pertanyaan ini untuk detail lebih lanjut dan cara-cara alternatif untuk mempertahankan pesanan saat menghapus duplikat.
Akhirnya catatan bahwa baik
set
sertaOrderedDict
/dict
solusi memerlukan item Anda untuk menjadi hashable . Ini biasanya berarti bahwa mereka harus abadi. Jika Anda harus berurusan dengan item yang tidak hashable (misalnya objek daftar), maka Anda harus menggunakan pendekatan lambat di mana Anda pada dasarnya harus membandingkan setiap item dengan setiap item lainnya dalam loop bersarang.sumber
Dalam Python 2.7 , cara baru untuk menghapus duplikat dari iterable sambil menjaganya dalam urutan asli adalah:
Dalam Python 3.5 , OrderedDict memiliki implementasi C. Pengaturan waktu saya menunjukkan bahwa ini sekarang adalah yang tercepat dan terpendek dari berbagai pendekatan untuk Python 3.5.
Dalam Python 3.6 , perintah reguler menjadi teratur dan kompak. (Fitur ini berlaku untuk CPython dan PyPy tetapi mungkin tidak ada dalam implementasi lain). Itu memberi kami cara deduksi tercepat baru sambil mempertahankan pesanan:
Dalam Python 3.7 , dikt reguler dijamin untuk keduanya dipesan di semua implementasi. Jadi, solusi terpendek dan tercepat adalah:
sumber
TypeError: unhashable type: 'dictlist'
Ini satu-baris:
list(set(source_list))
akan melakukan trik.A
set
adalah sesuatu yang tidak mungkin memiliki duplikat.Pembaruan: pendekatan pelestarian pesanan adalah dua baris:
Di sini kita menggunakan fakta yang
OrderedDict
mengingat urutan penyisipan kunci, dan tidak mengubahnya ketika nilai pada kunci tertentu diperbarui. Kami menyisipkanTrue
sebagai nilai, tetapi kami dapat menyisipkan apa pun, nilai tidak digunakan. (set
bekerja sangat miripdict
dengan nilai yang diabaikan juga.)sumber
source_list
hashable.sumber
frozenset
berfungsi dengan konten yang tidak dapat diacak. Saya masih mendapatkan kesalahan tidak hash saat menggunakanfrozenset
.Jika Anda tidak peduli dengan pesanannya, lakukan saja ini:
A
set
dijamin tidak memiliki duplikat.sumber
l
hashable.Untuk membuat daftar baru mempertahankan urutan elemen pertama duplikat di
L
newlist=[ii for n,ii in enumerate(L) if ii not in L[:n]]
misalnya
if L=[1, 2, 2, 3, 4, 2, 4, 3, 5]
makanewlist
akan[1,2,3,4,5]
Ini memeriksa setiap elemen baru belum muncul sebelumnya dalam daftar sebelum menambahkannya. Juga tidak perlu impor.
sumber
set
danOrderedDict
mungkin memiliki kompleksitas waktu diamortisasi yang lebih rendah.Seorang kolega telah mengirim jawaban yang diterima sebagai bagian dari kodenya kepada saya untuk codereview hari ini. Meskipun saya pasti mengagumi keanggunan jawaban yang dipermasalahkan, saya tidak senang dengan penampilannya. Saya telah mencoba solusi ini (saya menggunakan set untuk mengurangi waktu pencarian)
Untuk membandingkan efisiensi, saya menggunakan sampel acak 100 bilangan bulat - 62 unik
Berikut adalah hasil pengukurannya
Nah, apa yang terjadi jika set dihapus dari solusi?
Hasilnya tidak seburuk dengan OrderedDict , tetapi masih lebih dari 3 kali dari solusi asli
sumber
def unique(iterable):
:;seen = set()
;seen_add = seen.add
;return [item for item in iterable if not item in seen and not seen_add(item)]
Ada juga solusi menggunakan Pandas dan Numpy. Keduanya mengembalikan array numpy sehingga Anda harus menggunakan fungsi
.tolist()
jika Anda ingin daftar.Solusi panda
Menggunakan fungsi Pandas
unique()
:Solusi numpy
Menggunakan fungsi numpy
unique()
.Perhatikan bahwa numpy.unique () juga mengurutkan nilai . Jadi daftar
t2
dikembalikan disortir. Jika Anda ingin agar pesanan tetap digunakan seperti dalam jawaban ini :Solusinya tidak begitu elegan dibandingkan dengan yang lain, namun, dibandingkan dengan panda.unique (), numpy.unique () memungkinkan Anda juga untuk memeriksa apakah array bersarang unik di sepanjang satu sumbu yang dipilih.
sumber
Cara lain untuk melakukan:
sumber
keys()
mengembalikan objek tampilan kamus, bukan daftar.Sederhana dan mudah:
Keluaran:
sumber
in
adalah operasi O (n) dan Andacleanlist
akan memiliki paling banyakn
angka => kasus terburuk ~ O (n ^ 2)Dalam jawaban ini, akan ada dua bagian: Dua solusi unik, dan grafik kecepatan untuk solusi spesifik.
Menghapus Item Duplikat
Sebagian besar jawaban ini hanya menghapus item duplikat yang dapat hashable , tetapi pertanyaan ini tidak menyiratkan itu tidak hanya membutuhkan item hashable , artinya saya akan menawarkan beberapa solusi yang tidak memerlukan item hashable .
collections.Counter adalah alat yang ampuh di perpustakaan standar yang bisa menjadi sempurna untuk ini. Hanya ada satu solusi lain yang bahkan memiliki Counter di dalamnya. Namun, solusi itu juga terbatas pada kunci hashable .
Untuk memperbolehkan kunci yang tidak dapat pecah di Counter, saya membuat kelas Container, yang akan mencoba untuk mendapatkan fungsi hash default objek, tetapi jika gagal, ia akan mencoba fungsi identitasnya. Ini juga mendefinisikan metode eq dan hash . Ini harus cukup untuk memungkinkan barang yang tidak dapat dihancurkan dalam solusi kami. Objek yang tidak bisa pecah akan diperlakukan seolah-olah objek tersebut dapat hashable. Namun, fungsi hash ini menggunakan identitas untuk objek-objek yang tidak bisa didapati, yang berarti dua objek yang sama-sama tidak bisa dilepas tidak akan berfungsi. Saya sarankan Anda menimpa ini, dan mengubahnya untuk menggunakan hash dari jenis yang bisa berubah-ubah (seperti menggunakan
hash(tuple(my_list))
jikamy_list
adalah daftar).Saya juga membuat dua solusi. Solusi lain yang menjaga urutan barang, menggunakan subclass dari OrderedDict dan Counter yang dinamai 'OrderedCounter'. Sekarang, inilah fungsinya:
remd adalah penyortiran yang tidak dipesan, oremd adalah penyortiran yang dipesan. Anda dapat dengan jelas mengetahui mana yang lebih cepat, tetapi saya akan menjelaskannya. Penyortiran yang tidak teratur sedikit lebih cepat. Itu menyimpan lebih sedikit data, karena tidak perlu dipesan.
Sekarang, saya juga ingin menunjukkan perbandingan kecepatan dari setiap jawaban. Jadi, saya akan melakukannya sekarang.
Fungsi mana yang tercepat?
Untuk menghapus duplikat, saya mengumpulkan 10 fungsi dari beberapa jawaban. Saya menghitung kecepatan setiap fungsi dan memasukkannya ke dalam grafik menggunakan matplotlib.pyplot .
Saya membagi ini menjadi tiga putaran grafik. Sebuah hashable adalah objek apa pun yang dapat hash, sebuah hashable adalah objek yang tidak dapat hash. Urutan berurutan adalah urutan yang mempertahankan pesanan, urutan yang tidak berurutan tidak mempertahankan pesanan. Sekarang, inilah beberapa istilah lagi:
Unordered Hashable adalah untuk metode apa pun yang menghapus duplikat, yang tidak selalu harus menjaga ketertiban. Itu tidak harus bekerja untuk orang yang tidak terluka, tetapi itu bisa.
Memesan Hashable adalah untuk metode apa pun yang menjaga urutan item dalam daftar, tetapi itu tidak harus bekerja untuk yang tak tergoyahkan, tetapi bisa.
Ordered Unhashable adalah metode apa pun yang menjaga urutan item dalam daftar, dan bekerja untuk unhashables.
Pada sumbu y adalah jumlah detik yang dibutuhkan.
Pada sumbu x adalah angka fungsi diterapkan.
Kami membuat urutan untuk hashable yang tidak berurutan dan memesan hashable dengan pemahaman sebagai berikut:
[list(range(x)) + list(range(x)) for x in range(0, 1000, 10)]
Untuk pesanan yang belum dipesan:
[[list(range(y)) + list(range(y)) for y in range(x)] for x in range(0, 1000, 10)]
Perhatikan ada 'langkah' dalam rentang karena tanpa itu, ini akan memakan waktu 10x lebih lama. Juga karena menurut pendapat pribadi saya, saya pikir itu mungkin terlihat sedikit lebih mudah dibaca.
Juga perhatikan kunci pada legenda adalah apa yang saya coba tebak sebagai bagian terpenting dari fungsi. Adapun fungsi apa yang paling buruk atau terbaik? Grafik berbicara sendiri.
Dengan itu diselesaikan, di sini adalah grafik.
Hashables yang Tidak Diatur
(Diperbesar)
Hashables Dipesan
(Diperbesar)
Tidak Terperintahkan Dipesan
(Diperbesar)
sumber
Saya punya dict dalam daftar saya, jadi saya tidak bisa menggunakan pendekatan di atas. Saya mendapat kesalahan:
Jadi, jika Anda peduli dengan pesanan dan / atau beberapa item tidak dapat rusak . Maka Anda mungkin menemukan ini berguna:
Beberapa orang mungkin mempertimbangkan pemahaman daftar dengan efek samping untuk tidak menjadi solusi yang baik. Inilah alternatifnya:
sumber
map
dengan efek samping bahkan lebih menyesatkan daripada listcomp dengan efek samping. Juga,lambda x: unique_list.append(x)
ini hanya cara yang lebih rumit dan lebih lambat untuk dilewatiunique_list.append
.Semua pendekatan pelestarian pesanan yang saya lihat di sini sejauh ini baik menggunakan perbandingan naif (dengan O (n ^ 2) kompleksitas waktu terbaik) atau kombinasi berat
OrderedDicts
/set
+list
yang terbatas pada input hashable. Berikut ini adalah solusi O (nlogn) bebas hash:Pembaruan menambahkan
key
argumen, dokumentasi dan kompatibilitas Python 3.sumber
tuple()
daftar dan hash mereka. | | | | - Secara umum, proses hash membutuhkan waktu yang proporsional dengan ukuran seluruh data, sementara solusi ini membutuhkan waktu O (nlog (n)), tergantung hanya pada panjang daftar.reduce()
sudah bekerja pada koleksi diurutkansrt_enum
, mengapa Anda menerapkansorted
lagi?Jika Anda ingin mempertahankan pesanan, dan tidak menggunakan modul eksternal apa pun di sini adalah cara mudah untuk melakukan ini:
Catatan: Metode ini mempertahankan urutan penampilan, jadi, seperti yang terlihat di atas, sembilan akan muncul setelah satu karena itu adalah pertama kalinya itu muncul. Namun, ini adalah hasil yang sama seperti yang Anda dapatkan dengan melakukan
tetapi jauh lebih pendek, dan berjalan lebih cepat.
Ini berfungsi karena setiap kali
fromkeys
fungsi mencoba membuat kunci baru, jika nilainya sudah ada, ia hanya akan menimpanya. Namun ini tidak akan mempengaruhi kamus sama sekali, sepertifromkeys
membuat kamus di mana semua kunci memiliki nilaiNone
, sehingga secara efektif menghilangkan semua duplikat dengan cara ini.sumber
Anda juga bisa melakukan ini:
Alasan di atas berfungsi adalah bahwa
index
metode mengembalikan hanya indeks pertama dari suatu elemen. Elemen duplikat memiliki indeks lebih tinggi. Lihat di sini :sumber
list.index
adalah operasi linear-waktu, membuat solusi Anda kuadratik.Coba gunakan set:
sumber
Kurangi varian dengan penyimpanan pesanan:
Anggaplah kita memiliki daftar:
Kurangi varian (tidak efisien):
5 x lebih cepat tetapi lebih canggih
Penjelasan:
sumber
Pendekatan terbaik untuk menghapus duplikat dari daftar menggunakan fungsi set () , tersedia dalam python, sekali lagi mengubah set itu ke dalam daftar
sumber
Anda dapat menggunakan fungsi berikut:
Contoh :
Pemakaian:
['this', 'is', 'a', 'list', 'with', 'dupicates', 'in', 'the']
sumber
Ada banyak jawaban lain yang menyarankan berbagai cara untuk melakukan ini, tetapi semuanya adalah operasi batch, dan beberapa dari mereka membuang urutan aslinya. Itu mungkin baik-baik saja tergantung pada apa yang Anda butuhkan, tetapi jika Anda ingin beralih pada nilai-nilai dalam urutan contoh pertama dari setiap nilai, dan Anda ingin menghapus duplikat on-the-fly versus sekaligus, Anda bisa menggunakan generator ini:
Ini mengembalikan generator / iterator, sehingga Anda dapat menggunakannya di mana saja Anda dapat menggunakan iterator.
Keluaran:
Jika Anda menginginkannya
list
, Anda dapat melakukan ini:Keluaran:
sumber
seen = set(iterable); for item in seen: yield item
hampir pasti lebih cepat. (Saya belum mencoba kasus khusus ini, tetapi itu akan menjadi dugaan saya.)Tanpa menggunakan set
sumber
Anda dapat menggunakan
set
untuk menghapus duplikat:Tetapi perhatikan hasilnya akan tidak tertata. Jika itu masalah:
sumber
Satu lagi pendekatan yang lebih baik,
dan pesanan tetap dipertahankan.
sumber
Yang ini peduli dengan pesanan tanpa terlalu banyak kesulitan (OrderdDict & lainnya). Mungkin bukan cara yang paling Pythonic, atau cara terpendek, tetapi melakukan trik:
sumber
list
); 2. Metode Anda berskala sangat buruk: kuadratik dalam jumlah elemen dilist
.kode di bawah ini mudah untuk menghapus duplikat dalam daftar
mengembalikan [1,2,3,4]
sumber
list(set(..))
(lebih dari 1 juta pass) akan mengalahkan solusi ini sekitar 10 detik penuh - sedangkan pendekatan ini membutuhkan waktu sekitar 12 detik,list(set(..))
hanya membutuhkan waktu sekitar 2 detik!Inilah solusi pythonic tercepat yang dikirimkan ke orang lain yang tercantum dalam balasan.
Menggunakan detail implementasi evaluasi hubung singkat memungkinkan untuk menggunakan pemahaman daftar, yang cukup cepat.
visited.add(item)
selalu kembaliNone
sebagai hasilnya, yang dievaluasi sebagaiFalse
, jadi sisi kananor
akan selalu menjadi hasil dari ungkapan seperti itu.Waktunya sendiri
sumber
Menggunakan set :
Menggunakan unik :
sumber
Sayangnya. Sebagian besar jawaban di sini tidak mempertahankan pesanan atau terlalu lama. Berikut ini adalah jawaban sederhana, untuk menjaga agar.
Ini akan memberi Anda x dengan duplikat yang dihapus tetapi tetap mempertahankan pesanan.
sumber
Cara yang sangat sederhana dalam Python 3:
sumber
sorted(list(...))
redundan (sorted
sudah secara implisit mengonversi argumennya menjadi yang barulist
, mengurutkannya, lalu mengembalikan yang barulist
, jadi menggunakan keduanya berarti membuat sementara yang tidak perlulist
). Gunakan hanyalist
jika hasilnya tidak perlu disortir, gunakan hanyasorted
jika hasilnya perlu disortir.Keajaiban jenis Python Built-in
Dalam python, sangat mudah untuk memproses kasus rumit seperti ini dan hanya dengan tipe bawaan python.
Mari saya tunjukkan caranya!
Metode 1: Kasus Umum
Caranya ( 1 kode baris ) untuk menghapus elemen yang digandakan dalam daftar dan tetap menjaga urutan penyortiran
Anda akan mendapatkan hasilnya
Metode 2: Kasus Khusus
Kasing khusus untuk memproses yang tidak dapat pecah ( 3 kode baris )
Anda akan mendapatkan hasilnya:
Karena tuple hashable dan Anda dapat mengkonversi data antara daftar dan tuple dengan mudah
sumber