Petua menggunakan koleksi

1. Senarai koleksi

Seperti yang anda ingat, Java mempunyai koleksi — alat yang berguna untuk menyimpan objek daripada jenis yang sama.

Mari cuba ingat antara muka berkaitan koleksi utama:

Senaraikan , Tetapkan , Peta dan Baris Gilir .

Seperti biasa, alat tidak semestinya baik atau buruk — yang penting ialah sama ada anda menggunakannya untuk tujuan yang dimaksudkan. Dan untuk melakukan itu, kita mesti memahami sepenuhnya ciri khusus mereka untuk mengetahui koleksi yang hendak digunakan dan bila.

1. Senaraikan

Mari kita mulakan dengan koleksi yang paling banyak digunakan.

Senaraikan sedekat mungkin dengan tatasusunan lama biasa.

Koleksi ini membolehkan kami menyimpan senarai objek dari jenis yang sama dengan mudah tanpa perlu risau tentang saiz koleksi itu sendiri, seperti yang kami perlu lakukan jika kami menggunakan tatasusunan. Elemen koleksi diakses oleh indeks. Jika kita tahu dengan tepat di mana objek berada dan perlu mengaksesnya dengan kerap tanpa perlu menambah atau mengalih keluar elemen, Senarai adalah ideal.

2. Tetapkan

Set mempunyai struktur yang sama sekali berbeza.

Set paling sesuai apabila kita perlu menyimpan objek unik. Sebagai contoh, satu set pengarang dalam perpustakaan di mana setiap pengarang adalah unik. Tetapi kita tidak boleh pergi dan ambil mana-mana pengarang tertentu daripadanya. Set membolehkan kami menyemak dengan cepat sama ada pengarang tertentu terdapat dalam pustaka kami, iaitu kami boleh menyemak sama ada objek unik hadir dalam Set . Kami juga boleh mengulangi keseluruhan koleksi, mengakses setiap elemen, tetapi melakukan itu tidak optimum.

Dalam erti kata lain, untuk pustaka kami, Set boleh mewakili koleksi semua pengarang unik untuk menyemak dengan cepat jika ada pengarang tertentu.

3. Peta

Peta lebih seperti kabinet pemfailan, di mana setiap fail ditandatangani dan boleh menyimpan objek individu atau keseluruhan struktur. Peta harus digunakan dalam kes di mana kita perlu mengekalkan pemetaan dari satu nilai ke nilai yang lain.

Untuk Map , perhubungan ini dipanggil pasangan nilai kunci.

Kami boleh menggunakan struktur ini dalam perpustakaan kami dengan menggunakan objek pengarang sebagai kunci dan senarai ( Senarai objek) buku sebagai nilai. Oleh itu, selepas menyemak Set untuk melihat sama ada objek pengarang wujud dalam perpustakaan, kita boleh menggunakan objek pengarang yang sama untuk mendapatkan Senarai bukunya daripada Peta .

4. Beratur

Baris gilir ialah koleksi yang — mengejutkan! — melaksanakan gelagat baris gilir. Dan baris gilir boleh sama ada LIFO (Masuk Terakhir, Keluar Dahulu) atau FIFO (Masuk Dahulu, Keluar Dahulu). Apatah lagi, baris gilir boleh menjadi dua arah, atau "berdua".

Struktur ini berguna apabila objek yang ditambahkan pada kelas perlu digunakan mengikut susunan ia diterima. Sebagai contoh, ambil perpustakaan kami.

Kami boleh menambah pelawat yang baru tiba pada Baris Gilir dan melayani mereka secara bergilir-gilir, mengeluarkan buku yang mereka datangi.

Seperti yang kita dapat lihat, setiap struktur ini adalah baik jika digunakan untuk tujuan yang dimaksudkan. Dan kami mendapati kegunaan yang baik untuk semua empat jenis koleksi dalam satu contoh perpustakaan.

2. Kerumitan

Seperti yang telah dinyatakan, koleksi yang kami pertimbangkan di atas adalah antara muka, yang bermaksud ia mesti mempunyai pelaksanaan untuk kami menggunakannya.

Sama seperti memalu paku dengan mikroskop bukanlah idea terbaik, tidak setiap pelaksanaan koleksi sesuai untuk setiap situasi.

Apabila memilih alat yang sesuai untuk pekerjaan, kita biasanya melihat 2 ciri:

• Sejauh manakah alat itu sesuai dengan kerja?
• Berapa cepat ia akan menyelesaikan kerja?

Kami telah meluangkan sedikit masa untuk memikirkan cara memilih alat yang sesuai untuk sesuatu kerja, tetapi kelajuannya adalah sesuatu yang baharu.

Dalam pengkomputeran, kelajuan alat sering dinyatakan dari segi kerumitan masa dan dilambangkan dengan huruf besar O.

Apakah kerumitan masa di dunia?

Dalam istilah mudah, kerumitan masa menunjukkan masa yang diperlukan untuk algoritma dalam koleksi untuk melaksanakan tindakan tertentu (menambah/mengalih keluar elemen, mencari elemen).

ArrayList lwn LinkedList

Mari kita lihat ini menggunakan dua pelaksanaan antara muka Senarai — ArrayList dan LinkedList .

