Masyvas programavime: kas tai, indeksai, tipai ir dydis

Sužinokite viską apie masyvus programavime: kas tai, indeksai, tipai, dydžio valdymas ir praktiški pavyzdžiai pradedantiesiems.

Programavimo kalbose masyvas yra kelių elementų (pvz., sveikųjų skaičių) saugojimo būdas. Šie elementai paprastai yra to paties tipo (pvz., tik sveikieji skaičiai, tik eilutės ir pan.), nes daugelyje griežtai tipizuotų kalbų masyve negalima saugoti skirtingų tipų elementų. Kiekvienas masyvo elementas turi numerį, todėl programuotojas gali gauti elementą naudodamas šį numerį. Šis skaičius vadinamas indeksu. Kai kuriose programavimo kalbose pirmasis elementas turi indeksą 0, antrasis — indeksą 1 ir t. t., o kitose kalbose pirmasis elementas turi indeksą 1 (tada 2, 3, ...).

Kurdamas masyvą programuotojas dažnai turi nurodyti jo dydį — tai yra elementų, kuriuos galima saugoti masyve, skaičius. Tradiciniuose (statiniuose) masyvuose dydžio vėliau pakeisti negalima; jei reikia daugiau vietos, sukuriamas naujas masyvas arba naudojami dinamiški duomenų konteineriai.

Indeksavimo konvencijos

• 0-based indeksavimas (pirmas elementas — 0): naudojamas daugelyje kalbų, pvz., C, C++, Java, JavaScript, Python.
• 1-based indeksavimas (pirmas elementas — 1): naudojamas tam tikrose kalbose ir aplinkose, pvz., MATLAB, Fortran (pagal numatytąsias konvencijas kai kuriose versijose).
• Svarbu žinoti, kuri konvencija taikoma konkrečioje kalboje, kad nekiltų „off-by-one“ klaidų (klaidos dėl neteisingo indekso skaičiavimo).

Atminties išdėstymas ir našumas

• Tradiciniai masyvai paprastai saugomi nuosekliai (contiguous) atmintyje. Todėl prieiga prie elemento pagal indeksą yra labai greita — tiesioginis adresų skaičiavimas, dažnai O(1).
• Įterpti arba ištrinti elementą masyvo viduryje reikalauja perkelti kitus elementus, todėl tokios operacijos paprastai yra O(n).
• Dinamiški masyvai (pvz., C++ std::vector, Java ArrayList) dažnai automatiškai plečiasi, kopijuodami duomenis į didesnį bloką; papildymo amortizuotas sudėtingumas dažnai būna O(1).

Tipai ir rūšys

• Statiniai masyvai: dydis nustatomas deklaracijos metu ir vėliau nekeičiama (pvz., C masyvai deklaruojami kaip int a[10]).
• Dinamiški (plečiami) masyvai: galima keisti dydį vykdymo metu; pavyzdžiai — vector, ArrayList, Python list.
• Homogeniškumas: daugelyje tipizuotų kalbų masyvo elementai turi būti vienodo tipo. Tačiau dinamiškai tipizuotose kalbose (pvz., Python, JavaScript) masyvai (sąrašai) gali laikyti skirtingų tipų reikšmes.
• Daugiamatčiai masyvai: masyvo elementai patys gali būti masyvai — taip gaunami dvimačiai (matricos) ar aukštesnės dimensijos duomenų rinkiniai.

Daugiamatčiai masyvai ir tvarkos tipai

• 2D masyvas paprastai interpretuojamas kaip eilučių ir stulpelių rinkinys. Pvz., int m[3][4] turi 3 eilutes ir 4 stulpelius.
• Atmintyje daugiamačiai masyvai gali būti išdėstyti eilėmis (row-major) arba stulpeliais (column-major). C/C++ naudoja row-major, Fortran — column-major. Tai svarbu skaičiavimams ir optimizacijai (cache efektyvumas).

Pagrindinės operacijos

• Prieiga prie elemento pagal indeksą — O(1).
• Eilinis paieška (search) — O(n), jei nenaudojamos papildomos struktūros ar raktai.
• Iteravimas per visus elementus — O(n).
• Įterpimas/ištrynimas viduryje — O(n) (reikia perstumti likusius elementus).
• Pridedant pabaigoje dinamiškam masyvui — amortizuotas O(1), tačiau vienkartiniai perpildymai gali kainuoti O(n).

Masyvai C kalboje

• C kalboje masyvas diagnozuojamas kaip nuosekli atminties zona: deklaracija int a[10] rezervuoja vietą 10 sveikųjų skaičių.
• Masyvo pavadinimas dažnai verčiamas į nuorodą į pirmą elementą (nors tipai skiriasi), todėl galima naudoti rodyklių ar pointerio aritmetiką: a[i] yra ekvivalentu *(a + i).
• Jei dydis nežinomas vykdymo metu, galima naudoti dinaminę atmintį su malloc/free arba C++ new/delete / std::vector. Svarbu valdyti atmintį ir išvengti perpildymo klaidų.
• Naudojant sizeof galima apskaičiuoti masyvo dydį atmintyje (pvz., sizeof(a) / sizeof(a[0]) duoda elementų skaičių statiniame masyve), bet tai neveikia, jei masyvas paduodamas į funkciją kaip rodyklė.

Praktinės pastabos

• Renkantis tarp masyvo ir kitos struktūros (sąrašo, vektoriaus, nuorodų sąrašo) atsižvelkite į dažniausias operacijas: jei reikia greitos prieigos pagal indeksą — masyvas tinkamas; jei reikia daug įterpimų/ištrynimų viduryje — gal verta rinktis sąrašą.
• Naudokite biblioteką teikiamus dinaminio dydžio konteinerius, kai reikia saugiau arba patogiau valdyti atmintį (pvz., Java ArrayList, C++ std::vector, Python list).
• Visada patikrinkite indeksų ribas, kad išvengtumėte „out-of-bounds“ klaidų, kurios gali sukelti programos gedimą arba saugumo spragas.

Santrauka: masyvas yra paprasta ir efektyvi duomenų laikymo struktūra, leidžianti greitai pasiekti elementus pagal indeksą. Tačiau reikia atsižvelgti į dydžio, atminties išdėstymo ir kalbos specifikų ypatumus, ypač dirbant su statiniais C masyvais arba dinaminiais konteineriais aukštesnio lygio kalbose.

Klausimai ir atsakymai

K: Kas yra masyvas programavimo kalbose?

K: Kokio tipo elementus galima saugoti masyve?

K: Kas yra indeksas masyve?

K: Kaip nustatomas pirmojo masyvo elemento indeksas?

K: Ką programuotojas turi nurodyti kurdamas masyvą?

K: Kodėl negalima keisti masyvo dydžio?

Klausimas: Ką turi daryti programuotojas, jei nori saugoti daugiau elementų, nei leidžia masyvo dydis?

Paieška pagal raidę