Ajrat va xukmronlik qil” tilidagi algoritmlar. Reja: Ajrat va hukmronlik qil usuli

Ajrat va hukmronlik qil paradigmasi dasturlashning mashhur algoritmlari asosini tashkil qiladi:

• 
  Quick Sort
  

• 
  Merge Sort
  

• 
  Eng yaqin ikki nuqta (Closest two points)
  

• 
  Strassen ko’paytirishi (Strassen multiplication)
  

• 
  Karatsuba algoritmi (Karatsuba algorithm)
  

• 
  Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
  

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  

Ajrat va hukmronlik qil paradigmasining afzalliklari

• 
  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. Masalan: oddiy saralash bo’lgan Bubble Sortning tezligi O(n²) bo’lsa, MergeSortniki O(n*logn)
  

• 
  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o’zgarishsiz ishlatish mumkin
  

• 
  bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o’zida turib yechish mumkin bo’ladi.
  

• 
  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko’paytirish algoritmlarida)
  

Ajrat va hukmronlik qil paradigmasi kamchiliklari

• 
  bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu ularni ishlashini ma’lum miqdorga sekinlashtiradi. Buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin.
  

• 
  asosiy shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi
  

2. Kesh xotira bilan ishlash
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.