Datu struktūras –

  • Saraksti (Lists) un

  • Kopas (Sets)

Vai jums kādreiz ir bijis nepieciešams saglabāt dažus datus, bet neesat pārliecināts par to, kādu datu struktūru izmantot? Tā ir izplatīta kodēšanas problēma.

Šajā rakstā jūs atklāsiet divas svarīgas datu struktūras, kuras varētu izmantot. Saraksti un kopas, jeb Lists un Sets. Abas ļoti noderīgas datu struktūras ar savām stiprajām un vājajām pusēm. Saraksti un kopas ir izplatītas daudzās programmēšanas valodās. Sāksim ar sarakstu izpēti.

Datu struktūra – Saraksti, jeb Lists

Lielākajā daļā programmēšanas valodu saraksti tiek attēloti kā objekti. Tas nozīmē, ka papildus datu glabāšanai tiem ir arī savas iebūvētās metodes. Šeit tiek izmantota iebūvēta kārtošanas metode, lai sakārtotu skaitļus sarakstā.

list_piemērs = [1, 2, 3, 4, 5]

print(list_piemērs) # izvade būs [5, 4, 3, 2, 1]

list_piemērs.sort()

print(list_example) #izvade būs [1, 2, 3, 4, 5]

Tāpat kā ar masīviem (Arrays), parasti tiek atrasti saraksti, kas tiek deklarēti kā

  • virkne – string,
  • vesels skaitlis – integer
  • vai pludiņš – float.

Dažās programmēšanas valodās var būt saraksti ar jauktiem elementu veidiem. Saraksts ir abstrakts jēdziens, kas attiecas uz elementu konteineru. Stabila saraksta ieviešana tiek veikta, izmantojot masīvu vai saistīto sarakstu (Linked list). Uz masīvu balstīts saraksts ir sakārtota kolekcija, kas izveidota, izmantojot masīvus kā pamatā esošo datu struktūru. Tādējādi uz tiem attiecas tās pašas stiprās puses un ierobežojumi, kas saistīti ar masīviem. Uz masīvu balstītas ieviešanas ir saistītas ar sākotnējo izmēru, nevis vienkārši norāda uz citu mezglu, kā ar saistīto sarakstu. Dažas valodas pieprasa, lai jūs sākotnēji noteiktu, cik liela būs struktūra, savukārt citas pieļauj dinamiski augošas struktūras. Jāatzīmē, ka šī brīvība ir zināmā mērā virspusējā līmenī. Daudzām dinamiskām struktūrām ir sākotnējais izmērs, kas tiek automātiski konfigurēts momenta izveides laikā.

Array list

Kad šis ierobežojums tiek sasniegts, masīvs tiks kopēts jaunā struktūrā ar lielāku izmēru sadalījumu.

larger array list data structure

Tāpēc lēmums patvaļīgi nepiešķirt vietu sākumā var radīt atmiņas un datu apmaiņas izmaksas izpildes laikā, ja šādas datu struktūras var būt vairākas reizes jāpaplašina citu darbību izpildes laikā.

Apsveriet saraksta aprēķināšanas izmaksas, kas dinamiski pieaug, veicot darbības cilpā. Šajā gadījumā tas palīdzētu iestatīt sākotnējo saraksta lielumu kā lielāku, nevis dinamiski augošu, kas var būt “dārgi” ilgtermiņā, jo ir jāveido un jāpārkopē vērtības arvien lielākos sarakstos.

Saistītais saraksts, jeb Linked list

Saistītais saraksts darbojas citādi. Saistītajā sarakstā ir divas informācijas daļas, dati (data) un rādītājs (pointer) uz nākamo saraksta vienumu.

Saistītais saraksts sākas ar tukšu sarakstu, un tas var dinamiski augt, iekļaujot sarakstā jaunas šūnas.

 

Lai izveidotu saistīto sarakstu, jums vienkārši jāpievieno jauns mezgls un jānorāda saraksts uz tā atrašanās vietu. Tas padara tos ļoti ātrus lielu datu apjomu glabāšanai. Saistīto sarakstu elastība tiek panākta, iekļaujot dažas papildu krātuves prasības. Jo īpaši katrā mezglā ir jābūt atsaucei uz mezgliem ap to. Ir arī “galva – (head)” un “aste – (tail)”.

Galva ir unikāls mezgls, kas norāda, ka tas ir saraksta sākums, un aste norāda, kur saraksts beidzas. Šī pieeja datu struktūras lieluma palielināšanai ir ļoti spēcīga un var radīt ļoti lielas, bet pārvaldāmas datu kopas.

