Mga tip sa paggamit ng mga koleksyon

1. Listahan ng mga koleksyon

Tulad ng naaalala mo, ang Java ay may mga koleksyon — isang madaling gamiting tool para sa pag-iimbak ng mga bagay na may parehong uri.

Subukan nating alalahanin ang pangunahing mga interface na nauugnay sa koleksyon:

Listahan , Set , Mapa at Queue .

Gaya ng dati, ang mga tool ay hindi palaging mabuti o masama — ang mahalaga ay kung ginagamit mo ang mga ito para sa kanilang nilalayon na layunin. At para magawa iyon, dapat nating lubos na maunawaan ang kanilang mga partikular na feature para malaman kung aling koleksyon ang gagamitin at kung kailan.

1. Listahan

Magsimula tayo sa pinaka ginagamit na koleksyon.

Maglista nang mas malapit hangga't maaari sa isang simpleng lumang array.

Ang koleksyon na ito ay nagbibigay-daan sa amin na maginhawang mag-imbak ng isang listahan ng mga bagay na may parehong uri nang hindi nababahala tungkol sa laki ng mismong koleksyon, tulad ng kakailanganin namin kung gumagamit kami ng array. Ang mga elemento ng koleksyon ay ina-access sa pamamagitan ng index. Kung alam natin nang eksakto kung nasaan ang isang bagay at kailangan itong i-access nang madalas nang hindi kinakailangang magdagdag o mag-alis ng mga elemento, mainam ang isang Listahan .

2. Itakda

Ang set ay may ganap na naiibang istraktura.

Ang set ay pinakaangkop kapag kailangan nating mag-imbak ng mga natatanging bagay. Halimbawa, isang hanay ng mga may-akda sa isang aklatan kung saan ang bawat may-akda ay natatangi. Ngunit hindi tayo maaaring pumunta lamang at kumuha ng anumang partikular na may-akda mula dito. Hinahayaan kami ng Set na mabilis na suriin kung ang isang partikular na may-akda ay naroroon sa aming library, ibig sabihin, maaari naming suriin kung ang isang natatanging bagay ay naroroon sa isang Set . Maaari din nating ulitin ang buong koleksyon, na i-access ang bawat elemento, ngunit hindi ito pinakamainam.

Sa madaling salita, para sa aming library, maaaring kumatawan ang isang Set sa koleksyon ng lahat ng natatanging may-akda upang mabilis na masuri kung mayroong partikular na may-akda.

3. Mapa

Ang mapa ay mas katulad ng isang filing cabinet, kung saan ang bawat file ay nilagdaan at maaaring mag-imbak ng mga indibidwal na bagay o buong istruktura. Dapat gamitin ang mapa sa mga kaso kung saan kailangan nating magpanatili ng pagmamapa mula sa isang halaga patungo sa isa pa.

Para sa Map , ang mga ugnayang ito ay tinatawag na key-value pairs.

Magagamit namin ang istrukturang ito sa aming aklatan sa pamamagitan ng paggamit ng mga bagay ng may-akda bilang mga susi at mga listahan ( Mga bagay sa listahan ) ng mga aklat bilang mga halaga. Kaya, pagkatapos suriin ang isang Set upang makita kung mayroong isang object ng may-akda sa library, maaari naming gamitin ang parehong object ng may-akda upang makakuha ng Listahan ng kanyang mga libro mula sa isang Map .

4. Pila

Ang queue ay isang koleksyon na — nakakagulat! — nagpapatupad ng gawi ng isang pila. At ang pila ay maaaring LIFO (Last In, First Out) o FIFO (First In, First Out). Higit pa rito, ang pila ay maaaring bidirectional, o "double-ended."

Nakatutulong ang istrukturang ito kapag ang mga bagay na idinagdag sa klase ay kailangang gamitin sa pagkakasunud-sunod na natanggap ang mga ito. Halimbawa, kunin ang aming library.

Maaari kaming magdagdag ng mga bagong dating na bisita sa isang Queue at pagsilbihan sila nang sunod-sunod, na nagbibigay ng mga aklat na pinupuntahan nila.