Untuk penampilan luar, bekerja dengan koleksi ini adalah serupa:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Seperti yang anda lihat, untuk kedua-dua jenis koleksi, menambah, mendapatkan dan mengalih keluar elemen kelihatan sama. Ini kerana ini adalah pelaksanaan pada antara muka yang sama. Tetapi di situlah persamaan berakhir.

Oleh kerana pelaksanaan antara muka Senarai yang berbeza , kedua-dua struktur ini melakukan tindakan yang berbeza dengan lebih cekap daripada yang lain.

Pertimbangkan untuk mengalih keluar dan menambah elemen.

Jika kita perlu mengalih keluar elemen dari tengah ArrayList , kita perlu menulis ganti mana-mana bahagian senarai mengikut elemen yang kita alih keluar.

Katakan kami mempunyai senarai 5 elemen dan kami ingin mengalih keluar yang ke-3.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Dalam kes ini, penyingkiran membebaskan satu sel, jadi kita perlu menulis elemen ke-4 di mana yang ke-3 berada, dan yang ke-5 di mana yang ke-4.

Ini adalah sangat tidak cekap.

Perkara yang sama berlaku apabila menambah elemen ke tengah senarai.

LinkedList distrukturkan secara berbeza. Menambah atau mengalih keluar elemen adalah pantas, kerana kita hanya perlu menukar rujukan dalam elemen sebelumnya dan seterusnya, dengan itu mengecualikan objek yang kita alih keluar daripada rantaian unsur.

Kembali kepada contoh senarai 5 elemen yang sama, selepas mengalih keluar elemen ke-3, apa yang perlu kita lakukan hanyalah menukar rujukan elemen ke-2 kepada elemen seterusnya dan rujukan elemen ke-4 kepada yang sebelumnya.

Apabila elemen ditambahkan pada senarai, proses yang sama berlaku, tetapi sebaliknya.

Perhatikan betapa kurang kerja yang perlu kita lakukan dalam LinkedList berbanding dengan ArrayList . Dan itu hanya 5 elemen. Jika senarai kami mempunyai 100 atau lebih elemen, kelebihan LinkedList akan menjadi lebih ketara.

Tetapi bagaimana keadaan berubah jika kita mengakses elemen mengikut indeks?

Semuanya adalah sebaliknya di sini.

Memandangkan ArrayList berstruktur sebagai tatasusunan biasa, mendapatkan sebarang elemen mengikut indeksnya akan menjadi sangat mudah untuk kami. Kami hanya mengalihkan penunjuk ke tempat tertentu dan mendapatkan elemen dari sel yang sepadan.

Tetapi LinkedList tidak berfungsi seperti itu. Kita perlu melalui semua elemen senarai untuk mencari elemen dengan indeks tertentu.

Bolehkah kita cuba menyatakan semua ini dari segi O besar?

Mari mulakan dengan mengakses elemen mengikut indeks.

Dalam ArrayList , ini berlaku dalam satu langkah, tidak kira di mana elemen itu berada dalam senarai. Sama ada di akhir atau permulaan.

Dalam kes ini, kerumitan masa ialah O(1) .

Dalam LinkedList , kita perlu mengulangi beberapa elemen yang sama dengan nilai indeks yang kita perlukan.

Kerumitan masa untuk tindakan sedemikian ialah O(n) , dengan n ialah indeks elemen yang kita perlukan.

Di sini anda melihat bahawa nombor yang kami letakkan dalam kurungan besar-O sepadan dengan bilangan tindakan yang dilakukan.

Shell kita kembali untuk mengalih keluar dan menambah?

Mari kita mulakan dengan LinkedList.

Oleh kerana kita tidak perlu melakukan sejumlah besar tindakan untuk menambah atau mengalih keluar elemen, dan kelajuan operasi ini tidak bergantung dalam apa cara sekalipun pada lokasi elemen tersebut, kerumitannya dinyatakan sebagai O(1) dan dikatakan menjadi tetap.

Kerumitan masa operasi ini untuk ArrayList juga O(n) , yang kami panggil kerumitan linear.

Dalam algoritma dengan kerumitan linear, masa berjalan bergantung secara langsung pada bilangan elemen yang akan diproses. Ia juga mungkin bergantung pada kedudukan elemen, sama ada pada permulaan senarai atau menjelang akhir.

Kerumitan masa juga boleh menjadi logaritma. Ini dinyatakan sebagai O(log n) .

Sebagai contoh, pertimbangkan TreeSet diisih yang terdiri daripada 10 nombor. Kami ingin mencari nombor 2.

Memandangkan senarai itu diisih dan tidak mengandungi pendua, kita boleh membahagikannya kepada dua dan menyemak separuh mana yang akan mengandungi nombor yang dikehendaki, buang bahagian yang tidak berkaitan dan kemudian ulangi proses ini sehingga kita mencapai elemen yang dikehendaki. Akhirnya, kami akan mencari (atau tidak mencari) nombor selepas memproses log(n) bilangan elemen.

Berikut ialah jadual yang meringkaskan kerumitan masa bagi koleksi yang lain.

Memandangkan kami mempunyai jadual yang menunjukkan kerumitan masa koleksi popular, kami boleh menjawab soalan mengapa, daripada begitu banyak koleksi, kami paling kerap menggunakan ArrayList , HashSet dan HashMap .

Sememangnya mereka adalah yang paling cekap untuk kebanyakan tugas :)