Kolleksiýalary ulanmak boýunça maslahatlar

1. Kolleksiýalaryň Sanawy

Ine, Java-da meňzeş görnüşli obýektleri saklamak üçin amatly gurallar bar - kolleksiýalar.

Baş interfeýsleri ýatlamaga synanyşalyň:

List, Set, Map we Queue.

Görşüň ýaly, dogry ýa-da nädogry gurallar ýok, diňe maksada laýyk ulanylsa bolýar. Şonuň üçin olaryň aýratynlygyna düşünmek gerek, sebäbi nähili we haçan kolleksiýa ulanmalydygyny bilmeli.

1. List

Geliň iň köp ulanylýan kolleksiýadan başlalyň.

List adaty masş tablisasy ýaly. Ady näme? Sanaw (list) diýmek.

Bu kolleksiýa biziň üçin bir görnüşli obýektleriň sanawyny amatly saklamaga mümkinçilik berýär, masş tablisasy ýaly ululygy hakda alada etmeýäris. Kolleksiýanyň elementlerine indeks arkaly ýüzlenýäris. Obýektiň nirede ýerleşýändigini we oňa ýygy-ýygydan ýüzlenmeli, elementleri ýygy-ýygydan goşmaly ýa-da aýyrmaly däl bolsa, List gowy wariant.

2. Set

Set (köpülik) düýbünden başgaça gurluşa eýe.

Ilkinji nobatda, Set ulanmak gerek, eger bize üýtgeşik obýektleri saklamak gerek bolsa. Mysal üçin, her awtor üýtgeşik bolan kitap otagynda awtorlaryň sanawy. Ýöne, diňe awtorlaryň sanawyna ýüzlenip, belli bir awtory alyp bilmeris. Set-iň funksiýasy, belli bir awtoryň kitap otagynda bardygyny çalt barlamaga mümkinçilik berýär. Şeýle hem, kolleksiýadaky her elementi gözden geçirip bolar, bu optimal däl.

Şeýlelik bilen, kitap otagynda Set awtorlaryň sanawy bolup biler, awtoryň kitap otagynda bardygyny çalt barlamak üçin.

3. Map

Map (sözlük) has köp kartoçka ýaly, her hüjajyk gol çekilen, onda aýratyn obýektleri ýa-da tutuş gurluşlary saklap bileris. Map bir bahanyň başga bir bahanyňky bolan ýagdaýlarda ulanylmaly.

Map-da bu açar - baha gabat gelmeýär diýilýär.

Kitap otagymyzda, awtoryň obýektini açar hökmünde, kitaplaryň sanawyny (List) baha hökmünde ulanyp bileris. Şu awtoryň kitap otagynda bardygyny Set-da barlap, şol awtoryň obýekti bilen Map-dan kitaplaryň sanawyny alyp bileris.

4. Queue

Queue (nobat) - nobat görnüşinde gurlan kolleksiýa. Bu nobat diňe LIFO (Last In First Out – iň soňky giren, ilkinji çykar) däl, eýsem FIFO (First In First Out – ilkibaş giren, ilkinjisi çykar) bolup biler. Nobat iki tarapdan hem çykyp bilýän bolup biler.

Bu gural, klassyň, metodanyň aşakdaky obýektleri ulanmaly bolsa amatly. Mysal üçin, kitap otagymyzda.

Biz täze gelen myhmanlary Queue-a goşup, toparlaýyn hyzmat edip, kitaplary olaryň almagy üçin berip bileris.

Görüşiň ýaly, ähli gurluşlar maksada laýyk ulanylsa gowy. Bir mysalda, kitap otagynda, ähli dört görnüş kolleksiýa ulanýarys.

2. Çylşyrymlylyk

Ýokarda gözden geçirilen kolleksiýalar interfeýslerdir, bu bolsa olaryň ulanyp boljak realizasiýalarynyň boljakdygyny aňladýar.

Ölçegi mikroskop bilen doňdurmak gowy pikir däl, şonuň üçin nirede realizasiýany ulanjakdygyňy bilmek gaýratlyjak.

Kämilleşen guralyň saýlawynda köplenç 2 ölçeglige seredýäris:

• bu gural mesele üçin nädip laýyk gelýär
• onuň bilen işlemek näçe çalt bolar

Saýlanan guralyň mesele boýunça laýyklygyna belli bir derejede düşündik, indi işlemegiň tizligi - bu täze zat.

İşlemegiň tizligini köplenç wagt çylşyrymlylygy bilen aňladýarlar we uly O harpy bilen belleýärler.

Bu wagt çylşyrymlylygy näme?

Ýönekeý söz bilen aýdylanda, bu çylşyrymlylyk, algoritmiň wagt netijeliligini görkezýär, bu kolleksiýada şol ýa-da beýleki hereketleri (element goşmak, aýyrmak, gözlemek) almak üçin goýlan.

ArrayList vs LinkedList

Interfeýs List iki realizasiýasynyň mysaly barada pikir edeliň — ArrayList we LinkedList.

Bu iki realizasiýanyň tapawudy barada käbirleri agzalan bu makalada.

Öňki görnüşde, bu kolleksiýalar bilen işlemek meňzeýär:

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

Çykyş görnüşli bolsa, bu interfeýsleriň meňzeşligi soňlanýar.

Interfeýs List-iň realizasiýasynyň tapawudy sebäpli, bu iki gurluş dürli ulanylan ýagdaýda dürli netijelilik bardyr.

Elementi aýyrmak we goşmak operasiýasyny gözden geçireliň.

Eger ortaça sanawdan elementi aýyrjak bolsaň, ArrayList-da, her gezek aýyrýan elementden soňky sanawyň galan bölegini overwriting ederis.

Geliň, 5 aýyrmak elementleri bilen bir sanaw bar diýeliň we 3-nji elementi aýyrmaly.

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
list.remove(2);
    

Bu ýagdaýda aýrylandan soň boş gözenek boljak, we 3-nji ýerinde 4-nji element, 4-nji ýerinde 5-nji element ýazmaly bolarys.

Bu maksimum netijesiz.

Sanawyň ortaça elementini goşmak bilen bu ýagdaý ýüze çykýar.

LinkedList başgaça gurulandyr. Ondan elementleri goşmak ýa aýyrmak çalt bolýar, çünki öňki we soňky elementde linkleri üýtgedip, aýyrmaly elementi elementleriň zynjyryndan çykarmaly bolarys.

5 elementli sanawyň mysalynda 3-nji elementi aýyrsaň, 2-nji elementde indiki elemente linki we 4-nji elementde öňki elemente linki çalyşsaň bolýar.

Bu tersi bolup çykýar, diňe element goşmak üçin.

Görüşleriňize görä, LinkedList-da ArrayList-da edişine garanyňda az hereket edýäris. Diňe 5 elementde. Sanawda 100 we köp element bolsa, LinkedList-niň artykmaçlygy has duýarly bolardy.

Ýöne ýagdaý üýtgärmi, eger elementi indeksi boýunça ýüzlenmeli bolsa?

Şeýle ýagdaý doly tersi bolar.

ArrayList adaty masş tablisasy ýaly bolup, indeks boýunça elementi almak gaty aňsat bolar. Ýöne bir pointeri belli bir ýere geçirip, gözenekden element alyp bileris.

Ýöne LinkedList-da bu beýle aňsat bolmaz. Indeksi boýunça elementi tapmak üçin ähli elementleri gözden geçirmeli bolarys. Bu ýagdaýda bu indeksi ýedi bu sanawda däl, orna gelerligi diýip atlandyrmaly.

Muny "Uly O" bilen aňlatmaga synanyşalyň?

Başlangyç elemente ýüzlenmek bilen başla.

Üstesinden ArrayList diýmek hakyky bir hereketde bolardy, sanawdaky elementiň ýerleşýän ýerine garamazdan. Başlygynda ýa-da aýagyndaky.

Wagt çylşyrymlylygy bu ýagdaýda O(1) bolardy.

Ýöne LinkedList-da, bize indi gerek elementlere çenli elementleri gözden geçirmeli bolarys.

Bu hereket üçin wagt çylşyrymlylygy O(n) bolar - n bolsa, bize gerekli elementiň indeksi.

Netijede, uly O içinde, amala aşyrýan hereketleriň mukdaryny görkezýän sanaty ýerleşdirýäris.

Elementleri aýyrmak we goşmak bilen yza dolanyp baryp?

LinkedList bilen başla.

Elementleri goşmak ýa-da aýyrmak üçin köp hereket etmeli däl bolup, operasiýanyň tizligi elementiň ýerleşýän ýerine garaşmaýar, çylşyrymlylyk O(1) bolar we konstant.

Şu operasiýa çylşyrymlylygy ArrayList üçin O(n) bolar we liniýer.

Liniýer çylşyrymlylygy bolan algoritmlerde iş wagty işlejek elementleriň mukdaryna dolulygyna garaşly bolýar. Şeýlede elementleriň orny - sanawyň başlygynda ýa-da aýagyndaky - täsir edýär.

Beýleki bir çylşyrymlylyk logarifmleriňki bolup biler. Ol şeýlebir görnüşde – O(log n).

Əgetmek üçin, sorted TreeSet sanawynda 10 sany elementden 2-ni tapmaly.

Sanaw sorted we duplicate ýok bolany üçin, biz ony iki bölege bölüp söküp, islän nomerimiz haýsy böleginde galandygyny barlap bileris, bir bölegini başga düşürip, oý laplýak baryna çenli. Ahyrsoňy elementi log(n) mukdarda barlap taparys.

Öňümizde giňden ROWLYKLY tablisasy bar, şu tablisany gözden geçireliň.

Birden ROWLYK tablisasy elimizde bar wagty, häzirki wagtda köplenç ArrayList, HashSet we HashMap-y ulanyp, fikriňizi näme üçin ulanýarys?

Olar maksimum derejede optimal.—:)!