Tulad ng nakikita natin, ang bawat isa sa mga istrukturang ito ay mabuti kung gagamitin para sa layunin nito. At nakakita kami ng magagandang gamit para sa lahat ng apat na uri ng mga koleksyon sa isang halimbawa ng library.

2. Pagiging kumplikado

Gaya ng nabanggit na, ang mga koleksyon na aming isinasaalang-alang sa itaas ay mga interface, na nangangahulugang dapat silang magkaroon ng mga pagpapatupad upang magamit namin ang mga ito.

Tulad ng pagmamartilyo ng mga kuko gamit ang isang mikroskopyo ay hindi ang pinakamahusay na ideya, hindi lahat ng pagpapatupad ng isang koleksyon ay angkop sa bawat sitwasyon.

Kapag pumipili ng tamang tool para sa isang trabaho, karaniwang tinitingnan namin ang 2 katangian:

• Gaano kahusay ang tool sa trabaho?
• Gaano kabilis nito matatapos ang trabaho?

Gumugol kami ng ilang oras sa pag-iisip kung paano pumili ng angkop na tool para sa isang trabaho, ngunit ang bilis nito ay bago.

Sa pag-compute, ang bilis ng isang tool ay madalas na ipinahayag sa mga tuntunin ng pagiging kumplikado ng oras at tinutukoy ng isang malaking titik O.

Ano sa mundo ang pagiging kumplikado ng oras?

Sa simpleng mga termino, ang pagiging kumplikado ng oras ay nagpapahiwatig ng oras na kinakailangan para sa isang algorithm sa koleksyon upang maisagawa ang isang partikular na aksyon (pagdaragdag/pag-alis ng isang elemento, paghahanap para sa isang elemento).

ArrayList kumpara sa LinkedList

Tingnan natin ito gamit ang dalawang pagpapatupad ng interface ng Listahan — ArrayList at LinkedList .

Para sa panlabas na anyo, ang pagtatrabaho sa mga koleksyong ito ay magkatulad:

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

Tulad ng nakikita mo, para sa parehong mga uri ng koleksyon, ang pagdaragdag, pagkuha, at pag-alis ng mga elemento ay mukhang pareho. Ito ay dahil ang mga ito ay mga pagpapatupad sa parehong interface. Ngunit doon nagtatapos ang pagkakatulad.

Dahil sa kanilang magkakaibang pagpapatupad ng interface ng Listahan , ang dalawang istrukturang ito ay gumaganap ng magkaibang mga pagkilos nang mas mahusay kaysa sa iba.

Isaalang-alang ang pag-alis at pagdaragdag ng isang elemento.

Kung kailangan nating mag-alis ng elemento sa gitna ng isang ArrayList , kailangan nating i-overwrite ang anumang bahagi ng listahan na sumusunod sa elementong aalisin natin.

Ipagpalagay na mayroon kaming isang listahan ng 5 elemento at gusto naming tanggalin ang pangatlo.

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

Sa kasong ito, ang pag-alis ay nagpapalaya ng isang cell, kaya kailangan nating isulat ang ika-4 na elemento kung saan naroon ang ika-3, at ang ika-5 kung nasaan ang ika-4.

Ito ay lubos na hindi epektibo.

Ang parehong nangyayari kapag nagdaragdag ng isang elemento sa gitna ng listahan.

Ang LinkList ay iba ang pagkakaayos. Ang pagdaragdag o pag-alis ng mga elemento ay mabilis, dahil kailangan lang nating baguhin ang mga sanggunian sa nakaraan at susunod na mga elemento, at sa gayon ay hindi kasama ang bagay na aalisin natin sa chain ng mga elemento.

Pagbabalik sa halimbawa ng parehong listahan ng 5 elemento, pagkatapos alisin ang ika-3 elemento, ang kailangan lang nating gawin ay baguhin lang ang reference ng 2nd element sa susunod na elemento at ang reference ng ika-4 na elemento sa nauna.

Kapag ang isang elemento ay idinagdag sa listahan, ang parehong proseso ay nangyayari, ngunit sa kabaligtaran.