Datu struktūra – Kopas, jeb Sets

Ko nozīmē kopas, jeb sets? Kopa ir ļoti līdzīgs sarakstam. Tomēr kopa savus elementus uzglabās nesakārtotā veidā. Lai gan ir dažas iespējamās pasūtīto kopu realizācijas, kopām ir dažas neparastas tendences. Kopā būs tikai unikāli elementi, tāpēc jau esoša elementa pievienošana kopai neietekmēs tajā saglabātos datus. Nesakārtots process, kurā kopa glabā savu informāciju, nozīmē, ka kopas izdrukāšana ne vienmēr atspoguļos secību, kādā elements tika pievienots kopai. Kad vērtība ir pievienota kopai, to nevar mainīt. Tā vietā jums tas būtu jāizdzēš un tā vietā jāpievieno jauna vērtība.

Kopās ir iespējami īpaši ātri meklējumi. Tas ir tāpēc, ka, ja tas ir iekšējie mehānismi. Kopa izmanto jaucēj tabulas (Hash tables), lai noteiktu, kur uzglabāt kopas elementus.

Sets hash tables

Tāpēc katram skaitlim, kas tiek nodots kopai, tiks piemērota jaukšanas funkcija. Jaukšanas funkciju var definēt kā algoritmu, kas ņem dažus datus un kartē tos uz fiksēta lieluma vērtību. Vērtība teorētiski ir unikāla, un katru reizi, kad funkcija tiek lietota datiem, tiek atgriezta viena un tā pati vērtība. Tas nozīmē, ka kopas meklēšanu var veikt O(1) laikā. Tas ir saistīts ar mehānismu, kas tiek izmantots vērtību saglabāšanai komplektā. Par jaukšanas funkcijām sīkāk uzzināsiet kādā no nākošajiem rakstiem. O(n) pieeja būtu atkārtot visu datu struktūru, lai pārbaudītu vērtības esamību vai neesamību.

Tā vietā kopas ievades datiem piemēro kartēšanas funkciju un pārbauda iegūto izvadi, lai redzētu, vai tajā ir kāda vērtība. Ja tā notiek, vērtība tiek atgriezta. Ja tas komplektā nepastāv, dati nav saglabāti kopā, un tādējādi tiks atgriezts nepatiesa “false” atbilde. Lai gan kopas var veikt ārkārtīgi ātru meklēšanu, veiktspēja pasliktinās, strādājot ar ļoti lielām datu kopām. Tas ir saistīts ar jaukšanas funkcijas raksturu. Jo vairāk vērtību tiek saglabāta, jo lielāks ir sadursmes risks.

Sadursme ir tad, kad jaukšanas funkcijas atgriež vienu un to pašu unikālo kartējumu divām dažādām vērtībām. Jo lielāka ir izmantotā datu kopa, jo lielāka ir sadursmju iespējamība.

Saraksti un kopas dažādās programmēšanas valodās

Kopas un saraksti ir iebūvēti veidi daudzās valodās ar vispārīgu visaptverošu tēmu, kas ir kopīga lielākajai daļai valodu. Faktiskajā īstenošanā ir dažas smalkas atšķirības.

Šajā raksta turpinājumā jūs izpētīsiet dažas atšķirības starp sarakstiem un kopām dažādās programmēšanas valodās.

Mainīgums

Nemainības jēdziens jau ir apspriests. Konkrēti, tas ir veids, kā tiek izveidota datu struktūra. Nemaināmus objektus nevar mainīt izveides laikā, savukārt mainīgos objektus var mainīt pēc izveides. Kopas ir nemainīgas struktūras piemērs lielākajā daļā programmēšanas valodu. Tomēr objektus, kas tiek pievienoti kopām, var apstrādāt atšķirīgi atkarībā no valodas. Programmā JavaScript kopai var pievienot mainīgus objektus, kas Python nav atļauts. Izpratne par šo fundamentālo atšķirību sniegs ieskatu par to, kā valoda izmanto kopas.

Kāpēc kopas ir tik ātras, cik tās ir?

