Array (massiv)

Array — bir nechta qiymatni tartibli va bir-biriga bog‘langan holda saqlash uchun ishlatiladigan ma’lumotlar tuzilmasi. Dasturlashda bir xil ma’noga ega ko‘p qiymatlar bilan ishlash kerak bo‘lganda, har biri uchun alohida o‘zgaruvchi yaratish o‘rniga ularni bitta array ichiga joylaymiz.

Masalan, yetti kunlik havo haroratini saqlashimiz kerak bo‘lsin. Buning uchun harorat_1, harorat_2, harorat_3 kabi yettita alohida o‘zgaruvchi yaratish mumkin. Lekin kunlar soni yuzta yoki millionta bo‘lsa, bu usul bilan ishlashning iloji qolmaydi. Array esa barcha qiymatlarni bitta nom ostida tartib bilan saqlaydi:

haroratlar = [18, 20, 23, 22, 19, 17, 16]

Bu yerda array shunchaki qiymatlar to‘plami emas. Undagi har bir qiymatning o‘z o‘rni bor va shu o‘rin orqali kerakli qiymatga murojaat qilinadi. Arrayni tushunish uchun aynan shu uchta tushunchani bir-biridan ajratib olish kerak:

• element — array ichida saqlanayotgan qiymat;
• index — elementning array ichidagi tartib raqami;
• length — array ichidagi elementlar soni.

Array ko‘plab boshqa ma’lumotlar tuzilmalari va algoritmlarning asosi hisoblanadi. Matritsa, satr, heap, hash table hamda ko‘plab qidirish va saralash algoritmlarini chuqur tushunish uchun avval array qanday ishlashini yaxshi bilish kerak.

Arrayni oddiy tasavvur qilish

Arrayni bir qatorga qurilgan, bir xil o‘lchamdagi raqamlangan uylar deb tasavvur qiling. Har bir uyda bittadan qiymat yashaydi:

Index:      0       1       2       3       4
          +-------+-------+-------+-------+-------+
Element:  |  12   |  25   |  7    |  40   |  18   |
          +-------+-------+-------+-------+-------+

Bu misolda arrayning uzunligi 5. Birinchi element 12, lekin uning indexi 0. Uchinchi element 7, uning indexi esa 2.

Ko‘pchilik dasturlash tillarida index 0 dan boshlanadi. Shu sababli uzunligi n bo‘lgan arrayning birinchi indexi 0, oxirgi indexi esa n - 1 bo‘ladi. Masalan, 5 ta elementli arrayda mavjud indexlar 0, 1, 2, 3, 4. 5-indexga murojaat qilish array chegarasidan tashqariga chiqish hisoblanadi.

Array xotirada qanday joylashadi?

Arrayning eng muhim xususiyati — klassik array elementlari xotirada yonma-yon, ya’ni uzluksiz joylashadi. Kompyuterning tezkor xotirasini juda ko‘p raqamlangan kataklardan iborat uzun yo‘lak deb tasavvur qilish mumkin. Har bir katakning o‘z manzili bor. Array yaratilganda tizim uning elementlari uchun ketma-ket keladigan xotira maydonini ajratadi.

Faraz qilaylik, arrayning birinchi elementi 1000-manzilda joylashgan va har bir element xotiradan 4 bayt joy egallaydi:

Index:             0         1         2         3
Xotira manzili:  1000      1004      1008      1012
                 +---------+---------+---------+---------+
Element:         |   12    |   25    |    7    |   40    |
                 +---------+---------+---------+---------+

Kompyuter istalgan element manzilini quyidagi mantiq orqali hisoblay oladi:

element manzili = boshlang‘ich manzil + (index × bitta element hajmi)

Masalan, 2-indexdagi element manzilini topish uchun:

1000 + (2 × 4) = 1008

Demak, kompyuter uchinchi elementni topish uchun birinchi va ikkinchi elementlarni ko‘rib chiqishi shart emas. U indexdan foydalanib kerakli manzilni to‘g‘ridan-to‘g‘ri hisoblaydi. Arrayning asosiy kuchi ham shunda.

Nega elementlar bir xil hajmda bo‘lishi kerak?

Yuqoridagi manzil formulasining ishlashi uchun kompyuter har bir element qancha joy egallashini oldindan bilishi kerak. Agar birinchi element 4 bayt, ikkinchisi 20 bayt, uchinchisi esa 7 bayt joy egallasa, faqat indexga qarab kerakli element manzilini hisoblab bo‘lmaydi. Undan oldingi elementlarning hajmini ham tekshirishga to‘g‘ri keladi.

Shu sababli klassik array odatda bir xil turdagi elementlarni saqlaydi. Bir xil turdagi elementlarning xotira hajmi ham bir xil bo‘ladi. Masalan, butun sonlar arrayi faqat butun sonlarni, belgilar arrayi esa faqat belgilarni saqlaydi.

Ba’zi dasturlash tillari bitta kolleksiya ichida turli turdagi qiymatlarni saqlashga ruxsat beradi. Tashqaridan u arrayga o‘xshab ko‘rinsa ham, ichki tuzilishi klassik arraydan farq qilishi mumkin: uning kataklarida qiymatlarning o‘zi emas, boshqa joydagi obyektlarga olib boruvchi bir xil hajmdagi manzillar saqlanishi mumkin. DSAda “array” deyilganda avvalo bir xil hajmli elementlar uzluksiz xotirada joylashgan klassik model nazarda tutiladi.

Nega index 0 dan boshlanadi?

0 dan boshlash shunchaki dasturchilar kelishib olgan g‘alati qoida emas. Indexni array boshlanishidan qancha masofa uzoqlikda turganlik deb tushunish mumkin.

• 0-index — boshlang‘ich manzildan 0 ta element uzoqda;
• 1-index — boshlang‘ich manzildan 1 ta element uzoqda;
• 2-index — boshlang‘ich manzildan 2 ta element uzoqda.

Shuning uchun birinchi element manzili boshlang‘ich manzil + (0 × element hajmi) bo‘ladi. Bu yondashuv manzilni hisoblashni sodda qiladi. Yuqori darajadagi tilda kod yozayotganda xotira manzillarini qo‘lda hisoblamaysiz, lekin arrayning tez ishlashi ortida aynan shu mexanizm turadi.

