Skip to content

Xotira va Space Complexity. Algoritmlar va Murakkablik. 3-Qism

Ushbu maqolada algoritmlarni xotira sarfi bo'yicha analiz qilishni, ya'ni Space Complexityni ko'rib chiqamiz.

Xotira nima?

Kompyuterda barcha dastur qandaydir data, ya'ni ma'lumot bilan ishlaydi. Bu ma'lumotlar esa kompyuterning xotirasi, yoki RAMda saqlanadi.

RAM

Random Access Memory(RAM) kompyuterning asosiy xotirasi bo'lib, dasturlarni ishlatish uchun CPU aynan RAMdan ma'lumot o'qib, yozadi.


"Random access" deyilishini sababi, RAMdagi tasodifiy(random) xotira qismidan to'g'ridan-to'g'ri(aytaylik \(O(1)\) vaqtda) o'qish/yozish(access) mumkin. Boshqacharoq aytganda, CPU xotiraning ixtiyoriy qismiga bir xil vaqtda murojaat qila oladi. Masalan, Qattiq Disklarda RAMdan farqli ravishda xotira qismiga murojaat qilishga ketadigan vaqt, bu qismni diskdagi jismoniy joylashuviga bog'liq.


Odatda RAMda ma'lumotlar 1 baytli bloklardan iborat bo'ladi. Masalan, quyidagi "grid"ni RAM deb tasavvur qilsak, undagi har bir katak bir bayt ma'lumot saqlaydi va ixtiyoriy katakka murojaat qilish uchun CPU bir xil vaqt sarflaydi:


big_o

Storage emas, Memory

Shu o'rinda, Xotirani Storage bilan adashtirmaslik lozim. Storage yoki Disk, "persistent" qurilma hisoblanadi va kompyuter o'chganida ham ma'lumotlar saqlanib qoladi. Disk RAMga nisbatan ancha sekin ishlaydi.


RAM Diskka nisbatan ancha tanqis resurs, RAM hajmi odatda kompyuterlarda 16-32 GB bo'ladi. Disk bo'lsa, bir necha TB bo'lishi mumkin.


Bizga tanqis, lekin tez ishlaydigan resursdan unumli foydalanish qiziq. Shuning uchun Space Complexity deganda faqat RAMni analiz qilamiz.

CPU o'zi diskka to'g'ridan-to'g'ri o'qib, yozolmaydi. Ma'lumotlar baribir RAM orqali o'tishi kerak. Demak, aslida RAMga e'tibor qilishdan boshqa ilojimiz ham yo'q.

Adreslash

Demak, CPU xotiradagi har bir baytga murojaat qila oladi. Buning uchun esa, har bir baytni o'zini adresidan foydalanadi.


Protsessorni arxitekturasiga qarab, xotirani adreslash 32 bit yoki 64 bitli bo'lishi mumkin. Masalan, 32 bitli arxitekturada, xotira adresi uzunligi 32 bitdan iborat bo'ladi, bu degani \(2^{32}\) baytni(\(4\) GiB) adreslash mumkin. Hozirda asosan 64 bit arxitekturali protsessorlar keng tarqalgan.


Masalan, quyidagi C++ kod x o'zgaruvchini adresini chiqaradi:

int x;
cout << &x;

x ni adresi masalan quyidagicha bo'lishi mumkin (odatda \(16\) lik sanoq sistemasi ishlatiladi):

0x7ffdc7cf97a4

Demak, xotira 1 baytli bloklarga bo'lingan va har bir blokni o'zini adresi bilan murojaat qilish mumkin:


big_o

Processlar

Dasturni bir marta ishga tushirgandagi holati Process deyiladi.


Har bir process o'ziga ajratilgan xotira qismiga ega bo'ladi va process bu xotira qismidan tashqariga murojaat qila olmaydi. Bu qismni ajratishni eng oddiy usuli sifatida Base and Boundni aytish mumkin. Bunda process uchun qandaydir oraliqdagi xotira qismi ajratiladi. Masalan, 0xc0000000dan 0xc000ffffgacha xotira ajratilishi mumkin.


