Ajrat va hukmronlik qil

Ajrat va hukmronlik qil paradigmasi asosiy masalalari:

• 
  Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:
  

• 
  Ikkilik qidirish (Binary Search)
  

• 
  Merge Sort
  

• 
  Quick Sort
  

• 
  Eng yaqin ikki nuqta (Closest two points)
  

• 
  Strassen ko’paytirishi (Strassen multiplication)
  

• 
  Karatsuba algoritmi (Karatsuba algorithm)
  

• 
  Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
  

Kesh - bu shaxsiy kompyuter protsessoridan tez-tez so'raladigan ma'lumotlarni ma'lum vaqt davomida saqlash uchun foydalanadigan yuqori tezlikda ishlaydigan xotira. Bu samaradorlikni sifat jihatidan oshiradi, chunki u protsessorga kerakli ma'lumotlarni qidirish va ma'lumotlarni eng tezkor ravishda qanday olish kerakligini ko'rsatib beradi. Kesh xotirasi turli xil operatsiyalar tezligiga bevosita ta'sir qiladi, chunki u oldindan kerakli ma'lumotlarni saqlaydi. Uning ishlash printsipini oddiy misol bilan tavsiflash mumkin. Ularning ishini optimallashtirish uchun har qanday kishi ish stolidagi narsalarni ma'lum mantiqiy tartibda tartibga solishga harakat qiladi.