Arrayning asosiy xususiyatlari

Tartib saqlanadi

Arrayga elementlar qaysi tartibda joylashtirilgan bo‘lsa, shu tartib saqlanib qoladi. Ikkinchi element doim birinchi elementdan keyin, uchinchi element esa ikkinchisidan keyin turadi. Qiymatlar bir xil bo‘lishi mumkin, lekin ularning indexlari har xil bo‘ladi.

Har bir elementning indexi bor

Index orqali elementning array ichidagi o‘rnini aniq ko‘rsatish mumkin. “Qiymati 25 bo‘lgan element” deyish va “1-indexdagi element” deyish bir xil narsa emas. Qiymat takrorlanishi mumkin, index esa muayyan array ichidagi bitta joyni bildiradi.

Elementga to‘g‘ridan-to‘g‘ri kirish mumkin

Array boshlanish manzili va element hajmi ma’lum bo‘lgani sababli, kompyuter istalgan indexdagi elementni bevosita topadi. Birinchi elementni olish ham, millioninchi elementni olish ham bir xil miqdordagi manzil hisobini talab qiladi. Bu xususiyat random access, ya’ni ixtiyoriy elementga to‘g‘ridan-to‘g‘ri kirish deb ataladi.

Algoritmik murakkablik tilida index orqali elementni olish odatda O(1) vaqt oladi. Bu “mutlaqo nol vaqt” degani emas. Bu array kattalashgani sari bitta elementga index orqali kirish uchun bajariladigan ish miqdori ortmaydi deganidir.

Klassik arrayning o‘lchami aniq bo‘ladi

Array uchun xotiradan uzluksiz joy ajratish kerak. Tizim qancha joy ajratishni bilishi uchun elementlar soni odatda array yaratilayotgan paytda ma’lum bo‘ladi. Masalan, 100 ta elementning har biri 4 baytdan bo‘lsa, array uchun kamida 400 bayt uzluksiz joy kerak.

Klassik, fixed-size array yaratilgandan so‘ng uning uzunligini o‘zgartirib bo‘lmaydi. Bu array ichidagi qiymatni almashtirib bo‘lmaydi degani emas. Elementlar o‘zgarishi mumkin, lekin ajratilgan kataklar soni o‘zgarmaydi.

Uzunlik o‘zgarmaydi: [12, 25, 7, 40]
Qiymat o‘zgarishi mumkin: [12, 25, 99, 40]

Arrayning chegarasi bor

Uzunligi 4 bo‘lgan arrayda faqat 0 dan 3 gacha indexlar mavjud. Manfiy yoki mavjud bo‘lmagan indexga murojaat qilish chegaradan tashqariga chiqish deyiladi. Bunday holatda ayrim tillar xato qaytaradi, ayrim past darajali tillarda esa begona xotirani o‘qish yoki dastur ishdan chiqishi mumkin. Til qanday munosabat bildirishidan qat’i nazar, algoritm nuqtayi nazaridan bunday murojaat noto‘g‘ri hisoblanadi.

Fixed-size array va dynamic array bir xil emas

Amaliy dasturlashda “array” deb ataladigan barcha tuzilmalar ham qat’iy o‘lchamli emas. Ko‘p tillarda element qo‘shilganda o‘zi kattalashadigan qulay kolleksiya mavjud. U dynamic array deb ataladi; ayrim tillarda uning nomi list, vector yoki boshqa ko‘rinishda bo‘lishi mumkin.

Dynamic array sehrli tarzda mavjud xotirani cho‘zmaydi. Odatda uning ichida klassik array ishlaydi. Joy tugaganda u quyidagicha ishlaydi:

1. kattaroq yangi array uchun xotira ajratadi;
2. eski elementlarni yangi joyga ko‘chiradi;
3. eski xotirani bo‘shatadi;
4. yangi elementni qo‘shadi.

Shuning uchun tashqaridan o‘lchami bemalol o‘zgarayotgandek ko‘rinsa ham, ichkarida ma’lum sig‘imga ega array mavjud bo‘ladi. Bu yerda ikkita tushunchani farqlash muhim:

• length — hozir nechta element borligi;
• capacity — qayta joy ajratmasdan nechta element saqlash mumkinligi.

Masalan, dynamic arrayning length qiymati 5, capacity qiymati esa 8 bo‘lishi mumkin. Demak, unda 5 ta element bor, lekin ajratilgan xotirada yana 3 ta bo‘sh katak mavjud.

Tilga bog‘liq nomlarni yodlashdan ko‘ra, ishlatilayotgan kolleksiya haqiqiy fixed-size arraymi yoki array ustiga qurilgan dynamic tuzilmami, shuni aniqlash muhim. Keyingi algoritmik qarorlar aynan shu farqqa bog‘liq bo‘ladi.

Arrayning afzalliklari

• Index orqali elementga juda tez kirish mumkin.
• Elementlar tartibli saqlanadi.
• Xotirada yonma-yon joylashgani uchun protsessor ularni ketma-ket o‘qishda samarali ishlaydi.
• Tuzilishi sodda va ko‘plab algoritmlar uchun qulay.
• Boshqa murakkab ma’lumotlar tuzilmalarini qurish uchun asos bo‘lib xizmat qiladi.

Yonma-yon joylashish faqat manzil hisoblashga emas, amaliy tezlikka ham yordam beradi. Protsessor xotiradan bitta qiymatni olayotganda uning yonidagi ma’lumotlarni ham tezkor keshiga yuklashi mumkin. Array bo‘ylab ketma-ket yurish shu sababli ko‘pincha xotiraning turli joylariga tarqalgan elementlar bo‘ylab yurishdan tezroq bo‘ladi.

Arrayning cheklovlari

• Fixed-size arrayning uzunligini yaratilgandan keyin o‘zgartirib bo‘lmaydi.
• Boshiga yoki o‘rtasiga yangi element joylash uchun undan keyingi elementlarni surish kerak bo‘lishi mumkin.
• Elementni o‘rtadan olib tashlaganda hosil bo‘lgan bo‘shliqni yopish uchun ham elementlarni surishga to‘g‘ri keladi.
• Faqat qiymat ma’lum bo‘lsa, uning qayerdaligini topish uchun elementlarni birma-bir tekshirish kerak bo‘lishi mumkin.
• Oldindan ortiqcha joy ajratilsa xotira bekor turadi, kam joy ajratilsa yangi kattaroq array yaratish talab qilinadi.