big_o


Amalda, Base and Bound ishlatilmaydi va faqatgina konseptual tushunish uchun kerak bo'lishi mumkin. Xotira nazorati odatda virtual xotira orqali amalga oshiriladi.

Xotira taqsimoti

Hop, dasturni ishga tushirdik, yangi process yaratildi. Process uchun xotira qismi ajratildi. Ana endi process bu xotiradan qanday foydalanishini ko'rib chiqamiz.


Dastur ishga tushirilishi quyidagicha ifodalanishi mumkin:

  1. Dastur kodi maxsus "Kod segmenti"ga ko'chiriladi.
  2. Global o'zgaruvchilar "Data segmenti"ga ko'chiriladi.
  3. Stack va Heap xotira ajratiladi.

Process uchun xotira ajratilishini quyidagicha ko'rish mumkin:


big_o


E'tibor qilgan bo'lsangiz, yuqoridagi chizmada xotira adreslari katta qiymatli adresdan kichik qiymatli adresga qaratib keltirilgan. Buning asosiy sababi, Stack pastga qarab o'sishi va Heap yuqoriga qarab o'sishini aniqroq ko'rsatish uchun.

Kod va Data Segmenti

Kod Segmentida dastur kodi saqlanadi. Data Segmentida esa, dastur davomida ishlatilgan global obyektlar va o'zgaruvhilar saqlanadi. Data Segmenti o'z o'rnida.


Bu maqolada asosan Stack va Heap haqida gaplashamiz.

Stack va Heap

Buyog'iga xotiraning asosiy qismi bo'lgan Stack va Heap xotira haqida gaplashamiz.

Heap xotira

Heap xotirada process davomida dinamik yaratilgan obyektlar saqlanadi. Yuqoridagi chizmada ifodalanganidek, heap yuqoriga qarab o'sadi.


C++da quyidagilar heapda saqlanadi:

  1. malloc() orqali yaratilgan obyektlar
  2. new kalit so'zi bilan yaratilgan obyekt va massivlar
  3. map, set, vector kabi STL ma'lumot tuzilmalari elementlari.

Quyidagilarning barchasi heapda saqlanadi:

ptr = (int *) malloc(n * sizeof(int));
MyClass my_obj = new MyClass();
int* arr = new int[100];
vector<int> v(100, 0);

Oxirgi misoldagi vectorning elementlari heapda saqlansada, contextga qarab v obyektining o'zi stackda bo'lishi mumkin. Ya'ni STL tuzilmalari new kalit so'zi bilan yaratilmasa, obyektning o'zi stackda, ammo, uning elementlari heapda joylashadi.

Javada ham xuddi shu tarzda barcha obyektlar heapda saqlanadi. Xattoki, primitiv tiplar "wrapper"lari Boolean, Integer, Character kabilar ham obyekt bo'lgani uchun heapda saqlanadi. Stackda primitiv tipdagi o'zgaruvchilar saqlanadi.


Pythonda ham barcha obyektlar, Dictionary va Stringlar heapda yaratiladi.

Memory Leaks

Heap xotiradagi ma'lumotlar Operatsion Sistema tomonidan nazorat qilinmaydi. Bu degani, yangi obyektlar yaratish va ularni tozalash bajarilayotgan dasturning zimmasida. Masalan, C++dagi quyidagi kodni ko'raylik:

void func() {
    DataClass* data = new Data();
    return;
}

int main() {
    func();
    // data obyektiga murojaat qilib bo'lmaydi
    // ammo u hali ham heap xotirada 
}


func ichida data obyekt yaratilganda, obyektning o'zi heapda, unga pointer (ko'rsatkich) esa stackda joylashadi (lokal o'zgaruvchi bo'lgani uchun). func funksiya return qilganidan so'ng, stackda joylashgan ko'rsatkich o'chib ketadi va dataga murojaat qilishni imkoni bo'lmaydi. Ammo, dataga murojaat qilib bo'lmasada, heapda yaratilgan data obyekti hali ham o'chmagan bo'ladi. Sababi, heapda yaratilgan obyektlar "qo'lda" o'chirilishi kerak. Ya'ni ular avtomatik o'chib ketmaydi.