Pansinin kung gaano kaunting trabaho ang kailangan nating gawin sa isang LinkedList kumpara sa isang ArrayList . At iyon ay 5 elemento lamang. Kung ang aming listahan ay may 100 o higit pang mga elemento, ang higit na kahusayan ng LinkedList ay magiging mas kapansin-pansin.

Ngunit paano magbabago ang sitwasyon kung ma-access natin ang isang elemento sa pamamagitan ng index?

Ang lahat ay eksaktong kabaligtaran dito.

Dahil ang ArrayList ay nakabalangkas bilang isang ordinaryong array, ang pagkuha ng anumang elemento sa pamamagitan ng index nito ay magiging napakadali para sa amin. Ililipat lang namin ang pointer sa isang tiyak na lugar at kunin ang elemento mula sa kaukulang cell.

Ngunit ang isang LinkList ay hindi gumagana sa ganoong paraan. Kailangan nating dumaan sa lahat ng elemento ng listahan upang mahanap ang elementong may partikular na index.

Susubukan ba nating ipahayag ang lahat ng ito sa mga tuntunin ng malaking O?

Magsimula tayo sa pamamagitan ng pag-access sa isang elemento ayon sa index.

Sa isang ArrayList , nangyayari ito sa isang hakbang, hindi alintana kung saan matatagpuan ang elemento sa listahan. Sa dulo man o sa simula.

Sa kasong ito, ang pagiging kumplikado ng oras ay magiging O(1) .

Sa isang LinkedList , kailangan nating umulit sa isang bilang ng mga elemento na katumbas ng halaga ng index na kailangan natin.

Ang pagiging kumplikado ng oras para sa naturang aksyon ay O(n) , kung saan ang n ay ang index ng elementong kailangan natin.

Dito makikita mo na ang numerong inilagay namin sa big-O parentheses ay tumutugma sa bilang ng mga aksyon na ginawa.

Shell babalik tayo sa pag-alis at pagdaragdag?

Magsimula tayo sa LinkList.

Dahil hindi namin kailangang gumawa ng malaking bilang ng mga aksyon upang magdagdag o mag-alis ng isang elemento, at ang bilis ng operasyong ito ay hindi nakasalalay sa anumang paraan kung saan matatagpuan ang elemento, ang pagiging kumplikado ay ipinahayag bilang O(1) at sinasabing upang maging pare-pareho.

Ang pagiging kumplikado ng oras ng operasyong ito para sa ArrayList ay O(n) , na tinatawag naming linear complexity.

Sa mga algorithm na may linear complexity, ang oras ng pagpapatakbo ay direktang nakasalalay sa bilang ng mga elementong ipoproseso. Maaaring depende rin ito sa posisyon ng elemento, ito man ay sa simula ng listahan o sa dulo.

Ang pagiging kumplikado ng oras ay maaari ding logarithmic. Ito ay ipinahayag bilang O(log n) .

Bilang halimbawa, isaalang-alang ang isang pinagsunod-sunod na TreeSet na binubuo ng 10 numero. Gusto naming hanapin ang numero 2.

Dahil ang listahan ay pinagsunod-sunod at walang mga duplicate, maaari naming hatiin ito sa kalahati at suriin kung aling kalahati ang maglalaman ng nais na numero, itapon ang hindi nauugnay na bahagi at pagkatapos ay ulitin ang prosesong ito hanggang sa maabot namin ang nais na elemento. Sa huli, mahahanap namin (o hindi mahahanap) ang numero pagkatapos ng pagproseso ng log(n) bilang ng mga elemento.

Narito ang isang talahanayan na nagbubuod sa pagiging kumplikado ng oras sa iba pang mga koleksyon.

Ngayong mayroon na kaming talahanayan na nagpapakita ng pagiging kumplikado ng oras ng mga sikat na koleksyon, masasagot namin ang tanong kung bakit, sa napakaraming koleksyon, madalas naming ginagamit ang ArrayList , HashSet at HashMap .

Ito ay simpleng sila ang pinaka mahusay para sa karamihan ng mga gawain :)