To'plamlardan foydalanish bo'yicha maslahatlar

1. To'plamlar ro'yxati

Eslay olsang, Java-da bir xil turdagi obyektlarni saqlash uchun qulay vosita - to'plamlar mavjud.

Keling, to'plamlarning asosiy interfeyslarini eslab o'tamiz:

List, Set, Map va Queue.

Har qanday vositaning to'g'ri yoki noto'g'ri yo'li yo'q, agar u o'z vazifasini bajarsa. Va buning uchun ularning xususiyatlarini yaxshi tushunishimiz kerak, qachon va qaysi to'plamdan foydalanish kerakligini bilish uchun.

1. List

Keling, eng ko'p foydalaniladigan to'plamdan boshlaymiz.

List oddiy massiv bilan juda o'xshash. Nomidan ko'rinib turganidek, bu ro'yxat (list).

Bu to'plam bizga bir xil turdagi obyektlarni ro'yxat sifatida qulay saqlash imkonini beradi, massivlarda bo'lgani kabi to'plamning o'lchami haqida qayg'urmasdan. To'plam elementlariga indeks orqali murojaat qilinadi. Agar biz ob'ektning qayerda turganini aniq bilsak va unga tez-tez murojaat qilish kerak bo'lsa, elementlarni qo'shish yoki o'chirish kerak bo'lmasa, List juda mos variant hisoblanadi.

2. Set

Set (jamlanma) butunlay boshqacha tuzilishga ega.

Birinchi navbatda, Set dan foydalanish kerak, agar bizga noyob obyektlarni saqlash kerak bo'lsa. Masalan, bu kutubxonadagi mualliflar to'plami, har bir muallif noyob bo'lgan joyda. Ammo biz o'z to'plamimizda muayyan muallifni oddiygina topib olishimiz mumkin emas. Set funksionalligi bizga kutubxonada muayyan muallif borligini tezda tekshirish imkoniyatini beradi. Shuningdek, to'plamdagi har bir elemеnt orqali o'tib, qidirish mumkin, ammo bu optimal emas.

Ya'ni, kutubxonadagi Set mualliflar to'plami sifatida xizmat qilishi mumkin, muallif bor-yo'qligini tezda tekshirish uchun.

3. Map

Map (lug'at) ko'proq kartoteka kabi, har bir uyacha imzolangan, unda alohida obyektlar yoki to'liq tuzilmalar saqlanishi mumkin. Mapdan bir qiymatni boshqasiga moslashtirish kerak bo'lganda foydalanish kerak.

Mapda bu kalit – qiymat moslashuvi deb ataladi.

Bizning kutubxonamizda, muallif ob'ektini kalit sifatida va kitoblar ro'yxatini (List) qiymat sifatida ishlatishimiz mumkin. Setda muallifning kutubxonada bor-yo'qligini tekshirib, biz muallif ob'ektiga qarab Mapdan uning kitoblar ro'yxatini olamiz.

4. Queue

Queue (navbat) – bu navbat sifatida qurilgan to'plam. Bu navbat LIFO (oxirgi kirdi, birinchi chiqdi) yoki FIFO (birinchi kirdi, birinchi chiqdi) bo'lishi mumkin. Shu bilan birga, navbat ikki yo'nalishli bo'lishi mumkin, ikkala tomondan chiqishlar bilan.

Bu vosita ob'ektlar, bizning sinf yoki metodga navbat bilan kelishi kerak bo'lgan hollarda qulaydir. Masalan, bizning kutubxonada.

Biz yangi kelgan mehmonlarni Queuega qo'shib, navbat bilan ularga kitoblar berish orqali xizmat ko'rsatishimiz mumkin.

Ko'rib turganimizdek, barcha tuzilmalar o'z maqsadiga muvofiq ishlatilsa yaxshi. Va kutubxona misolida, biz to'rt turdagi to'plamlarni ishlatdik.

2. Murakkablik

Yuqorida ko'rganimizdek, ko'rib chiqqan to'plamlar interfeyslar, shuning uchun ularda biz foydalanadigan realizatsiyalar bo'lishi kerak.

Chukur mikroskop bilan mix urish - eng yaxshi g'oya emas, shuning uchun biz aynan qaysi to'plam realizatsiyasini qaysi holatda ishlatishni bilishimiz kerak.

Ko'pincha, biror vositani tanlayotganda biz ikki ko'rsatkichga qaraymiz:

• bu vosita qanday vazifaga mos keladi
• u bilan ishlash tezligi qanday bo'ladi

Agar biz mos vosita tanlovini unchalik emas bilsak, uning ishlash tezligi - bu yangi bir narsa.

Ish tezligi ko'pincha vaqt murakkabligi orqali ifodalanadi va katta O harfi bilan belgilanadi.

Vaqt murakkabligi nima o'zi?

Sodda qilib aytganda, bu murakkablik to'plamda ma'lum bir harakat (elementni qo'shish, o'chirish, qidirish) uchun ishlab chiqilgan algoritmning ish vaqtiga ishora qiladi.

ArrayList vs LinkedList

Keling, buni List interfeysining ikki realizatsiyasi - ArrayList va LinkedList misolida ko'rib chiqamiz.

Ushbu ikki realizatsiya o'rtasidagi farq qisman mana bu maqolada eslatilgan.

Tashqaridan qaraganda, bu to'plamlar bilan ishlash o'xshash ko'rinadi:

// String qo'shish, olish, o'chirish
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);
    

E'tibor berganingizdek, har ikkala holatda biz element qo'shish, olish va o'chirishni bir xil yo'sin bilan bajaramiz. Bu, biz bir xil interfeys asosida realizatsiyalar yaratganimiz uchun. Ammo bu o'xshashlik shu yerda tugaydi.

List interfeysining turli realizatsiyalari tufayli bu ikkita tuzilma turli xil foydalanishda turli samaradorlikka ega.

Elementni qo'shish va o'chirish operatsiyasiga misol ko'rib chiqamiz.

Agar ArrayListning o'rtasidan biror elementni o'chirish kerak bo'lsa, biz har doim o'chirilayotgan elementdan keyingi qismni qayta yozishimiz kerak bo'ladi.

Masalan, 5 ta elementdan iborat ro'yxatingiz bor va 3-elementni o'chirish kerak bo'lsa.

// 2 indeksdagi elementni o'chirish
List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
list.remove(2);
    

Bu holda, o'chirilganidan so'ng, 4-elementni 3-ning, 5-elementni esa 4-ning o'rniga o'tkazishimiz kerak bo'ladi.

Bu juda samarasiz.

Huddi shu narsa ro'yxatning o'rtasiga element qo'shish jarayonida ham sodir bo'ladi.

LinkedList esa boshqacha tuzilgan. Undan element qo'shish yoki o'chirish tez amalga oshadi, chunki biz faqatgina oldingi va keyingi elementlarning havolalarini o'zgartiramiz va o'chirilgan elementni zanjirdan chiqaramiz.

5 ta elementli ro'yxat misolida, 3-elementni o'chirganimizda, biz 2-elementning keyingi havolasini va 4-elementning oldingi havolasini o'zgartiramiz.

Xuddi shu narsa, lekin teskari tarzda, ro'yxatga element qo'shishda sodir bo'ladi.

E'tibor bering, LinkedListda biz qiladigan harakatlar soni ArrayListga qaraganda qancha kam. Va bu faqatgina 5 element. Ro'yxatda 100 va undan ko'p elementlar bo'lsa, LinkedListning afzalligi yanada sezilarli bo'lardi.

Ammo, agar biz elementga indeks orqali murojaat qilsak, vaziyat qanday o'zgaradi?

Bu erda hamma narsa teskarisiga bo'ladi.

Chunki ArrayList oddiy massiv sifatida tuzilgan, biz istalgan elementni indeks orqali osonlik bilan olamiz. Biz faqat ko'rsatkichni ma'lum bir joyga o'tkazib, hujayradan elementni olamiz.

Ammо LinkedListda bunday oddiy bo'lmaydi. Biz kerakli indeksga ega elementni topish uchun barcha elementlarni ko'rib chiqishimiz kerak bo'ladi. Faqat bu holatda uni indeks emas, balki ketma-ket raqam deb atash mantiqli.

Keling, buni katta O orqali ifodalashga harakat qilamiz?

Elementga indeks orqali murojaat qilishdan boshlaymiz.

ArrayListda bu bir harakatda amalga oshadi, elementning ro'yxatda qayerda joylashganidan qat'iy nazar. Boshlanishida yoki oxirida.

Bu holatda vaqt murakkabligi O(1) bo'ladi.

LinkedListda esa bizga kerakli indeksga ega elementlarni ko'rib chiqish kerak bo'ladi.

Bu harakat uchun vaqt murakkabligi O(n) bo'ladi - bu erda n kerakli elementning indeksi.

Demak, katta O qavslarida biz amalga oshirilayotgan harakatlar soniga mos keluvchi sonni joylashtiramiz.

Yana qo'shish va o'chirishga qaytamizmi?

LinkedList bilan boshlaymiz.

Chunki biz elementni qo'shish yoki olib tashlash uchun ko'p harakatlar qilmaganimiz uchun, va bu operatsiya tezligi elementning qayerda joylashganiga bog'liq emas, murakkablik quyidagicha ko'rinadi - O(1) va u doimiy deb ataladi.

ArrayListning bu operatsiyasi murakkabligi esa O(n) bo'ladi va u chiziqli deb ataladi.

Chiziqli murakkablikka ega algoritmlarda ish vaqti to'g'ridan-to'g'ri qayta ishlanishi kerak bo'lgan elementlar soniga bog'liq. Bu elementning ro'yxatda boshlanishida yoki oxiriga yaqin joylashganligiga bog'liq bo'lishi mumkin.

Murakkablik hali logarifmik ham bo'ladi. U quyidagicha ko'rinadi — O(log n).

Misol sifatida 10 ta soni bo'lgan saralangan TreeSet ro'yxatini ko'rib chiqamiz, unda 2 sonini topish kerak.

Chunki ro'yxat saralangan va unda dublikatlar yo'q, biz uni yarmiga ajratib, qaysi qismida kerakli son qolganligini tekshirishimiz mumkin, bir qismini tashlaymiz va kerakli elementga yetguncha harakatlarni takrorlaymiz. Natijada biz sonni log(n) miqdorda elementlarni qayta ishlash orqali topamiz.

Keling, mashhur to'plamlar uchun vaqt murakkabligi tavsiflangan jadvalga bir ko'z tashlaymiz.

Endi, bizda mashhur to'plamlar uchun vaqt murakkabligi keltirilgan jadval mavjud bo'lganda, ko'p miqdordagi to'plamlardan ArrayList, HashSet va HashMapni nega ko'pincha ishlatamiz?

Ular ko'pgina vazifalar uchun maksimal darajada samarali :)