Ehtimol, ruchkalar, telefon, kerakli ma'lumotnomalar, joriy hujjatlar va boshqalar yaqin joyda joylashgan bo'lishi mumkin, chunki har safar kimdir besh yil oldin yillik hisobot ostida kerakli hujjatlarni yashirgan bo'lishi mumkin emas, chunki bu vaqt va kuch talab qiladi. Aynan shu printsip asosida kesh-xotira ishlaydi. Kompyuter darajasida bu nimani anglatadi? Aslida shunga o'xshash jarayon. Barcha ma'lumotlar shaxsiy kompyuterda ma'lum bir ierarxiyada mavjud. Agar ba'zi ma'lumot boshqalarga qaraganda tez-tez talab qilinadigan bo'lsa, ular mos ravishda yaqinroqdir.
Kesh - bu yuqori tezlikda ishlaydigan xotira, bu sizga protsessorga kerakli ma'lumotlarni tezda olish imkonini beradi, buning natijasida shaxsiy kompyuterning ishlashi sifat jihatidan oshadi. Kesh brauzerlar tomonidan ham qo'llaniladi va oddiy tozalash tartibini talab qiladi. Kesh [yoki kesh (ingliz tilidagi kesh, fr. Ref.rf-da joylashtirilgan cacher - yashirish; talaffuz qilingan - kesh) - tezkor xotira bilan talab qilinishi mumkin bo'lgan ma'lumotni o'z ichiga olgan tezkor kirish bilan, masalan, operatsion. Keshdagi ma'lumotlarga kirish tashqi xotiradan ma'lumotni olish yoki uni qayta hisoblashdan ko'ra tezroq, bu esa kirishning o'rtacha vaqtini kamaytiradi.
Protsessor ishlash uchun o‘z ma’lumotlarini operativ xotiradan oladi. Bunda mikrosxema ichida signallar juda katta chastotada (bir necha yuz MGts) ishlanadi, operativ xotiraga murojaatlarning hammasi esa bir necha marta kam chastotada sodir bo‘ladi. Chastotaning ichki ko‘paytirish koeffitsienti qanchalik yuqori bo‘lsa, protsessor, tashqarida saqlanayotgan ma’lumotlarga qaraganda, o‘zining ichida saqlanayotgan ma’lumotlar bilan shunchalik samaraliroq ishlaydi. Odatda protsessor o‘zining ichida deyarli hech narsani saqlamaydi. Unda ma’lumotlarga ishlov beriladigan yacheykalar (bu «ishchi» yacheykalar registrlar deb ataladi) juda kam. Shuning uchun protsessor ishini tezlatish uchun ancha oldin (4-avloddan boshlab) keshlash texnologiyasi taklif qilingan.
Kesh – bu bufer vazifasini bajaruvchi xotira yacheykalarining nisbatan katta bo‘lmagan to’plami (nabori)dir. Umumiy xotiradan biror narsa o‘qilayotganda yoki unga yozilayotganda ma’lumotlarning nusxa (копия)si kesh-xotiraga ham kiritiladi. Agar shu ma’lumotlarning o‘zi yana zarur bo‘lib qolsa, ularni uzoqdan chaqirib olish zarur bo‘lmaydi – ularni buferdan olish ancha tezroq bo‘ladi. Kesh-xotiradan foydalanish kompyuter tizimi unumdorligini sezilarli oshirish imkonini berdi. 486-protsessorlar uchun keshlash texnologiyasi birinchi marta qo‘llanilganda, kesh-xotira onalik platasida protsessorga mumkin qadar yaqinroq joylashar edi; bunda sig‘imi katta bo‘lmasa ham, lekin unumdorligi bo‘yicha eng «tez» mikrosxemalardan foydalanishar edi.
Bugungi kunda kesh-xotira «piramidali» o‘rnatiladi. Tezligi bo‘yicha eng tezkor, lekin hajmi bo‘yicha eng kichik birinchi darajali kesh-xotira protsessor kristalli tarkibiga kiradi. Ularni protsessor registrlari tayyorlanadigan texnologiya bo‘yicha tayyorlashadi, natijada u juda qimmat, lekin juda tezkor va eng asosiysi ishonchli bo‘lib qoldi. Uning o‘lchami atigi bir necha o‘n Kbayt bilan o‘lchanadi, lekin u tez ishlov berishda juda katta ahamiyatga ega. Ikkinchi daraja kesh-xotirasi protsessorning o‘sha kristallining o‘zida joylashishi mumkin (bu holda u protsessori yadrosi chastotasida ishlaydi). Odatda ikkinchi daraja kesh-xotira hajmi yuzlab Kbaytda (128/256/512 Kbayt va h.k.) o‘lchanadi.
Eng katta, lekin eng sekin kesh-xotira – bu uchinchi daraja keshidir. U protsessorga kirmaydi, chunki onalik platasida o‘rnatiladi va uning chastotasida ishlaydi. Uning o‘lchamlari 1-2 Mbaytga yetishi mumkin. Birinchi va ikkinchi daraja kesh-xotira o‘lchami protsessor narxiga juda katta ta’sir qiladi. Bir modelli va berilgan ishchi chastotali protsessorlar kesh-xotira hajmi bilan farqlanishi mumkin.
Dasturlashda cache-oblivious algoritmlar protsessorning keshini (inglizcha kesh) kesh hajmiga (yoki kesh satrlarining uzunligiga) bog’lamasdan ishlatadigan tarzda yaratilgan algoritmlardir. Optimal cache-oblivious algoritm o'zgaruvchan omillarni hisobga olmagan holda asimptotik ma'noda keshni optimal ravishda ishlatadigan cache-oblivious algoritmdir. Bunday algoritmlar turli xil xotira darajalaridagi kesh hajmidan qat'iy nazar har xil mashinalarda samarali va modifikatsiyasiz ishlaydi.
Oddiy cache-oblivious algoritmlar: matritsani ko'paytirish, tashqi tartiblash, matritsani transpozitsiyasi va boshqa ba'zi vazifalar. Odatda, cache-oblivious algoritmlar “ajrat va hukmronlik qil” usulidan foydalanadi, bunda vazifa kichik vazifalar va quyi qismlarga bo'linadi. Ajratish jarayonida biz kichik vazifalarga ega bo’lamiz. Bir muncha vaqt o'tganda, ushbu kichik vazifalar kesh hajmiga moslasha boshlaydi, biz ularning qachon moslashishini bilmaymiz, lekin eng kichik asos o'lchamlarga bo'lishda davom etamiz.
Keyin kichik vazifa uchun samarali algoritmni qo'llaymiz. Shundan so’ng natijalarni asosiy vazifaning mohiyatiga qarab birlashtiramiz. Masalan, matritsani ko’paytirishning cache-oblivious algoritmi har bir matritsani to'rtta kichik matritsaga rekursiv ravishda bo'lish orqali hosil bo’ladi. Matritsa to’liq holda keshga joylashganda kichik masalalarga mo’ljallangan optimallashtirilgan algoritmdan foydalanamiz, keyinchalik funktsiyalar natijasini matritsaga qo'shamiz.
Rekursiya deb shundаy kоnstruktsiyagа аytilаdiki, funktsiya o‘zini o‘zi chаqirаdi. To‘g‘ri vа nisbiy rekursiya аjrаtilаdi. Funktsiya to‘g‘ri rekursiv deyilаdi, аgаr tаnаsidа o‘zigа murоjааt bo‘lsа. Funktsiya bоshqа funktsiyani chаqirsа vа bu funktsiya o‘z nаvbаtidа birinchi funktsiyani chаqirsа, bundаy funktsiya nisbiy rekursiv deyilаdi.
Quiksort – tez saralash algoritmi “ajrat va hukmronlik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo’lib, o’rtacha N*log2N ta solishtirish natijasida saralaydi. Algoritm berilgan massivni saralash uchun uni 2 taga bo’lib oladi. Bo’lib olish uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi.
Lekin o’rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma’qul. Tanlangan kalit elementga nisbatan chapdagi va o’ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o„ng tomonga o’tkaziladi. Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya’ni bu oraliqlarning o’rtasidagi elementlar kalit sifatida olinadi va h.k.
Stekning implementasiyasi ikki xil usulda bajarilishi mumkin. Zanjir(Linked) va Massiv.
Zanjir yoki Linked Stek. Stekdagi barcha element o’zidan keyingi elementga bo’glangan bo’ladi va ushbu ketma-ketlik yordamida stekdagi “top” elementni aniqlab olamiz. Ushbu usulda yaratilga Stekning vaqt murakkabligi quyidagi jadvalda berilgan.

Barcha amallarni asosini o’zlashtirish amali tashkil qilgani sababi barcha metodlar \(O(1)\) vaqtda bajariladi.
Massivga asoslangan Stek. Massivning qulayliklaridan biri bu indeks orqali massivda joylashgan elementni vaqtda qaytara olishdir. Lekin massivdagi elementlar soni ko’payib ketsa qimmatbaho amal – hajmni kengaytirish lozim bo’ladi. O’z hajmini o’zi o’zgartira oladigan massiv dinamik massiv deyiladi.

Nazariyaga ko’ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize()ning chaqirilish ehtimolligi har chaqirilgandan so’ng pasayib boradi. Natijada, yuqoridagi metodni vaqt murakkablikka ega deb qabul qilishimiz mumkin.