Arrayning kuchli va zaif tomonlari bir xil sababdan kelib chiqadi: elementlar xotirada tartibli va yonma-yon joylashadi. Bu index orqali kirishni tezlashtiradi, lekin array o‘rtasidagi elementlarni siljitishni qimmat qiladi. Ma’lumotlar tuzilmasini tanlashda faqat uning afzalligini emas, qaysi amal evaziga bu afzallikka erishilganini ham tushunish kerak.

Array turlari va ular qayerda ishlatiladi?

Arraylar odatda ikki jihatdan tasniflanadi:

1. elementni topish uchun nechta index kerakligi — bir, ikki yoki ko‘p o‘lchamli array;
2. o‘lchami o‘zgarishi yoki o‘zgarmasligi — fixed-size yoki dynamic array.

Qaysi turni tanlash dasturlash tiliga emas, ma’lumotning tabiatiga bog‘liq. Agar ma’lumot bitta ketma-ketlik bo‘lsa bir o‘lchamli, qator va ustunlardan iborat bo‘lsa ikki o‘lchamli, bir nechta yo‘nalish yoki qatlamga ega bo‘lsa ko‘p o‘lchamli array mos keladi. Elementlar soni oldindan ma’lum bo‘lsa fixed-size, muntazam ortib-kamayib tursa dynamic array qulayroq bo‘ladi.

Bir o‘lchamli array — bitta ketma-ketlik

Bir o‘lchamli arraydagi elementni topish uchun bitta index yetarli. Uni bitta qator, navbat yoki vaqt bo‘yicha ketma-ket kelgan o‘lchovlar deb tasavvur qilish mumkin:

Index:       0    1    2    3    4
Harorat:    18   20   23   22   19

Bir o‘lchamli array quyidagi holatlarda mos keladi:

• ma’lumot bitta tartibli ro‘yxatdan iborat bo‘lsa;
• har bir elementning faqat ketma-ketlikdagi o‘rni muhim bo‘lsa;
• ma’lumot bo‘ylab boshidan oxirigacha yurish kerak bo‘lsa;
• elementga uning tartib raqami orqali tez kirish talab qilinsa.

Real misollar:

• Kunlik haroratlar. Ob-havo tizimi har soatda o‘lchangan haroratlarni arrayda saqlashi mumkin. Index vaqt oralig‘ini, element esa o‘sha paytdagi haroratni bildiradi.
• Audio yozuv. Raqamli ovoz juda qisqa vaqt oralig‘ida o‘lchangan signal qiymatlarining uzun ketma-ketligidir. Audio faylni qayta ishlashda uning ortida bir o‘lchamli sample’lar arrayi turadi.
• Sensor ma’lumotlari. Yurak urishi, serverning CPU yuklanishi yoki avtomobil tezligi kabi vaqt bo‘yicha yig‘ilgan o‘lchovlar bitta arrayda saqlanishi mumkin.
• Leaderboard. O‘yinchilar ball bo‘yicha saralanganda ularning natijalari tartibli array ko‘rinishida ifodalanishi mumkin.
• Qidiruv natijalari. Qidiruv tizimi topgan sahifalarni muhimlik tartibida bitta ketma-ketlik qilib qaytaradi.

Bu misollarning barchasida ma’lumotning tabiiy ko‘rinishi “birinchi, ikkinchi, uchinchi...” tarzidagi bitta ketma-ketlik bo‘lgani uchun bir o‘lchamli array ishlatiladi.

Ikki o‘lchamli array — qator va ustunlar

Ikki o‘lchamli array jadval yoki to‘r ko‘rinishidagi ma’lumotni ifodalaydi. Elementni topish uchun ikkita index: qator va ustun kerak bo‘ladi.

             Ustun
              0   1   2
            +---+---+---+
Qator 0     | 1 | 2 | 3 |
Qator 1     | 4 | 5 | 6 |
Qator 2     | 7 | 8 | 9 |
            +---+---+---+

Agar indexlar 0 dan boshlansa, 1-qator va 2-ustundagi element 6 bo‘ladi. Bu yerda bittagina 2 indexi yetarli emas, chunki 2-qator va 2-ustun turli narsalarni anglatadi.

Ikki o‘lchamli array quyidagi holatlarda mos keladi:

• ma’lumot qator va ustunlardan tashkil topgan bo‘lsa;
• elementning gorizontal va vertikal joylashuvi ma’noga ega bo‘lsa;
• qo‘shni kataklar bilan ishlash talab qilinsa;
• jadval, xarita yoki matritsa ustida hisob-kitob bajarilsa.

Real misollar:

• Raqamli rasm. Ekrandagi oddiy qora-oq rasm piksellar jadvalidir. Birinchi index pikselning qatorini, ikkinchisi ustunini ko‘rsatadi. Har bir element o‘sha piksel yorqinligini saqlaydi.
• Shaxmat taxtasi. Taxta 8 qator va 8 ustundan iborat. Har bir katak bo‘sh yoki unda ma’lum dona turishi mumkin. taxta[qator][ustun] mantiqi istalgan katakni aniq ko‘rsatadi.
• Elektron jadval. Spreadsheet ichidagi kataklar qator va ustun bo‘yicha joylashgan. Har bir katak qiymatini ikki o‘lchamli array elementi sifatida tasavvur qilish mumkin.
• O‘yin xaritasi. Ikki o‘lchamli o‘yinda har bir katak yo‘l, devor, suv yoki raqibni ifodalashi mumkin. Yo‘l topish algoritmi aynan shu to‘r bo‘ylab harakatlanadi.
• Kinoteatr o‘rindiqlari. Birinchi index qatorni, ikkinchisi shu qatordagi o‘rindiqni bildiradi. Element esa o‘rindiq bo‘sh yoki band ekanini saqlaydi.
• Matematik matritsa. Grafik transformatsiya, sun’iy intellekt va ilmiy hisoblarda sonlar qator va ustun ko‘rinishida saqlanadi.

Ikki o‘lchamli arrayni “array ichidagi array” deb ko‘rish mumkin, lekin uning xotirada aynan qanday saqlanishi til va tizimga bog‘liq. Ayrim hollarda barcha elementlar bitta uzluksiz xotira blokida, ayrim hollarda esa har bir qator alohida joyda saqlanadi. Algoritmik modelda esa biz uni qator va ustunli jadval sifatida ko‘ramiz.