C++ kabi memory safe bo'lmagan tillardagi bu muammo Memory Leak deb ataladi. Memory Leak deb murojaat qilib bo'lmaydigan heapdagi ma'lumotlarga aytiladi. Ular process tugamagunga qadar xotiradan joy egallab turadi va xotirani to'ldirib qo'yishi mumkin. Shuningdek, memory leak tufayli Undefined Behaviourlar kelib chiqadi va debug qilish qiyinlashadi.

Garbage Collection

Java va Python kabi dasturlash tillarida bu muammoga yechim bor.


Keling yuqoridagi kodni Javadagi versiyasini ko'ramiz:

public class Main {
    public static void func() {
        Data data = new Data();
        return;
    }

    public static void main(String[] args) {
        func();
        // data avtomatik ravishda heapdan tozalanadi
    }
}

Bir xil kod, lekin Javada func bajarilganidan so'ng data heapdan avtomatik tarzda o'chirib tashlanadi. Javaning bu xususiyati Garbage Collection deb ataladi.


Garbage Collector obyektlarga bo'lgan "reference"larni nazorat qilib boradi. Agar biror obyekt uchun hech bir threadda reference qolmasa, Garbage Collector avtomatik tarzda bu obyektni heapdan o'chirib tashlaydi.


Javada hamma narsa obyekt bo'lgani uchun Garbage Collection juda ham muhim, bu orqali Javada obyektlarni xotiradan tozalashni o'ylamay agressivroq yaratish mumkin. Garbage Collectionsiz Javani tasavur qilib ko'ringa :)

Bu mavzuda shaxsan menga qiziq yechimlardan biri Rustniki. Rustda Memory Leak yaratadigan kod compile bo'lmaydi! Ya'ni Rust xotiradan "unsafe" foydalanishga yo'l qo'ymaydi. Bu ajoyib xususiyat Rustning Ownership Principlei orqali ishlaydi. O'rganishni maslahat beraman.

Stack xotira

Stack xotirada dasturni ishlashiga bevosita bog'liq ma'lumotlar saqlanadi. Bular funksiya argumentlari, lokal o'zgaruvchilar bo'lishi mumkin.


Stack xotira Last In First Out tartibida ishlaydigan Stack ma'lumotlar tuzilmasiga asoslanib ishlaydi. Bunda stackni faqat ustiga yangi ma'lumot qo'shib (push amali), faqat ustidan ma'lumotni olish mumkin(pop amali). Stack xotirada esa element qo'shish va o'chirish uchun stack pointer nomli ko'rsatkichdan foydalaniladi.


Oddiy qilib aytganda Stackda funksiya argumentlari va lokal o'zgaruvchilar saqlanadi. Misol sifatida, quyidagi funksiyani ko'raylik:

void func(int a, int b) {
    int c = a + b;
    cout << c << '\n';
    return;
}

Aytaylik bu funksiyani func(32, 64); qilib chaqiraylik. Bu chaqiruvdan oldin Stackga funksiya argumentlari(a=32 va b=64) qo'shiladi. So'ng "return address", deb nomlangan maxsus adres qo'shiladi, bu adres funksiya return qilganidan so'ng, qaysi instruksiyaga qaytishi kerakligini ifodalaydi. Vanihoyat, func ni ichida lokal o'zgaruvchi c stackda yaratiladi:

big_o


Bunda Stack pastga qarab o'smoqda. Ya'ni a = 32 birinchi bo'lib qo'shilgan, c bo'lsa oxirgi bo'lib.


Keling endi yana bir funksiya qo'shamiz:

int mul(int a, int b, int c) {
    return a * b * c;
}

void func(int a, int b) {
    int c = a + b;
    cout << mul(a, b, c) << '\n';
    return;
}

mul funksiya bajarilishdan oldin Stack quyidagi ko'rinishda bo'ladi:

