Nega ma'lumotlar tuzilmalari va algoritmlarni o'rganish kerak?
Norasmiy tarzda aytganda, algoritm muammoni hal qilish qadamlarining bayonidan boshqa narsa emas. Ular mohiyatan yechimdir.
Masalan, faktorial masalasini hal qilish algoritmi quyidagicha ko'rinishi mumkin:
Muammo: n sonining faktorialini topish
fact = 1 deb boshlaymiz
1 dan n gacha bo'lgan har bir v qiymati uchun:
fact ni v ga ko'paytiramiz
natijada fact n ning faktorialini saqlaydi
Bu yerda algoritm so'zlar bilan yozilgan. Agar u dasturlash tilida yozilsa, biz uni kod deb ataymiz. Quyida Go tilida sonning faktorialini topish kodi keltirilgan:
func factorial(n int) int {
fact := 1
for v := 1; v <= n; v++ {
fact = fact * v
}
return fact
}
Dasturlash — bu to'liq ma'lumotlar tuzilmalari va algoritmlardan iborat. Ma'lumotlar tuzilmalari (data structures) ma'lumotlarni saqlash uchun, algoritmlar (algorithms) esa ushbu ma'lumotlar yordamida muammoni hal qilish uchun ishlatiladi.
Ma'lumotlar tuzilmalari va algoritmlar (DSA) standart muammolarning yechimlarini batafsil o'rganadi va ularning har biridan foydalanish qanchalik samarali ekanligi haqida tushuncha beradi. Shuningdek, u sizga algoritm samaradorligini baholash fanini o'rgatadi. Bu sizga turli xil yechimlar orasidan eng yaxshisini tanlash imkonini beradi.
Vaqt juda qimmatli.
Faraz qilaylik, Alisa va Bob dastlabki 10¹¹ ta natural sonning yig'indisini topish kabi oddiy masalani yechishga harakat qilmoqda. Bob algoritm yozayotgan paytda, Alisa uni amalda kodga aylantirdi.
Algoritm (Bob tomonidan):
sum = 0 deb boshlaymiz
1 dan 10^11 gacha bo'lgan har bir natural n soni uchun:
n ni sum ga qo'shamiz
sum sizning javobingizdir
Kod (Alisa tomonidan):
func findSum() int64 {
var sum int64 = 0
for v := int64(1); v <= 100000000000; v++ {
sum += v
}
return sum
}
Alisa va Bob deyarli hech qancha vaqt ketkazmasdan o'z yechimlarini yaratganliklaridan xursand bo'lishdi. Keling, ularning ish maydoniga nazar tashlaymiz va suhbatini tinglaymiz:
Alisa: Qani, bu kodni ishga tushiraylik va yig'indini bilib olaylik.
Bob: Men bu kodni bir necha daqiqa oldin ishga tushirgan edim, lekin u hali ham natijani chiqarmayapti. Unga nima bo'ldi?
Afsuski, nimadir noto'g'ri ketdi! Kompyuter eng aniq (deterministik) mashinadir. Orqaga qaytib, uni qayta-qayta ishga tushirish foyda bermaydi. Shuning uchun, keling, ushbu oddiy kodda nima noto'g'ri ekanligini tahlil qilaylik.
Kompyuter dasturi uchun eng qimmatli ikki resurs — bu vaqt va xotira.
Kompyuter tomonidan kodni bajarish uchun sarflanadigan vaqt:
Kodni bajarish vaqti = ko'rsatmalar soni * har bir ko'rsatmani bajarish vaqti
Ko'rsatmalar soni siz yozgan kodga, har bir kodni bajarish vaqti esa kompyuteringiz va kompilyatoringizga bog'liq.
Ushbu holatda, bajarilgan jami ko'rsatmalar soni (deylik x):
x = 1 + (10¹¹ + 1) + (10¹¹) + 1, ya'ni x = 2 * 10¹¹ + 3
Faraz qilaylik, kompyuter bir soniyada y = 10⁸ ta ko'rsatmani bajara oladi (bu mashina konfiguratsiyasiga qarab farq qilishi mumkin). Yuqoridagi kodni bajarish uchun ketadigan vaqt:
y ta ko'rsatmani bajarish vaqti = 1 soniya
1 ta ko'rsatmani bajarish vaqti = 1 / y soniya
x ta ko'rsatmani bajarish vaqti = x * (1/y) soniya = x / y soniya
Demak, kodni bajarish vaqti = x / y = (2 * 10¹¹ + 3) / 10⁸ (33 daqiqadan ko'proq)
Alisa va Bob ushbu kodni har safar ishga tushirganda 33 daqiqa kutmasliklari uchun algoritmni optimallashtirish mumkinmi?
To'g'ri usulni allaqachon topdingiz deb o'ylaymiz. Dastlabki N ta natural sonning yig'indisi quyidagi formula bilan beriladi:
Sum = N * (N + 1) / 2
Buni kodga aylantirish quyidagicha ko'rinadi:
func sum(N int64) int64 {
return N * (N + 1) / 2
}
Ushbu kod atigi bir nechta ko'rsatmada bajariladi va qiymat qanchalik katta bo'lishidan qat'i nazar vazifani bir zumda bajaradi. U koinotdagi jami atomlar sonidan katta bo'lsa ham, natijani darhol hisoblab beradi.
Bu holda masalani yechish uchun ketadigan vaqt 1/y (taxminan 10 nanosoniya) ni tashkil etadi.
Eslatma: Ko'paytirish va bo'lishni hisoblash uchun kompyuterga bir nechta ko'rsatma kerak bo'ladi. Tushunish oson bo'lishi uchun bu yerda soddalashtirib ko'rsatildi.
Scalability (masshtablanuvchanlik) — bu algoritm yoki tizimning kattaroq hajmdagi muammolarni yecha olish qobiliyatidir.
Tasavvur qiling, 50 nafar talaba uchun dars xonasi tashkil qilish kerak. Eng oddiy yechimlardan biri — xonani band qilish, doska va bir nechta bo'r olish. Masala hal bo'ldi.
Ammo muammo hajmi oshsa-chi? Talabalar soni 200 nafarga yetsa-chi? Yechim hali ham o'z kuchida qoladi, lekin ko'proq resurslar talab qilinadi. Bu holatda sizga ancha katta zal (ehtimol teatr zali), proyektor ekrani va raqamli qalam kerak bo'ladi.
Talabalar soni 1000 nafarga yetsa-chi? Muammo hajmi oshganda yechim ish bermay qoladi yoki haddan tashqari ko'p resurs sarflaydi. Demak, sizning yechimingiz masshtablanuvchi emas edi.
Unda qanday yechim masshtablanuvchi hisoblanadi?
Khan Academy kabi platformani ko'ring: millionlab talabalar bir vaqtning o'zida videolarni ko'rishlari, topshiriqlarni bajarishlari mumkin va ortiqcha bino talab qilinmaydi. Demak, yechim resurslar cheklangan sharoitda ham kattaroq hajmdagi muammolarni hal qila oladi.
Agar dastlabki N ta natural sonning yig'indisini topish bo'yicha birinchi yechimimizni ko'rsangiz, u masshtablanuvchi emas edi. Chunki muammo hajmining chiziqli o'sishi bilan vaqt ham chiziqli ravishda o'sib bordi. Bunday algoritmlar chiziqli masshtablanuvchi algoritmlar deb ataladi.
Bizning ikkinchi yechimimiz esa juda yaxshi masshtablanuvchi bo'lib, kattaroq hajmdagi muammoni hal qilish uchun ortiqcha vaqt talab qilmadi. Ular konstant vaqtdagi (constant-time) algoritmlar deb ataladi.
Xotira doim ham cheksiz bo'lavermaydi. Juda ko'p ma'lumotlarni saqlash yoki ishlab chiqarishni talab qiladigan tizimlar bilan ishlaganda, algoritm imkon qadar xotiradan tejamkor foydalanishi juda muhim. Masalan: Odamlar haqidagi ma'lumotlarni saqlashda ularning yoshini emas, faqat tug'ilgan sanasini saqlash orqali xotirani tejash mumkin. Yoshni esa tug'ilgan sana va joriy sana orqali kerak bo'lganda osongina hisoblab olish mumkin.
Algoritmlar va ma'lumotlar tuzilmalarini o'rganish sizga nimalar qilish imkonini berishiga ba'zi misollar:
Muayyan yosh guruhidagi odamlarni topish kabi masalalar Binary Search (Ikkilik qidiruv) algoritmining biroz o'zgartirilgan versiyasi bilan osonlikcha hal qilinishi mumkin (ma'lumotlar saralangan deb hisoblaganda).
Barcha odamlarni birma-bir ko'rib chiqadigan oddiy algoritm chiziqli masshtablanadi. Ikkilik qidiruv esa logarifmik masshtablanuvchi algoritmdir. Bu shuni anglatadiki, agar muammo hajmi kvadrat darajaga oshsa, uni hal qilish vaqti faqat ikki barobarga oshadi.
Faraz qilaylik, 1000 kishilik guruhdan ma'lum bir yoshdagi odamlarni topish uchun 1 soniya ketadi. Unda 1 million kishilik guruh uchun:
Xuddi shu ikkilik qidiruv algoritmi sonning kvadrat ildizini topishda ham qo'llaniladi.
Tasavvur qiling, siz Rubik kubigini yechish dasturini yozyapsiz. Ushbu boshqotirma 43,252,003,274,489,856,000 ta turli holatga ega bo'lishi mumkin! Va bular faqat holatlar! Noto'g'ri holatlarga olib boradigan yo'llar sonini tasavvur qiling.
Yaxshiyamki, ushbu muammoni yechish usulini graf ma'lumotlar tuzilmasi (graph data structure) orqali ifodalash mumkin. Graf algoritmlaridan biri bo'lgan Dijkstra algoritmi bu masalani minimal qadamlarda yechilgan holatga olib kelish imkonini beradi.
DNK genetik ma'lumotni tashuvchi molekuladir. Ular A, C, T va G harflari bilan belgilanadigan kichik birliklardan iborat.
Tasavvur qiling, siz bioinformatika sohasida ishlayapsiz. Sizga DNK zanjirida ma'lum bir pattern (ketma-ketlik) uchrashini aniqlash vazifasi yuklatildi.
Bu kompyuter fanidagi mashhur masaladir. Eng oddiy algoritm quyidagi ko'paytmaga mutanosib vaqt oladi:
(DNK zanjiridagi belgilar soni) * (qidirilayotgan namunadagi belgilar soni)
Odatdagi DNK zanjiri millionlab bunday birliklarga ega. Lekin xavotirlanishga hojat yo'q: KMP algoritmi buni quyidagi yig'indiga mutanosib vaqtda hal qiladi:
(DNK zanjiridagi belgilar soni) + (qidirilayotgan namunadagi belgilar soni)
* operatorining + ga almashishi katta farq qiladi. Agar qidirilayotgan namuna 100 belgidan iborat bo'lsa, sizning algoritmingiz endi 100 barobar tezroq ishlaydi. Agar 1000 belgidan iborat bo'lsa, KMP algoritmi deyarli 1000 barobar tezroq bo'ladi. Ya'ni oddiy usulda 1 soniya ketgan bo'lsa, bu yerda 1 millisoniya ketadi.
Va bunday misollar cheksiz...
Umuman olganda, dasturiy ta'minotni ishlab chiqish har kuni yangi texnologiyalarni o'rganishni talab qiladi. Siz ushbu texnologiyalarning ko'pchiligini loyihalaringizda ishlatish jarayonida o'rganasiz. Biroq, algoritmlar bilan bunday emas.
Agar siz algoritmlarni yaxshi bilmasangiz, hozir yozayotgan kodingizni optimallashtira olishingiz mumkinligini ham seza olmaysiz. Sizdan ularni oldindan bilish va zarur bo'lgan joyda qo'llash talab etiladi.
Biz algoritmlarning masshtablanuvchanligi haqida so'z yuritdik. Dasturiy ta'minot tizimi ko'plab ana shunday algoritmlardan tashkil topadi. Ulardan birortasini optimallashtirish butun tizimning yaxshilanishiga olib keladi.
Shu bilan birga, tizimni masshtablashning yagona yo'li bu emasligini ham bilish muhim. Masalan, taqsimlangan hisoblash (distributed computing) usuli dasturning mustaqil qismlarini bir vaqtning o'zida bir nechta mashinalarda bajarish imkonini beradi va uni yanada masshtablanuvchan qiladi.