Uch o‘lchamli array — qator, ustun va qatlam

Uch o‘lchamli arraydagi elementni topish uchun uchta index kerak. Uni bir nechta ikki o‘lchamli jadvallar ustma-ust joylashtirilgan holat deb tasavvur qilish mumkin:

element = array[qatlam][qator][ustun]

Uch o‘lchamli array quyidagi holatlarda mos keladi:

• ma’lumot qator va ustundan tashqari yana bir qatlamga ega bo‘lsa;
• fazodagi hajmni mayda kataklarga ajratib saqlash kerak bo‘lsa;
• bir xil jadvallarning bir nechta nusxasi bilan ishlansa.

Real misollar:

• Rangli rasm. Rangli piksel odatda qizil, yashil va ko‘k kanallardan iborat. Bunday tasvirni rasm[qator][ustun][kanal] ko‘rinishida tasavvur qilish mumkin. Uchinchi index qaysi rang kanali ekanini bildiradi.
• Tibbiy tasvir. MRT yoki KT qurilmasi inson tanasining ko‘plab kesimlarini oladi. Har bir kesim ikki o‘lchamli rasm, kesimlar birlashtirilganda esa tananing uch o‘lchamli modeli hosil bo‘ladi.
• Minecraftga o‘xshash dunyo. Har bir blokning kenglik, balandlik va chuqurlik bo‘yicha koordinatasi bor. Array elementi o‘sha joyda havo, tuproq, tosh yoki suv borligini bildirishi mumkin.
• Bino harorati. Ko‘p qavatli binoda sensor qiymatini qavat, qator va xona bo‘yicha saqlash mumkin.

Uch o‘lchamli array har doim real fazoni anglatmaydi. Uchinchi index shunchaki ma’lumotning yana bir mustaqil xususiyatini, masalan rang kanali yoki vaqt kesimini ham bildirishi mumkin.

To‘rt va undan ko‘p o‘lchamli arraylar

O‘lchamlar soni uchtadan ham ko‘p bo‘lishi mumkin. Bunday arrayni ko‘z oldiga keltirish qiyin, lekin uning mantiqi o‘zgarmaydi: har bir qo‘shimcha index ma’lumotga yana bitta yo‘nalish yoki belgi qo‘shadi.

Masalan, bir nechta rangli rasmlar to‘plami quyidagicha ifodalanishi mumkin:

rasmlar[rasm_raqami][qator][ustun][rang_kanali]

Bu to‘rt o‘lchamning ma’nosi:

1. qaysi rasm;
2. rasmdagi qaysi qator;
3. qaysi ustun;
4. qaysi rang kanali.

Real misollar:

• Video. Video vaqt bo‘yicha ketma-ket kelgan rangli rasmlardir. Uni video[kadr][qator][ustun][rang_kanali] ko‘rinishida tasavvur qilish mumkin.
• Sun’iy intellekt. Neyron tarmoqqa bir vaqtning o‘zida ko‘plab rasmlar uzatilganda ma’lumot rasmlar_soni × balandlik × kenglik × kanallar shaklidagi arrayda saqlanishi mumkin.
• Ob-havo modeli. Harorat vaqt, balandlik, geografik kenglik va uzunlik bo‘yicha o‘zgarishi mumkin. Har bir o‘lcham alohida index bilan ifodalanadi.

Ko‘p o‘lchamli array tanlashdan oldin har bir index nimani anglatishini aniq ayta olish kerak. Agar indexlarning ma’nosi tushunarsiz bo‘lsa, tuzilma ham tezda chalkashib ketadi.

Fixed-size array qachon ishlatiladi?

Fixed-size array elementlar soni oldindan aniq va kamdan-kam o‘zgaradigan holatlarda eng yaxshi tanlov bo‘lishi mumkin:

• haftaning 7 kuni;
• shaxmat taxtasining 64 katagi;
• bir baytdagi 8 bit;
• yilning 12 oyi bo‘yicha hisobot;
• qurilmadagi o‘zgarmas miqdordagi sensorlar;
• algoritm ishlashi davomida o‘lchami o‘zgarmaydigan bufer.

Masalan, svetofor boshqaruvchisida aynan uchta chiroq holati kuzatilsa, buning uchun cheksiz kattalasha oladigan kolleksiya kerak emas. O‘lchami uchta bo‘lgan fixed-size array sodda va xotira sarfi oldindan ma’lum bo‘ladi.

Fixed-size arrayning maqsadi faqat xotirani tejash emas. O‘lchamning o‘zgarmasligi tizimga aniq kafolat beradi: elementlar soni tasodifan ortib yoki kamayib ketmaydi.

Dynamic array qachon ishlatiladi?

Dynamic array elementlar soni oldindan noma’lum yoki ish jarayonida o‘zgarib turadigan holatlarda qulay:

• foydalanuvchi savatiga qo‘shilgan mahsulotlar;
• ijtimoiy tarmoqdagi izohlar;
• serverga kelayotgan so‘rovlar ro‘yxati;
• qidiruvdan topilgan natijalar;
• fayldan o‘qilayotgan, satrlar soni noma’lum ma’lumot;
• o‘yinda paydo bo‘lib va yo‘qolib turadigan obyektlar.

Masalan, internet-do‘konda foydalanuvchi savatga nechta mahsulot qo‘shishini oldindan bilib bo‘lmaydi. Shu sababli savat uchun fixed-size array tanlansa, joy yetmay qolishi yoki juda ko‘p bo‘sh xotira ajratilishi mumkin. Dynamic array esa ehtiyojga qarab o‘sadi.

Dynamic array qulay bo‘lsa ham, har qanday holatda avtomatik ravishda eng yaxshi tanlov emas. U sig‘imi tugaganda yangi joy ajratishi va elementlarni ko‘chirishi kerak. Elementlar soni oldindan aniq bo‘lsa, kerakli o‘lchamni birdan ajratish ortiqcha ko‘chirishlarning oldini oladi.

Qaysi array turini tanlash kerak?

Tanlashdan oldin quyidagi savollarni bering:

1. Ma’lumot nechta yo‘nalishga ega? Bitta ketma-ketlik uchun 1D, jadval uchun 2D, qatlamli ma’lumot uchun 3D yoki undan ko‘p o‘lcham kerak.
2. Har bir indexning ma’nosi nima? Masalan, vaqt, qator, ustun, rang kanali yoki qavat.
3. Elementlar soni oldindan ma’lummi? Ma’lum bo‘lsa fixed-size, noma’lum va o‘zgaruvchan bo‘lsa dynamic array ko‘rib chiqiladi.
4. Qaysi amal ko‘p bajariladi? Index orqali o‘qish ko‘p bo‘lsa array juda qulay. O‘rtaga tez-tez element qo‘shish va o‘chirish kerak bo‘lsa boshqa ma’lumotlar tuzilmasi yaxshiroq bo‘lishi mumkin.

Masalan, shaxmat taxtasi uchun 8 × 8 fixed-size ikki o‘lchamli array tabiiy tanlov: qator va ustunlar soni aniq, kataklarning joylashuvi o‘zgarmaydi va istalgan katakka tez murojaat qilish kerak. Ijtimoiy tarmoq izohlari esa bitta ketma-ketlik, ammo ularning soni oldindan noma’lum; shu sababli bir o‘lchamli dynamic array ko‘proq mos keladi.

Array ustidagi asosiy amallar

Ma’lumotlar tuzilmasini bilish faqat uning ta’rifini yodlash degani emas. Uni ishlatishda qaysi amal tez, qaysi amal sekin va nima sababdan shunday ekanini tushunish kerak. Array ustida odatda quyidagi amallar bajariladi:

• index orqali elementni o‘qish;
• element qiymatini o‘zgartirish;
• barcha elementlarni birma-bir ko‘rib chiqish;
• kerakli qiymatni qidirish;
• yangi element qo‘shish;
• mavjud elementni o‘chirish.

Bu amallarning narxi bir xil emas. Arrayning xotirada yonma-yon joylashishi ba’zi amallarni juda tez bajarishga yordam beradi, lekin ayrim amallarda ko‘plab elementlarni siljitishga majbur qiladi.

Keyingi misollarda aniq bir dasturlash tili sintaksisi ishlatilmaydi. ARRAY, FOR, IF, RETURN kabi yozuvlar algoritmning umumiy mantiqini ko‘rsatadigan pseudocode hisoblanadi. Uni tushungan odam shu algoritmni istalgan dasturlash tilida yozishi mumkin.

Elementni index orqali o‘qish

Arraydagi elementning indexi ma’lum bo‘lsa, unga to‘g‘ridan-to‘g‘ri murojaat qilish mumkin:

sonlar = [14, 27, 8, 35, 19]

sonlar[0] → 14
sonlar[2] → 8
sonlar[4] → 19

Kompyuter sonlar[2]ni olish uchun 14 va 27ni tekshirib o‘tirmaydi. Boshlang‘ich manzil, index va element hajmidan foydalanib kerakli xotira manzilini hisoblaydi. Shu sababli array boshidagi, o‘rtasidagi yoki oxiridagi elementni olish bir xil miqdordagi ishni talab qiladi.

Index orqali elementni o‘qishning vaqt murakkabligi:

O(1)

Real misol sifatida haftaning har bir kuni uchun savdo miqdori saqlangan arrayni olaylik. Chorshanba 2-indexga mos kelishi oldindan ma’lum bo‘lsa, aynan shu kun natijasini boshqa kunlarni ko‘rmasdan olish mumkin.

Element qiymatini o‘zgartirish

Element indexi ma’lum bo‘lsa, uning eski qiymatini yangi qiymat bilan almashtirish ham to‘g‘ridan-to‘g‘ri amalga oshiriladi:

sonlar = [14, 27, 8, 35, 19]

sonlar[2] = 10

natija: [14, 27, 10, 35, 19]

Arrayning uzunligi o‘zgarmadi va hech bir element siljitilmadi. Faqat 2-indexdagi xotira katagiga yangi qiymat yozildi. Shu sababli elementni index orqali o‘zgartirish ham O(1) vaqt oladi.

Bu amal real tizimlarda juda ko‘p uchraydi. Masalan, kinoteatr o‘rindiqlari ikki o‘lchamli arrayda saqlansa, foydalanuvchi chipta sotib olganida tegishli katakning qiymati bo‘sh holatidan band holatiga o‘zgartiriladi. Taxtaning qolgan kataklariga tegish shart emas.

Array bo‘ylab yurish — traversal

Ba’zan bitta elementning indexi ma’lum bo‘ladi. Ba’zan esa barcha elementlarni ko‘rib chiqish kerak. Arrayning boshidan oxirigacha har bir elementga bir marta murojaat qilish traversal deb ataladi.

FOR index = 0 DAN array uzunligi - 1 GACHA
    array[index] BILAN ISHLA

Masalan, barcha sonlarni ekranga chiqarish:

sonlar = [14, 27, 8, 35, 19]

14
27
8
35
19

Arrayda n ta element bo‘lsa, traversal ularning har biriga bir martadan murojaat qiladi. Demak, bajariladigan ish elementlar soni bilan birga ortadi:

O(n)

Traversal quyidagi vazifalarning asosi hisoblanadi:

• barcha qiymatlar yig‘indisini hisoblash;
• o‘rtacha qiymatni topish;
• eng katta yoki eng kichik elementni aniqlash;
• ma’lum shartga mos elementlarni sanash;
• barcha elementlarni o‘zgartirish;
• kerakli qiymatni qidirish.

Array elementlari yig‘indisini topish

Yig‘indini saqlash uchun summa nomli o‘zgaruvchi kerak bo‘ladi. Dastlab uning qiymati 0. Array bo‘ylab yurganimizda har bir elementni unga qo‘shib boramiz:

summa = 0

FOR har bir element array ichida
    summa = summa + element

RETURN summa

[4, 7, 2, 9] arrayi uchun jarayon quyidagicha kechadi:

Boshlanish: summa = 0
4 dan keyin: summa = 4
7 dan keyin: summa = 11
2 dan keyin: summa = 13
9 dan keyin: summa = 22

Har bir element bir marta ko‘rilgani uchun vaqt murakkabligi O(n). Arraydan tashqari faqat bitta summa o‘zgaruvchisi ishlatilgani sabab qo‘shimcha xotira murakkabligi O(1) bo‘ladi.

Eng katta elementni topish

Eng katta elementni topishda boshlang‘ich qiymat sifatida arrayning birinchi elementini olish kerak:

eng_katta = array[0]

FOR index = 1 DAN array uzunligi - 1 GACHA
    IF array[index] > eng_katta
        eng_katta = array[index]

RETURN eng_katta

eng_katta = 0 deb boshlash xato bo‘lishi mumkin. Agar arraydagi barcha sonlar manfiy bo‘lsa, 0 arrayda yo‘q bo‘lsa ham natija bo‘lib qoladi. Birinchi elementdan boshlash algoritmni musbat va manfiy sonlar uchun bir xil ishlatish imkonini beradi.

Arraydan qiymat qidirish

Index orqali olish va qiymat bo‘yicha qidirish bir xil amal emas. 3-indexdagi element kerak bo‘lsa, uning manzili to‘g‘ridan-to‘g‘ri hisoblanadi. Ammo qiymati 35 bo‘lgan elementning qayerdaligi noma’lum bo‘lsa, uni topish uchun qidiruv algoritmi kerak.

Qaysi qidiruv ishlatilishi arrayning saralangan yoki saralanmaganiga bog‘liq.

Linear search — ketma-ket qidiruv

Saralanmagan arrayda kerakli qiymat istalgan joyda bo‘lishi mumkin. Eng sodda va ishonchli usul elementlarni boshidan boshlab birma-bir tekshirishdir:

FUNCTION qidir(array, kerakli_qiymat)
    FOR index = 0 DAN array uzunligi - 1 GACHA
        IF array[index] = kerakli_qiymat
            RETURN index

    RETURN topilmadi

[14, 27, 8, 35, 19] ichidan 35 qidirilsa, algoritm avval 14, keyin 27, 8 va nihoyat 35ni tekshiradi. Qiymat topilganda uning indexi qaytariladi.

Eng yaxshi holatda kerakli element array boshida turadi va bitta tekshiruv yetadi — O(1). Eng yomon holatda element array oxirida bo‘ladi yoki umuman mavjud bo‘lmaydi. Bunda barcha n ta element tekshiriladi — O(n). Big O tahlilida odatda eng yomon holat hisobga olingani uchun linear search murakkabligi O(n) deyiladi.

Linear search quyidagi holatlarda mos keladi:

• array saralanmagan bo‘lsa;
• array kichik bo‘lsa;
• qidiruv kamdan-kam bajarilsa;
• ma’lumotni avval saralash foyda bermasa.

Masalan, kichik guruhdagi talabalar identifikatorlari tartibsiz saqlangan bo‘lsa, kerakli talabani linear search bilan topish mumkin.

Binary search — oraliqni yarmiga kamaytirib qidirish

Array saralangan bo‘lsa, qidiruvni ancha tez bajarish mumkin. Binary search har safar arrayning o‘rtasidagi elementni tekshiradi va qidiruv maydonining yarmini tashlab yuboradi.

Masalan, quyidagi saralangan arraydan 31ni qidiramiz:

[3, 8, 12, 17, 24, 31, 42, 56]

1. O‘rtadagi qiymat tekshiriladi.
2. Kerakli qiymat kattaroq bo‘lsa chap yarmi, kichikroq bo‘lsa o‘ng yarmi tashlab yuboriladi.
3. Qolgan qismda shu jarayon takrorlanadi.

Har qadamda qidiriladigan elementlar soni ikki baravar kamayadi:

n → n/2 → n/4 → n/8 → ... → 1

Shu sababli binary searchning vaqt murakkabligi O(log n) bo‘ladi. Millionta element orasida linear search eng yomon holatda millionta tekshiruv bajarishi mumkin. Binary search esa taxminan yigirmata qadamda javobga yaqinlashadi.

Lekin uning muhim sharti bor: array saralangan bo‘lishi kerak. Saralanmagan arrayda qaysi yarmini tashlab yuborish mumkinligini aniqlab bo‘lmaydi.

Binary search quyidagi holatlarda foydali:

• ma’lumot allaqachon saralangan bo‘lsa;
• bitta array ustida juda ko‘p qidiruv bajarilsa;
• elementga index orqali kirish imkoniyati mavjud bo‘lsa.

Masalan, alifbo tartibida saqlangan katta lug‘atdan so‘z qidirishda har bir so‘zni boshidan tekshirish o‘rniga binary search ishlatish mumkin.

Arrayga element qo‘shish

Arrayga element qo‘shish narxi element qayerga joylashtirilishiga bog‘liq. Bo‘sh joy mavjud deb faraz qilsak ham, boshiga, o‘rtasiga va oxiriga qo‘shish bir xil amal emas.

Array oxiriga qo‘shish

Dynamic arrayda bo‘sh sig‘im bo‘lsa, yangi element keyingi bo‘sh katakka yoziladi:

Oldin:  [10, 20, 30, _]
Keyin:  [10, 20, 30, 40]

Hech bir eski element siljitilmaydi. Bo‘sh joy mavjud holatda oxiriga qo‘shish O(1) vaqt oladi.

Ammo capacity to‘lib qolgan bo‘lsa, kattaroq xotira maydoni ajratiladi va barcha eski elementlar unga ko‘chiriladi:

Eski joy:  [10, 20, 30, 40]
Yangi joy: [10, 20, 30, 40, 50, _, _, _]

Bunday alohida kengaytirish amali O(n) vaqt oladi. Lekin dynamic array odatda har safar bittadan emas, kattaroq zaxira bilan kengayadi. Shu sababli ko‘p marta oxiriga element qo‘shish hisoblanganda bitta qo‘shishning o‘rtacha narxi amortized O(1) deb qaraladi.

Amortized degani har bir qo‘shish aynan O(1) degani emas. Ba’zi qo‘shishlar qimmat bo‘ladi, lekin ular kamdan-kam sodir bo‘lgani uchun umumiy xarajat ko‘plab arzon qo‘shishlar orasida taqsimlanadi.

Array boshiga qo‘shish

Array boshidagi 0-index band bo‘lsa, yangi element uchun joy ochish maqsadida barcha mavjud elementlarni bir katak o‘ngga surish kerak:

Oldin:            [10, 20, 30, 40, _]
O‘ngga surish:    [_, 10, 20, 30, 40]
Yangi element:    [5, 10, 20, 30, 40]

Arrayda n ta element bo‘lsa, ularning barchasi siljitiladi. Shu sababli boshiga qo‘shish O(n) vaqt oladi.

Array o‘rtasiga qo‘shish

Yangi element k-indexga qo‘shilsa, k-indexdan boshlab oxirigacha bo‘lgan elementlar bir katak o‘ngga suriladi:

Oldin:                   [10, 20, 30, 40, _]
2-indexga 25 qo‘shish:   [10, 20, 25, 30, 40]

30 va 40 o‘ngga ko‘chirildi. Qo‘shish joyi array boshiga qancha yaqin bo‘lsa, shuncha ko‘p element siljiydi. Eng yomon holatda vaqt murakkabligi O(n) bo‘ladi.

Real misol sifatida tartib bilan turgan navbatni tasavvur qiling. Yangi odam navbat oxiriga kelsa, boshqalar joyidan qimirlamaydi. U navbat o‘rtasiga kirsa, undan keyingi barcha odamlar bir qadam surilishi kerak. Arrayga qo‘shish ham xuddi shu mantiqda ishlaydi.

Arraydan element o‘chirish

O‘chirishda faqat qiymatni yo‘q qilish yetarli emas. Array tartibli va bo‘shliqsiz qolishi kerak bo‘lsa, o‘chirilgan elementdan keyingi qiymatlar chapga suriladi.

Array oxiridan o‘chirish

Oxirgi element olib tashlansa, boshqa elementlarni siljitish shart emas:

Oldin:  [10, 20, 30, 40]
Keyin:  [10, 20, 30, _]

Dynamic array uchun oxiridan o‘chirish odatda O(1) vaqt oladi.

Array boshidan o‘chirish

Birinchi element o‘chirilsa, qolgan barcha elementlar chapga suriladi:

Oldin:          [10, 20, 30, 40]
10 o‘chirildi:  [20, 30, 40, _]

Bu amal O(n) vaqt oladi, chunki deyarli barcha elementlarning joyi o‘zgaradi.

Array o‘rtasidan o‘chirish

Masalan, 1-indexdagi 20 o‘chirilsa, undan keyingi elementlar bo‘shliqni yopish uchun chapga suriladi:

Oldin:          [10, 20, 30, 40]
20 o‘chirildi:  [10, 30, 40, _]

O‘rtadan o‘chirishning eng yomon holatdagi murakkabligi ham O(n).

Bu yerda yana bir muhim farq bor. Agar o‘chiriladigan elementning faqat qiymati ma’lum bo‘lsa, avval uni qidirish kerak. Saralanmagan arrayda qidirish O(n), topilgandan keyin elementlarni siljitish ham O(n) bo‘lishi mumkin. Ikkalasi ketma-ket bajarilganda O(n) + O(n) hosil bo‘ladi. Big O doimiy ko‘paytuvchilarni hisobga olmagani uchun umumiy murakkablik baribir O(n) bo‘lib qoladi.

Ikki o‘lchamli array bo‘ylab yurish

Ikki o‘lchamli arrayda har bir elementni ko‘rish uchun avval qatorlar, har bir qator ichida esa ustunlar bo‘ylab yuriladi. Buning uchun ichma-ich ikkita takrorlash ishlatiladi:

FOR har bir qator
    FOR shu qatordagi har bir ustun
        array[qator][ustun] BILAN ISHLA

Masalan:

[
  [1, 2, 3],
  [4, 5, 6]
]

Birinchi takrorlash 0-qatorni tanlaydi, ichki takrorlash 1, 2, 3 elementlarini ko‘radi. Keyin tashqi takrorlash 1-qatorga o‘tadi va ichki takrorlash 4, 5, 6ni ko‘radi.

Arrayda r ta qator va har bir qatorda c ta ustun bo‘lsa, jami r × c ta element mavjud. Barcha elementlarni ko‘rishning vaqt murakkabligi:

O(r × c)

Agar array kvadrat, ya’ni qator va ustunlar soni bir xil n bo‘lsa, bu murakkablik O(n²) deb yoziladi. Ichma-ich ikkita takrorlashni ko‘rib darhol O(n²) deb xulosa qilish to‘g‘ri emas. Murakkablik haqiqiy qator va ustunlar soniga bog‘liq.

Bu usul rasmning barcha piksellarini o‘zgartirish, o‘yin xaritasidagi to‘siqlarni topish yoki matritsa elementlari yig‘indisini hisoblashda ishlatiladi.

Asosiy amallarning vaqt murakkabligi

Quyidagi jadval array bilan ishlashdagi asosiy farqlarni umumlashtiradi:

Jadvaldagi qiymatlar umumiy, klassik array modeli uchun berilgan. Muayyan dasturlash tilining standart kutubxonasi ichki optimizatsiya yoki boshqa xatti-harakatga ega bo‘lishi mumkin. Lekin algoritm tanlashda shu model asos bo‘lib xizmat qiladi.

Array bilan ishlashdagi foydali yondashuvlar

Array masalalarining ko‘pi bir nechta asosiy yondashuvlarning turli ko‘rinishidan iborat. Hozir ularning ichki mantiqini bilish yetarli; keyingi mavzularda har birini alohida chuqur o‘rganish mumkin.

Ikki ko‘rsatkich — two pointers

Ba’zi masalalarda arrayning ikki joyini bir vaqtda kuzatish kerak bo‘ladi. Masalan, arrayni teskari aylantirishda bitta index boshidan, ikkinchisi oxiridan harakat qiladi:

chap = 0
o‘ng = array uzunligi - 1

WHILE chap < o‘ng
    array[chap] VA array[o‘ng] JOYINI ALMASHTIR
    chap = chap + 1
    o‘ng = o‘ng - 1

[10, 20, 30, 40]
 ↓           ↓
chap        o‘ng

natija: [40, 30, 20, 10]

Two pointers saralangan arraydan juftlik topish, bir xil elementlarni ajratish va arrayni joyida o‘zgartirish kabi masalalarda ko‘p ishlatiladi.

Sliding window — harakatlanuvchi oraliq

Ketma-ket joylashgan bir nechta element ustida hisoblash kerak bo‘lsa, har safar butun oraliqni boshidan hisoblash o‘rniga oldingi natijadan foydalanish mumkin.