big_o


Ko'rib turganingizdek funcni ichida chaqirilgan mul uchun ham dastlab argumentlar, so'ng "return address" stackga qo'shilmoqda. Stackni yashil rangda belgilangan qismi esa func funksiyasini, ko'k rangdagi qismi esa mul funksiyasini Stack Frameini ifodalaydi. Funksiyaning Stack Frameida funksiya holatiga oid barcha ma'lumotlar saqlanadi.

Albatta bu misollarda soddalashtirishlar ko'p. Amalda, Stack bundan ko'ra ko'proq "meta" ma'lumotlar saqlaydi, ayrim registerlar, stack frame ma'lumotlari, argumentlar soni va hokazo. Hozircha bizga Stackga nima qo'shilishi va qanday qo'shilishi muhim.

Heap vs Stack

Heap ham Stack ham RAMda joylashgan bo'lsada, ko'p jihatdan bir-biridan farq qiladi. Masalan:

  1. Stack Heapdan ko'ra tezroq. Bunga ko'p sabablar bor. Masalan, tuzilish jihatdan Stackdagi elementlarni topish qiyin emas, heapni strukturasi murakkab bo'lgani tufayli ham ma'lumotga murojaat qilish sekinroq amalga oshadi. Shuningdek, Stackda elementlar ko'p murojaat qilingani uchun, cache xotiradan ko'proq foyda ko'radi.
  2. Stack xotira chegaralangan resurs. Odatda Stack OS tomonidan belgilangan limitga ega bo'ladi va bir necha Megabaytdan iborat bo'ladi. Buning asosiy sababi, Stack xotira har bir thread uchun alohida ajratiladi. Stack hajmi kattalashgani sari yaratilishi mumkin bo'lgan threadlar soni kamayib boradi. Shuningdek, kattaroq stacklarda muammolarni topish va to'g'irlash qiyinlashadi. Umuman olganda, yaxshi dizaynli kod katta hajmdagi stackdan foydalanmaydi. Heap bo'lsa aksincha, butun boshli RAM hajmidan ham katta hajmdagi joydan foydalanishi mumkin(virtual memory tufayli).
  3. Heapda dinamik uzunlikdagi obyektlar yaratish mumkin. Masalan Linked-List va Binar Daraxt kabi dinamik strukturalarni Heapda osonlikcha yaratish mumkin.
  4. Heapda obyektlar global va istalganicha nazorat qilinishi mumkin. Heapda yaratilgan obyekt, Stack kabi funksiya tugaganida emas, istalgan paytda o'chirilishi va istalgan joydan murojaat qilinishi mumkin.

Space Complexity

Xotirani va Time Comlpexityni tushungandan keyin Space Complexityni tushunish qiyin emas.


Time Complexityga ta'rif berganda, dastlab dastur bajaradigan operatsiyalar sonini topib, so'ng uning o'zgarish sur'atini Time Complexity orqali ifodalagan edik.


Space Complexity uchun ham, dastur ishlatgan baytlar sonini topib, o'zgarish sur'atini "big O" kabi funksiya orqali ifodalask bo'ladi.


Maslan, quyidagi dasturni ko'raylik:

int func(int n) {
    vector<int> arr(n, 0);
    ....
}

Bu dasturda uzunligi n bo'lgan int tipli vector yaratildi. Bu degani \(n\) ta int tipidagi o'zgaruvchi yaratildi. intni hajmi 4 bayt bo'lgani uchun, bu dastur jami \(4n\) xotira ishlatmoqda, buni \(O(4n)\) ko'rinishida ham yozishimiz mumkin. Time Complexity darsidan bilamizki, \(O(4n)\) = \(O(n)\). Demak, bu funksiyaning xotira sarfi \(O(n)\).

struct LinkedListNode{
    int val;
    LinkedListNode* next;
};

vector<LinkedListNode> linked_list(n);