Iemesls ātrumam, ar kādu kopas var atrast vienumu, ir to pamatā esošā arhitektūra. Iestata saglabātās vērtības, izmantojot jaukšanas pieeju. Jaukt kaut ko nozīmē to paņemt un ģenerēt no tā unikālu rezultātu. Tas tiek darīts, piemērojot tam algoritmu, kas pārvērš ievadi vienkāršā burtciparu (vārdu un burtu) izvadē. Katru reizi, kad algoritms redz ievadi, tas vienmēr ģenerēs to pašu burtciparu izvadi. Pēc tam to izmanto jaucējtabulā (hash), kas izmanto unikālo jaucējkodu, lai informētu, kur atmiņā saglabāt vienumu. Tātad ar vienu aprēķinu var uzzināt, vai vērtība ir atmiņā vai nav. Tā vietā, lai meklētu katru elementu sarakstā, vienkārši izmantojiet jaukšanas funkciju un pārbaudiet, vai tā tiek izmantota.

Tāpēc kopas ir ātras, taču tās ir tik ātras arī tāpēc, ka nevarat mainīt saglabāto vērtību. Ja elementam izveidojat jauktu un saglabājat to atbilstoši šai jauktajai, tad maināt vienumu, un jaucējfunkcija to vairs nevarēs atrast. Tas ir viens no iemesliem, kāpēc Python ļauj saglabāt tikai nemainīgus objektus, kurus nevar mainīt kopās. Ne visas valodas piedāvā šo aizsardzību. Piemēram, JavaScript ļauj saglabāt mainīgus objektus. Tādējādi objekta aizsardzība tiek atstāta lietotāja ziņā, kodējot ar JavaScript kopām. Pieņemsim, ka vēlaties mainīt JavaScript mainīgo vērtību. Tādā gadījumā ir ieteicams izvilkt un dzēst mainīgo objektu, pirms to atkārtoti ievieto kopā kā jaunu elementu.

Tāpat kā Python, Kotlin neļaus mainīt elementus, kad tie ir pievienoti kopai. Tas nozīmē, ka komplektam ir tikai lasīšanas piekļuve (Read only). Ja vēlaties kopas, kuras var mainīt, Kotlinam ir cita veida komplekts, ko sauc par MutableSet. Kotlin komplekti ir ļoti daudzpusīgi un piedāvā virkni iebūvētu metožu, piemēram, max, min, summa un medium. Tas padara tos ļoti parocīgus, meklējot konkrētus vienumus skaitļu grupā.

Saraksti jeb Lists

Vēl viens svarīgs kolekcijas veids, par kuru ir vērts zināt, ir saraksti. Saraksti glabā elementus noteiktā secībā, kam var piekļūt, izmantojot indeksu. Indekss ir tikai skaitlis, kas tiek nodots sarakstam, kas norāda, ka šajā numura vietā atrastais elements ir jāatgriež. Indekss ir veids, kā elementi tiek meklēti sarakstā. Ja kāds vēlas uzzināt, vai kaut kas ir sarakstā, viņam ir jāveic meklēšana un jāpārbauda katrs vienums, tāpēc tie ir lēnāki nekā kopa. Turklāt saraksts ļaus tajās saglabāt visu veidu elementus. Nav atšķirības starp to, vai vienums ir mainīgs vai nemainīgs. Saraksti arī ļaus jums saglabāt vienumu dublikātus. Ir dažādi sarakstu veidi, kas tiek ieviesti atšķirīgi.

Tomēr galvenais, ko ir vērts atcerēties, ir tas, ka saraksts ļauj saglabāt atkārtotus vienumus un dažāda veida vienumus. Saraksts ir sakārtots, kas nozīmē, ka tas saglabās vienumu secību, kad tie tiks ievietoti. Tas atšķiras no kopām, kurās vienumi var tikt glabāti dažādās vietās, nevis tajās, kur tie sākotnēji tika ievadīti.

Zinot šīs smalkās atšķirības, var būt noderīgi izlemt, kāda veida datu struktūru vēlaties atlasīt. Gan kopas, gan saraksti ir noderīgi, taču, tā kā tie darbojas atšķirīgi, dažās situācijās tie būs noderīgāki nekā citās. Pārliecināties, ka saraksts vai kopa ir vispiemērotākais situācijai, ir gudrs un noderīgs triks!

Secinājums

Šajā rakstā tika sniegts īss pārskats par sarakstiem un kopām dažādās valodās. Tika apspriestas abu stiprās un vājās puses, kā arī dažas interesantas atziņas par to darbību. Cerams, ka par tiem padomāsiet nākamreiz, kad plānojat uzglabāt datus!

Šajā rakstā izpētiīām divas ļoti svarīgas un noderīgas datu struktūras, sarakstus un kopas, kā arī uzzinājāt par abu stiprajām un vājajām pusēm. Tagad jums vajadzētu labāk izprast, kad katru izmantot, atkarībā no risinājuma uzglabāšanas vajadzībām.

Loading

Noderīgs raksts? Dalies ar citiem: