4-Maruza Kontekst-erkin tillar. Reja: Xeshlash usullari

---

4-Maruza Kontekst-erkin tillar. 
Reja: 
1.
 
Xeshlash usullari . 
2.
 
Dasturning mashinaga bog‘liq va bog‘liq bo‘lmagan optimizatsiyasi.
3.
 
Algoritmik til operatorlarining jadval ko‘rinishda ifodalash usuli. 
 
Tayanch so’z va iboralar: 
Xeshlash usullari , optimizatsiyasi, Algoritmik til .
 
 
1.
Jadvallarni to‘ldirish va qidirish vaqti logarifmik bog‘lanishi bu juda 
yaxshi lekin identifikatorlar soni judayam katta bo‘lishi mumkin bu xoldi boshqa 
usullar qo‘llashga to‘g‘ri keladi. 
Xesh-funksiyalarni qo‘llash usullari yaxshi natijaga olib keladi. 
R elementlar to‘plamini Z butun musbat sonlar to‘plamiga aks ettiruvchi
funksiya . Xesh funksiya deb nomlanadi. Kiruvchi elementlar to‘plami xesh 
funksiyani aniqlash soxasiga kiradi. Xesh funksiyani qiymat soxasi deb to‘plam 
qismi M deyiladi . Xesh funksiyani aniqlash soxasini qiymatlar to‘plamiga aks 
ettirish jarayoni xeshlattirish deb taqdim qilinadi. 
Identifikatorlar jadvallar ustida ishlaganda xesh funksiya identifikatorlarni 
butun sonlarga aks ettirishi kerak. Shunda xesh funksiyani aniqlash soxasi barcha 
identifikatorlar nomlari bo‘ladi. Xesh adreslashda xesh funksiyani qiymati birorta 
berilganlar massivni elementlarini adresi deb xisoblanadi. Bundan ko‘rinib 
turibdiki massivni o‘lchovi fuksiyani qiymatlar soxasiga teng bo‘lishi kerak. Yani 
xesh funksiyani maksimal qiymati kompyuter xotirasida oshib ketmaslik kerak. 
Jadvalni tuzish kuyidagicha bo‘ladi, joriy elementni xesh-funksiyasi xisoblanadi. 
Hisoblangan qiymat elementni joylashtiradigan yacheykani adresini beradi.
A
1 
F
A
2 
A
1 
A
3 
A
3 
A
2 
F
?
n
1 
n
2 
n
3 
m
Хэш-функция
Идентификаторлар
Жадвал
Қидириш
Қидириш 
натижаси

---

Shunday qilib xar qanday identifikator uchun uni xesh funksiyasini xisoblash 
yetarli va shu yacheykaga identifikator yuklanadi. 
Qidirishda xam elementni xesh funksiyasi xisoblanadi va shu adres bo‘yicha 
yacheyka bo‘shligi tekshiriladi agar bo‘sh bo‘lmasa element jadvalda bor aks xolda 
bunday element yo‘q. Rasmda xesh-funksiyani ishlash prinsipi ko‘rsatilgan. 
Bu usul juda yaxshi chunki elementni jadvalga yuklashga va qidirishga 
ketgan vakt funksiyani xisoblashi bilan o‘lchanadi bu juda kamdir. 
Bu usulni ikkita kamchiligi bor: 
Birinchidan xotirani noeffektiv ishlatish , chunki massivni o‘lchovi 
funksiyani qiymatlar soxasiga teng bo‘lishi kerak, aksincha real identifikatorlar 
soni ancha kam bo‘lishi mumkin.
Ikkinchidan yaxshi qanoatlantiradigan xesh-funksiyani tanlash muammosi. 
Xesh funksiyani xar xil variantlari mavjud. Xesh funksiyada ko‘pincha 
belgilar ketmaketligi ustidan biror arifmetik yoki mantiq amallar bajariladi. 
Masalan deylik satrdagi birinsi belgini aski qodini natija qilib olish mumkin 
masalan A harfni kodi 65 mana shu qiymat xesh funksiyani qiymati deb xisoblasa 
bo‘ladi. Lekin bunday xesh funksiyada yangi muammo paydo bo‘ladi ikkita har xil 
identifikatorlar bir xil harfdan boshlansa ularni xesh funksiya qiymati bir xil bo‘lib 
qoladi. Bu xolda bitta yacheykaga ikkita identifikatorlarni joylashtirish kerak 
bo‘ladi bu albatta mumkin emas. Ikki yoki ko‘p identifikatorlarni xesh funksiyasi 
bir xil qiymatga ega bo‘lgan xolat kolliziya deb nomlanadi.
Albatta kolliziyaga ega bo‘lgan funksiyalarni to‘g‘rima to‘gri ishlatib 
bo‘lmaydi. Nazariy kolliziyaga ega bo‘lmagan funksiyalarni tuzish mumkin 
masalan xar bir harfni kodini ketma ket yozilib chiqilsa xosil bo‘lgan son adresni 
ko‘rsatishi mumkin , lekin bunday fuksiya uchun massivdi uzunligi cheksiz bo‘lib 
qoladi, vaxolanki kompyuter xotirasi cheklangan, bundan xulosa qilish mumkinki 
kolliziyadan kutulish ilojisi yuk , shuning uchun kolliziyani ishlatadigan usullar 
qo‘llash kerak. 
Rexeshlash usuli. 
Bu muammani yechish usullardan biri rexeshirlash usulidir. 
Biror element A uchun nhh(A) xisoblanadi, agar shu adres bo‘yicha xotira 
yacheykasi band bo‘lsa , n1qh1(A) funksiya qiymati xisoblanadi agar bu adres xam 
band bo‘lsa element bo‘lsa n2=h2(A) fuksiya xisoblanadi, va xokazo qachonki 
bo‘sh adres topilmasa yoki ni=n teng bo‘lib qolsa, bu xolda jadval to‘lgan deb 
xisoblanadi va xato beradi. Bu usulda identifikatorlar jadvali bo‘sh belgisi bilan 
to‘ldirilishi kerak masalan “” yoki NULL bilan. 
H funksiya kuyidagi formula bilan yozilishi mumkin hi=(h(A) +pi)mod Nm , 
bunda pi – qandaydir formula bilan xisoblanadigan son, Nm - identifikator 
jadvalidagi elementlar maksimal soni. Eng sodda usuli pi=i 
Shunda formulamiz kuyidagicha bo‘ladi hi=(h(A)+i) mod Nm. Bu xolda xesh 
funksiyani qiymati bir xil bo‘lsa, h(A) o‘rindan boshlab ketma-ket yacheykalar 
bo‘shligi tekshiriladi. Tanlangan formula uncha yaxshi emas chunki elementlar bir 
joyga to‘planib qoladi. 

---

Misol taraqasida ketma-ket joylashgan n1,n2,n3,n4,n5 jadval yacheykalarni 
ko‘raylik va A1,A2,A3,A4,A5 identifikatorlarni jadvalga yuklaylik. Funksiyalar 
h(A1)=h(A2)=h(A5)=n1, h(A3)=n2, h(A4)=n4 teng bo‘lsin. 
Natijada A1 elementni qidirish uchun fakat bitta solishtirish yetarli, A2 uchun 
2, A3 uchun 2, A4 uchun 1 va A5 uchun 5 solishtirish kerak bo‘ladi. Bundan 
ko‘rinib turibdiki solishtirishlar soni kolliziyaga bog‘liqdir , kancha kolliziya kam 
bo‘lsa shunchalik solishtirishlar xam kam bo‘ladi. Undan tashqari shunday r 
qiymat topish kerakki u kolliziyani jadval bo‘yicha jipslashtirmasdan keng 
tarqatishi kerak. Shunday usuldan biri r tasodifiy sonlar bo‘lishi. Ko‘paytma
ko‘rinishdagi xesh funksiya hiq(h(A)*i)mod Nm xam yaxshi natija beradi. 
2. To‘rt xil optimizatsiya uchun mumkin bo‘lgan algoritmlarni ko‘raylik. 
A. Umumiy ifodaostilarni o‘chirish. 
O‘chiradigan algoritm quyidagilarni amalga oshirishi kerak: 
1)
Matritsani shunday shaklda hosil qilish kerakki, unda umumiy bo‘lgan 
ifodaostilarni aniqlash mumkin bo‘lsin. 
2)
Ikkita ifodaostilarni ekvivalentligini aniqlansin.
3)
Ulardan bittasini o‘chirilsin. 
4)
O‘chirilgan elemenlarni inobatga olgan holda matritsa o‘zgartirilsin. 

---

Berilgan operator ustida modifikatsiya amalg oshirilgandan keyin yangi bir 
umumiy ifodaostilar paydo bo‘lganligini aniqlash uchun optimallashtirish algoritm 
yana ishlatilishi mumkin.
Umumiy ifodaostilarni izlash uchun algoritm quyidagicha bo‘lishi mumkin: 
1)
‘+’ va ‘*’ operandlari alfavit bo‘yicha tartiblansin, ya’ni o‘ng tomonda tartibi 
past, operatordan o‘ng tomonda ratibi yuqorisi joylashsin (bizning holda 
M3 va M4 o‘zgaruvchilar o‘rni almashtiriladi). 
2)
Operator chegarasini topish. (Bizning holda ular = belgisi bilan ajraladi) 
3)
Umumiy ifodaostilarini topish (M2 ni M3,M4,M5 bilan solishtirish orqali. 
Agar M3 to‘g‘ri kelsa, u M2 va M4 ko‘rsatkichlarini ulash orqali o‘chiriladi) 
4)
Natijaviy matritsada M3 elementga ko‘rsatkichni M2 o‘tkazish orqali 
o‘chirish
5)
Hosil bo‘lgan matritsa yana umumiy ifodaostilarni topish uchun tekshirish 
1-5 punktlarni bajarish. 
6)
B. Kompilyatsiya paytida hisoblash.

---

Optimizatsiyalashning eng sodda algoritmlaridan biri – shunday operatorni topish 
kerakki uning operatorlari literallar bo‘lsin. Agar bunday operatsiya topilsa, u
hisoblanadi, yangi literal paydo bo‘ladi. Matritsadagi literalga ko‘rsatkich yangi 
literalga ko‘rsatkich bilan almashtiriladi. Xuddi shu usulda matritsa yana qarab 
chiqiladi, yangi literalli operatorni topish maqsadida. 
Quyidagi rasmda A=2*276/92*B ifodasini soddalashtirish misoli keltirilgan. 
V. 
Bul ifodalarini optimallashtirish. 
Diskret matematikadagi formulalarni almashtirish qoidalaridan foydalangan 
holda ifodalani soddalashtirish mumkin. 
G. Invariant hisoblashlarni takrorlashdan tashqariga chiqarish. 
Takrorlash tanasidagi hisoblash takrorlashda o‘zgarmaydigan o‘zgaruvchiga 
bog‘liq bo‘lsa, bu hisoblashni takroralashdan tashqariga chiqarish mumkin. Bunda 
quyidagi masalalar yuzaga keladi. 
a)
Invariant hisoblashni anglash. 
b)
Invariant hisoblashni chiqarish joyini aniqlash. Odatda bunday 
hisoblashlarni takrorlash boshlanishi oldiga quyish zarur bo‘ladi. Shu 
sababli matritsadagi takrorlash boshlanishi nuqtasini topish zarur 
bo‘ladi.
c)
Invariant hisoblarni chiqarish. Umumiy ifodaostilarni o‘chirish usulidan 
foydalangan holda takrorlash ichidagi invariant hisobni o‘chirish zarur 
bo‘ladi. 
3.
Kompilyatorda ikki turdagi optimizatsiya farilanadi: mashinaga bog‘liq 
mashinaga bog‘liqmas. Mashinaga bog‘liq optimizatsiya generatsiya qilinuvchi 
buyruqlar bilan uzviy bog‘liq va shu sabali u kod generatsiyasi fazasini ham o‘z 
ichiga oladi.
Matritsa – bu optimizatsiya fazasida foydalaniladigan asosiy beriaganlar bazasi 
hisoblanadi. Matritsaga yangi elementlarni qo‘shish, o‘chirish jarayonini 
yangillashtirish uchun uning har bir satri (elementi) quyidagi ma’lumotlparga ega 
bo‘ladi: elementning bog‘langan zanjirdagi o‘rnini ifodalash uchun to‘g‘ri va 
teskari ko‘rsatkichlar.
To‘g‘ri ko‘rsatkich kodlarni generatsiya qilish fazasida matritsani to‘g‘ri 
yo‘nalishda qarashga imkon beradi. Teskari ko‘rsatkich esa optimizatsiya uchun 
zarur bo‘ladigan matritsani teskari qarab chiqishga imkon beradiki, undan, 

---

masalan, takrorlash tanasi nisbatan invariant hisoblashni kiritish uchun. Matritsa 
elementi quyidagi ko‘rinishga ega. 
Bu yerda to‘g‘ri ko‘rsatkich matritsaning navbatdagi elementi adresini, 
teskari ko‘rsatkich – oldingi element adresini ko‘rsatadi. 
Identifikatorlar jadvali kerak bo‘lmagan vaqtinchalik xotirani o‘chirish va 
identifikatorlar haqidagi ma’lumotlarni olish uchun zarur bo‘ladi. 
Literallar jadvali – optimizatsiyaning ayrim turlarida beriladigan yangi 
literallarni o‘zida saqlaydi. 
Nazorat savollari 
1.
Xeshlash usullari xaqida tushuncha? 
2.Dasturning mashinaga bog‘liq va bog‘liq bo‘lmagan optimizatsiyasi xaqida ? 
3.Algoritmik til operatorlarining jadval ko‘rinishda ifodalash usulini tushuntiring?