Yuqoridagi kodda, uzunligi \(n\) bo'lgan linked list yaratilgan. Linked listdagi har bir tugunda int tipidagi val qiymati va next ko'rstakichi mavjud. int \(4\) bayt va next ko'rsatkichi \(8\) bayt(\(64\) bitli adres) xotiradan joy oladi. Demak, har bir tugun \(4+8=12\) bayt joy oladi. \(n\) ta tugun bo'lganda, Space Complexity \(O(12n)\) bo'ladi, buni esa \(O(n)\) deyish mumkin.

Tiplar muhim emas

Yuqoridagi misollarda qiymatlar uchun int ishlatildi. Ammo, buni o'rniga ko'proq joy egallaydigan tip bo'lganda ham Space Complexity o'zgarmasdi. Sababi, murakkablik nazariyasiga ko'ra \(O(4n)\) ham, \(O(16n)\) ham \(O(n)\) bo'ladi. Bizga faqat o'sish sur'ati qiziq. Elementlar hajmi esa o'zgarmas qiymat.


Xuddi shu kabi, murakkabroq tuzilmalarda ham, obyektning qanchalik kattaligi odatda muhim emas. Masalan, Binary Tree strukturasi Linked Listdan ko'ra xotiradan ko'proq joy egallaydi, aytaylik \(20\) bayt. Lekin bu qiymat o'zgarmas bo'lgani uchun, \(n\) ta elementli Binary Treeni ham, \(n\) ta elementli Linked Listni ham Space Complexitysi bir xil bo'ladi.


O'zi umuman ko'pchilik ma'lumot tuzilmalari hajmi o'zgarmas. Ya'ni, \(n\) ta elementli HashMap, Binary Tree, Linked List, Trie, BBST, Heap, String va Arraylarning barchasi \(O(n)\) Space Complexityga ega bo'ladi.

\(n\) ta elementli int tipidagi massiv \(4n\) bayt joy egallasa, xuddi shu o'lchamdagi linked-list \(12n\) bayt joy egallaydi. Ayrim xotira tanqis holatlarda, \(n\) dan oldin kelgan "constant factor" muhim rol o'ynaydi. Shuning uchun iloji boricha linked listdan ko'ra oddiy arrayni ishlatgan ma'qul.

Shuningdek, xotira sarfi vaqt sarfiga nisbatan ancha deterministikroq. Dasturni ishlash vaqti ko'p factorlarga bog'liq bo'lgani uchun, har doim har xil vaqt ketqizishi mumkin. Xotira sarfini bo'lsa dasturni kodiga qarab katta aniqlikda taxmin qilish mumkin. Bu esa "critical" hollarda, xotirani osonroq nazorat qilishga yordam beradi.

Rekursiya

O'zi umuman Space Complexityni hisoblash ancha oson. Lekin, Rekursiya bilan qiziq muammolar kelib chiqadi.


Sonni factorialini hisoblashni ko'raylik. Quyidagi kod, bu ishni iterativ usulda amalga oshiradi:

vector<int> fact(n + 1, 0);

fact[0] = 1;
for(int i = 1; i <= n; i ++)
    fact[i] = fact[i - 1] * i;

Quyida esa, xuddi shu kodni rekursiv ko'rinishi:

int fact(int n) {
   if (n == 0)
      return 1;
   return n * fact(n - 1);
}

Bu kodlarni ishlash vaqtini bir zum unutib turib, faqat xotira sarfiga e'tibor qilaylik. Iterativ kodda uzunligi \(n + 1\) bo'lgan list oldindan yaratilmoqda. Demak Space Complexityni \(O(n)\) desak bo'ladi.


Rekursiv kodda esa faqat primitiv int o'zgaruvchilari ishlatilgan xolos, hech qanday list yo'q. Bir qarashda Space Complexity \(O(1)\)dek tuyuladi. Yaxshiyamki, Stack xotirani o'rgangan edik, Stack qanday o'zgarishini ko'rib chiqamiz.


Masalan, fact(3) holatni ko'raylik. fact(3) chaqirilgandan keyin Stack quyidagi ko'rinishda bo'ladi:

big_o