Masalan, har uch kunlik savdo yig‘indisini topishda oynaning chap tomonidagi eski qiymat chiqarilib, o‘ng tomondagi yangi qiymat qo‘shiladi:

[5, 2, 7, 4, 6]
 └─────┘             birinchi 3 kun
    └─────┘          keyingi 3 kun
       └─────┘       keyingi 3 kun

Sliding window ketma-ket kunlar statistikasi, satr ichidagi bo‘laklar, trafik monitoringi va signal tahlilida ishlatiladi.

Prefix sum — oldindan hisoblangan yig‘indilar

Bitta arrayning turli oraliqlari yig‘indisi ko‘p marta so‘ralsa, har bir so‘rovda elementlarni qayta-qayta qo‘shish samarasiz bo‘ladi. Prefix sum arrayning boshidan har bir indexgacha bo‘lgan yig‘indilarni oldindan saqlaydi:

Asl array:   [3,  5,  2,  4]
Prefix sum:  [3,  8, 10, 14]

Bu yerda prefix arraydagi 10 — asl arrayning 3 + 5 + 2 yig‘indisi. Oldindan hisoblash O(n) vaqt oladi, keyin ko‘plab oraliq yig‘indilarini tez topish mumkin. Bu usul hisobotlar, moliyaviy statistika, o‘yin natijalari va vaqt oralig‘idagi o‘lchovlar bilan ishlashda foydali.

Array bilan ishlashdagi keng tarqalgan xatolar

Oxirgi indexni length bilan adashtirish

Uzunligi 5 bo‘lgan arrayning oxirgi indexi 5 emas, 4. Umumiy formula:

oxirgi index = length - 1

Bu xato off-by-one error, ya’ni bir birlikka adashish deb ataladi. Array masalalarida eng ko‘p uchraydigan xatolardan biri shu.

Bo‘sh arrayni hisobga olmaslik

Eng katta elementni topishda darhol array[0]ga murojaat qilinsa, bo‘sh arrayda bunday element mavjud bo‘lmaydi. Algoritm boshida array bo‘sh yoki bo‘sh emasligini tekshirish kerak.

Qiymat va indexni aralashtirish

array[3] yozuvidagi 3 qiymat emas, index. Arrayning ichida qiymati 3 bo‘lgan element boshqa indexda turishi yoki umuman mavjud bo‘lmasligi mumkin.

Saralanmagan arrayda binary search ishlatish

Binary search faqat tartib ma’lum bo‘lganda qaysi yarmini tashlab yuborishni aniqlay oladi. Saralanmagan arrayda uning natijasi ishonchsiz bo‘ladi.

Element qo‘shilganda siljishni unutish

Array o‘rtasidagi band katakka yangi qiymatni shunchaki yozish eski qiymatni yo‘qotadi. Haqiqiy qo‘shish uchun avval keyingi elementlarni o‘ngga surib, bo‘sh joy ochish kerak.

Dynamic arrayni cheksiz deb o‘ylash

Dynamic array avtomatik kattalashadi, lekin xotira cheksiz emas. Kengayish vaqtida yangi xotira ajratish va eski elementlarni ko‘chirish xarajati mavjud. Juda katta ma’lumot bilan ishlaganda length, capacity va umumiy xotira sarfi hisobga olinishi kerak.

Qachon array tanlamaslik kerak?

Array juda muhim tuzilma, lekin har bir masala uchun eng yaxshi yechim emas. Quyidagi holatlarda boshqa ma’lumotlar tuzilmasini ko‘rib chiqish kerak:

• array boshiga yoki o‘rtasiga juda ko‘p element qo‘shilib-o‘chirilsa;
• elementlar orasidagi bog‘lanish oddiy ketma-ketlikdan murakkabroq bo‘lsa;
• qiymat bo‘yicha juda tez qidirish kerak, lekin ma’lumot saralanmagan bo‘lsa;
• doim eng katta yoki eng kichik elementni tez olish kerak bo‘lsa;
• ma’lumot ota-bola yoki tarmoq shaklidagi bog‘lanishga ega bo‘lsa.

Masalan, foydalanuvchini identifikatori orqali juda tez topish kerak bo‘lgan tizimda oddiy arrayni boshidan oxirigacha qidirish qimmatga tushishi mumkin. Bunday vazifada hash table mosroq bo‘lishi mumkin. Navbat boshidan doim element olib tashlash kerak bo‘lsa, har safar array elementlarini surish o‘rniga queue uchun mos tuzilma tanlanadi.

To‘g‘ri ma’lumotlar tuzilmasini tanlash “qaysi biri eng tez?” degan umumiy savolga emas, “biz qaysi amalni eng ko‘p bajaramiz?” degan savolga javob berishdan boshlanadi.

Array haqidagi eng muhim xulosa

Arrayni faqat [] belgisi bilan yoziladigan qiymatlar ro‘yxati deb eslab qolish yetarli emas. Sintaksis tildan tilga o‘zgaradi, lekin arrayning modeli o‘zgarmaydi:

1. elementlar tartib bilan saqlanadi;
2. har bir elementning indexi mavjud;
3. klassik array elementlari xotirada yonma-yon joylashadi;
4. element hajmi ma’lum bo‘lgani uchun uning manzili index orqali hisoblanadi;
5. shu sababli istalgan indexdagi elementga kirish O(1) bo‘ladi;
6. shu tartibni saqlash sabab array o‘rtasiga qo‘shish va o‘chirish qimmatroq bo‘lishi mumkin.

Arrayni o‘rganishda eng muhim savol “uni qaysi tilda qanday yozaman?” emas, balki “xotirada nima sodir bo‘ladi va har bir amal qancha ish talab qiladi?” bo‘lishi kerak. Shu modelni tushungan odam arrayni istalgan dasturlash tilida ishlata oladi; faqat o‘sha tilning sintaksisi va standart kutubxonasidagi nomlarni o‘rganishi qoladi.

Keyingi qismda array ustida bajariladigan asosiy amallarni — elementni o‘qish va o‘zgartirish, array bo‘ylab yurish, qidirish, qo‘shish hamda o‘chirishni — xotirada nima sodir bo‘lishi va vaqt murakkabligi bilan birga ko‘rib chiqamiz.