Ya'ni, fact uchun argument va return address qo'shildi. factni ichida esa, \(n\) != \(0\) bo'lgani uchun return n * fact(n - 1); qatori bajariladi. Bu esa fact(n-1), ya'ni fact(2) chaqirilishga sabab bo'ladi:

big_o


Xuddi shu tarzda fact(1) va fact(0) lar rekursiv chaqiriladi:

big_o


Ana endi biroz to'xtaymiz. Hozir biz fact(0)ni ichidamiz, \(n\) = \(0\) bo'lgani uchun fact(0) ortiqcha amal bajarmay \(1\) qiymatini qaytaradi. Funksiya qaytargan qiymat protsessor registerida saqlanadi(aytaylik EAX). Bu degani hozircha bu qiymatni istalgan paytda olishimiz mumkin.


Ana endi, fact(0) dan chiqqanimizdan keyin, fact(1)ga qaytamiz. Lekin, fact(1)ning aynan qayeridan ishni davom ettiramiz? Yaxshiyamki, bizni stackda "fact(0) return address" elementi bor edi. Bu qiymat bizga fact(1) ning return n * fact(n - 1); qismidagi instruksiyalardan davom etish kerakligini ko'rsatadi. Protsessor shu qismga qaytadi va fact(n - 1) o'rniga EAX registerini (fact(0) qaytargan qiymat o'sha yerda) ishlatib ko'paytmani hisoblaydi.


Har bir funksiyadan chiqqanimizdan keyin, shu funksiya uchun ochilgan stack frame (yuqoridagi yashil, havorang bloklar) stackdan olib tashlanadi. Buning uchun stack frameni surib qo'ysa bo'ldi.


Yuqorida xotira stackidan aynan qanday foydalanishni ko'rib chiqdik, Space Complexity uchun qiziq holat esa boyagi fact(0) chaqirilishidan oldingi vaziyat:

big_o


Bu yerda har bir yashil/havorang blok stack frameni ifodalaydi. Har bir funksiya chaqiruvi uchun alohida stack frame yaratiladi va uning ichida shu funksiya chaqiruvi uchun kerak bo'lgan ma'lumotlar: argumentlar, return address, lokal o'zgaruvchilar saqlanadi.


Qiziq joyi esa bu stack framelar soni dastlabki \(n\) ning qiymatiga bog'liq. Masalan, yuqoridagi holatda \(n=3\) uchun \(4\) ta stack frame yaratildi, \(n=100\) bo'lganida \(101\) ta stack frame ochishga to'g'ri kelardi. Ya'ni, berilgan \(n\) qiymati uchun \(n+1\) ta stack frame yaratilmoqda.


Xulosa qilamiz.


Iterativ yechim:

vector<int> fact(n + 1, 0);

fact[0] = 1;
for(int i = 1; i <= n; i ++)
    fact[i] = fact[i - 1] * i;

\(n + 1\) ta elementli vectorni oshkor ravishda xotirada ochyapmiz. Shuning uchun, Space Complexity \(O(n)\).


Rekursiv yechim:

int fact(int n) {
   if (n == 0)
      return 1;
   return n * fact(n - 1);
}

Rekursiya uchun \(n+1\) ta stack frame ishlatiladi, har bir stack frame \(O(1)\) xotira egallagani uchun(faqat bu misol uchun), umumiy Space Complexity \(O(n)\) bo'ladi.

Misollar

Quyida rekursiya uchun Space Complexity hisoblashga ko'proq misollar ko'rib chiqamiz.


int fact(int n, vector<int> temp) { //temp.size() == m
   if (n == 0)
      return 1;
   return n * fact(n - 1, temp);
}

Bu misolda, funksiya argumenti sifatida \(n\) dan tashqari \(temp\) vectorini ham qabul qilyapmiz. Shuning uchun har bir factga chaqiruvda stack frame \(temp\) vectorni ham o'z ichiga oladi. Ya'ni har bir stack frame \(O(m)\) Space Complexityga ega bo'ladi(\(temp\)ni uzunligi \(m\)). Stack Framelar soni \(n\) ta bo'lgani uchun, umumiy Space Complexity \(O(nm)\) bo'ladi.

Bu yerda ozgina aldadim. Sababi, oldinroq aytganimdek C++da vector elementlari heapda yaratiladi. Ya'ni stack frameda \(temp\) vectorni barcha elementlari emas, faqat shu elementlarning adresi saqlanadi. Ya'ni har bir stack frame \(O(1)\) xotira oladi. Ammo, har bir stack frame uchun \(temp\)ni yangi nusxasi heapda yaratiladi. Shuning uchun, har bir stack frame \(O(m)\) xotira egallaydi desa ham bo'ladi. Chunki Heap ham Stack ham asosiy xotirani qandaydir qismi.

int fact(int n, vector<int> &temp) { //temp.size() == m
   if (n == 0)
      return 1;
   return n * fact(n - 1, temp);
}

Bu esa \(O(n)\) Space Complexityga ega. Sababi \(temp\) reference orqali uzatilmoqda: &temp. Bu kabi funksiya argumentini qabul qilish "pass by reference" deb nomlanadi va bu holda fact funksiyasi \(temp\)ni o'zini emas, uni adresini yoki referenceni qabul qiladi. Bu degani har bir fact chaqiruvi uchun bir xill qiymat, ya'ni shu reference ishlatiladi, reference esa xotiradan \(O(1)\) joy egallaydi. Shuning uchun umumiy Space Complexity \(O(1)\). Birinchi misolda esa, \(temp\) qiymati bilan funksiya uzatilgan edi, ya'ni "pass by value". Bu holda, har bir stack frame uchun alohida \(temp\) massiv nusxasi uzatiladi.

Bu misolda fact funksiyaga faqat \(temp\)ni adresini uzatganimiz bilan, \(temp\)ni o'zi ham fact funksiya chaqrilishidan oldin xotiraning qaysidir qismida yaratilib, keyin factga uzatiladi. Lekin bu xotira sarfini factni Space Complexitysi uchun inobatga olmaymiz. Odatda Space Complexity deganda, extra Space Complexity nazarda tutiladi. Ya'ni, ma'lum funksiya yoki dastur amallarni bajarish uchun qancha qo'shimcha xotira ishlatadi?

int fact(int n) { 
   if (n == 0)
      return 1;
   vector<int> temp(m, 0);
   return n * fact(n - 1);
}

Ana endi \(temp\) vectori funksiya ichida lokal o'zgaruvchi sifatida ochildi. Bunda ham birinchi misolga o'xshab Space Complexity \(O(nm)\) bo'ladi. Sababi har bir stack frameda uzunligi \(m\) bo'lgan \(temp\) vectori saqlanadi, masalan quyidagi kabi:

big_o

int fact(int n) { 
   if (n == 0)
      return 1;

   int ret_val = n * fact(n - 1);

   vector<int> temp(m, 0);

   return ret_val;
}

Bunisi esa eng qiziq misol. E'tibor qilgan bo'lsangiz, \(temp\) vectori, rekursiv chaqiruvdan so'ng yaratilmoqda. fact(0) bajarilishidan oldin, stack quyidagi ko'rinishda bo'ladi:

big_o


\(temp\) local o'zgaruvchi bo'lsa ham stack framelar ichida yo'q? Sababi, koddagi \(temp\)ni yaratadigan operatsiyaga hech bir fact() funksiya chaqiruvi hali kelmadi. fact(0) qaytib, stackdan o'chib ketganidan keyingina, fact(1) uchun \(temp\) yaratiladi:

big_o

Ammo, fact(1) qiymat qaytarganidan so'ng, u ishlatgan stack frame, unga qo'shilib \(temp\) vectori ham o'chib ketadi. Control esa fact(2)ga qaytadi va u o'zi uchun \(temp\) yaratadi va hokazo.


Xullas, har bir stack frame alohida \(temp\) vector yaratgani bilan, bir vaqtni o'zida xotirada ko'pi bilan bitta \(temp\) vectori saqlanadi. Shuning uchun worst-case Space Complexity \(O(n + m)\) bo'ladi. Ya'ni, eng yomon holatda rekursiya \(n\) qavat pastga tushadi va buning uchun \(O(n)\) xotira sarflaydi. So'ng, faqat oxirgi qavatdagina \(temp\) vectori saqlanayotgan bo'lishi mumkin. Shuning uchun umumiy Space Complexity \(O(n + m)\).

Tail Recursion

Dastlab keltirilgan Factorialni hisoblovchi iterativ va rekursiv yechimlar xotiradan ko'p joy oladi. Shuni optimalroq usulda ishlaymiz.


Iterativ yechim:

int fact = 1;
while(n > 0) {
    fact *= n;
    n --;
}

Rekursiv yechim:

int fact(int n, int acc) {
    if(n == 0)
        return acc;
    return fact(n - 1, n * acc);
}


Bu ikkala yechim ham \(O(1)\) Space Complexityga ega!


Iterativ yechimku tushunarli, lekin Rekursiv yechimda nimalar bo'lyapti? Yana stackni ko'rib chiqamiz.


Aytaylik, fact(3, 1) chaqirildi. fact(0, 6) chaqirulganicha stack xotirani kuzatamiz:

big_o


acc argumentini hisobga olmasa, boshqa hech nima o'zgarmadi. acc argumenti javobni yig'ib ketish uchun ishlatilgan xolos, bu yerda Space Complexity o'zgarishiga ta'sir o'tkazmaydi.


Hop, fact(0, 6) ni baralishini ko'raylik. \(n==0\) bo'lgani uchun, funksiya acc=6 qiymatini qaytaradi va bu qiymat EAX registerga yoziladi. So'ng, dastur stackdagi "return address" orqali fact(1)ning return fact(n - 1, n * acc) qismiga qaytadi. Buni endi return EAX deb tasavur qilsak ham bo'ladi. Sababi fact(0, 6) qaytargan qiymat EAX registerida saqlanib turibdi. So'ng, fact(1) ham o'zini javobini EAXga yozadi(ya'ni EAXdagi qiymatni EAXga) va fact(2)dagi aynan shu return EAX qismiga qaytadi. fact(2) ham javobini EAXga yozadi va hokazo.


Bu yerda muammo yuqoridagi funksiya fact(3) qaytaradigan qiymat, eng quyidagi funksiya chaqiruvi fact(0) bilan bir xil. Bu kabi rekursiya Tail Recusion deb ataladi.


Tail Recursionda rekursiv funksiya chaqiruvi (masalan, fact(n) ni ichida fact(n-1) ni chaqirish) funksiyaning oxirida chaqiriladi.


Yuqoridagi misolga qaytadigan bo'lsak, bu kabi Tail Recursion uchun, Tail Recursion Optimization (TCO)ni qo'llasak bo'ladi.


TCOni asosiy g'oyasi, bitta stack frameni boshqa funksiya chaqiruvlari uchun qaytadan ishlatish.


Masalan, fact(3, 1) ichida fact(2, 3) chaqiriladi. Aytaylik, fact(2, 3) ni chaqirishdan oldin, stack quyidagicha bo'lsin:

big_o


Bu yerda fact(2, 3) o'ziga yangi stack frame ochish o'rniga fact(3, 1)ni stack frameini ishlatsa bo'ladi. Sababi, fact(3, 1) uchun stack framedagi ma'lumotlar boshqa kerak emas, "return address"ni saqlab qolsa bo'ldi. "Return address"ni esa boshqa funksiya chaqiruvlari o'zgartirmaydi. Shuning uchun, fact(2, 3) chaqirilganidan so'ng stack quyidagicha bo'ladi:

big_o


Xuddi shu tarzda qolgan fact(1, 6) va fact(0, 6) chaqiruvlari ham aynan shu stack frameni qayta ishlashadi. Butun funksiya bajarilishi davomida bitta stack frame ishlatilgani uchun, umumiy Space Complexity ham \(O(1)\).

Made with Material for MkDocs