Ajratkichlar va ajratish masalasi. Ajratkichlarning ko‘rinishlari. Chekli avtomatlar

Maslahat: Vaqt o'tishi bilan, fayl tizimi ma'lumotni saqlash, saqlash va saqlash qurilmasidan yo'q qilish sababi, faylning turli qismlari o'rtasida muqarrar ravishda yuz beradigan bo'shliqlar tufayli parchalanishiga olib keladi. Buni tuzatish uchun bepul defrag dasturi yordam berishi mumkin.
Fayllarni tashkillashtirish uchun tuzilmasdan, o'rnatilgan dasturlarni olib tashlash va maxsus fayllarni olish mumkin bo'lmay qolmaydi, lekin har ikkala narsa bir xil papkada bo'lishi mumkin, chunki har ikkala fayl bir xil papkada bo'lishi mumkin foydali).
Eslatma: Xuddi shu nomdagi fayllar orqali rasmga o'xshaydi. IMG123.jpg fayli yuzlab papkada mavjud bo'lishi mumkin, chunki har bir jild
ad
JPG faylini ajratish uchun ishlatiladi, shuning uchun ziddiyat yo'q. Biroq, fayllar bir xil katalogda bo'lsa, xuddi shu nomni o'z ichiga olmaydi.
Fayl tizimi faqat fayllarni saqlamaydi, shuningdek, ular haqidagi ma'lumotlar, masalan, tarmoq bloklari o'lchami, parcha ma'lumotlari, fayl hajmi, atributlari , fayl nomi, fayl manzili va katalog ierarxiyasi kabi.
Windows tashqari boshqa operatsion tizimlar ham FAT va NTFS dan foydalanishadi, lekin HFS + kabi iOS va macOS kabi Apple mahsulotlarida ishlatiladigan turli xil fayl tizimlari mavjud. Mavzuga qiziqqan bo'lsangiz, Vikipediya fayl tizimlarining to'liq ro'yxatiga ega.
Ba'zan, "fayl tizimi" atamasi bo'limlarda ishlatiladi. Misol uchun, "mening qattiq diskda ikkita fayl tizimi mavjud" degani diskda NTFS va FAT o'rtasida bo'lishini anglatmaydi, lekin fayl tizimini ishlatadigan ikkita alohida bo'lim mavjud.
Siz bilan bog'laydigan ko'pgina ilovalar ishlash uchun fayl tizimini talab qiladi, shuning uchun har bir bo'lakda bitta bo'lishi kerak. Bundan tashqari, dasturlar fayl tizimiga bog'liq, ya'ni agar u MacOS-da foydalanish uchun tuzilgan bo'lsa, Windows dasturidan foydalana olmaysiz.
3.Identifikatorlar jadvalini tashkil etish usullari. Binar daraxt usuli bo‘yicha identifikatorlar jadvalini qurish. Xesh funksiya va xesh xotira. Xesh adreslash. Zanjir usuli yordamida xesh adreslash.
.Identifikatorlar jadvalini tashkil etishning belgilanishi va
xususiyatlari
Semantikaning to’g’riligini tekshirish va kodni generasiyalash boshlang’ich
tildagi dasturda uchraydigan o’zgaruvchilar, konstantalar, funksiyalar va boshqa
elementlaming xususiyatlarini bilishni talab qiladi. Boshlang’ich dasturda ushbu
elementlar identifikatorlar sifatida belgilanadilar. Boshlang’ich dasturda
identifikatorlar va boshka elementlami ajratish leksik tahlil fazasida amalga
oshiriladi. Ulaming xususiyatlari sintaksis ajratish, semantik tahlil va kodni
generasiyaga tayyorlash fazasida aniqlanadi. Mumkin bo’lgan xususiyatlar va ulami
aniqlash usullari kiruvchi til semantikasiga bog’Iiq. Har qanday ixtiyoriy holda ham
kompilyator barcha topilgan identifikatorlami va ularga bog’Iiq xususiyatlami butun
kompilyasiya jarayoni davomida, kompilyasiya jarayonining turli fazalarida
foydalanish imkoniyatiga ega bo’lish uchun, saqlab turish imkoniyatiga ega bo’lishi
kerak. Ushbu maqsadlar uchun, kompilyatorlarda maxsus berilganlami saqlash
joylari, ya'ni belgilar jadvali yoki identifikatorlar jadvali deb atalgan, jadvallardan
foydalaniladi.
Ixtiyoriy identifikatorlar jadvali maydonlar to’plamidan iborat bo’lib, ulaming
soni boshlang’ich dasturda topilgan turli identifikatorlar soniga teng. Har bir maydon
jadvalning ushbu elementi haqida to’liq ma'lumotni saqlaydi. Kompilyator bitta yoki
bir nechta identifikatorlar jadvali bilan ishlashi mumkin, ulaming soni kompilyatomi
amalga oshirilishiga bog’Iiq. Masalan, boshlang’ich dastuming turli modullari uchun
turli identifikatorlar jadvalini, yoki kiruvchi tilning turli toifali elementlari uchun
tashkil etish mumkin.
Boshlang’ich dastuming identifikatorlar jadvalida saqlanayotgan har bir elementi
uchun ma'lumotlar tarkibi kiruvchi tilning semantikasi va element toifasiga bog’Iiq.
Masalan, identifikatorlar jadvalida quyidagi ma'lumotlar saqlanishi mumkin:
□ o’zgaruvchilar uchun:
O o’zgaruvchi ismi;
O o’zgaruvchining qabul qiluvchi qiymatining toifasi;
O o’zgaruvchi bilan bog’Iiq xotira sohasi;
□ konstantalar uchun:
O konstanta nomi (agar bor bo’Isa);
O konstanta qiymati
O konstanta toifasi (agar talab qilinsa);
□ funksiyalar uchun: ---------------------------- ----- ----------------------- --------
O funksiya ismi;
O funksiyaning formal argumentlari soni va toifasi;
O qaytariluvchi natija toifasi;
146
O funksiyakodi manzili.
Demak, identifikatorlar jadvali - kiruvchi dastur elementlari haqidagi
ma'lumotlami saqlovchi berilganlar to’plami. Bir necha xil identifikatorlar jadvali
mavjud bo’lishi mumkin.
Identifikatorlar jadvali leksik tahlil fazasida tashkil etiladi va ketma-ket
to’ldiriladi. Leksik tahlil fazasida identifikatorlar turlari yoziladi. Kodni
generasiyalashga tayyorgarlik fazasida - xotira ajratiladi.
7.2.Identifikatorlar jadvalini tashkil etishning oddiy usullari
Identifikatorlar jadvalini tashkil etishning eng oddiy usuli elementlami jadvalga
ulaming kelib tushishi bo’yicha joylashtirishdir. U holda identifikatorlar jadvali
ma'Iumotlaming tartibsiz, har bir yacheykasi jadvalning mos elementi haqidagi
ma'lumotlami saqlovchi, to’plamidan tashkil topadi.
Jadvalda kerakli elementni qidirish bu holda, kerakli element topilguniga qadar
qidirilayotgan elementni jadvalning har bir elementi bilan ketma-ket solishtirishdan
iborat tx)’ladi. ::
Identifikatorlar jadvaliini tashkil etishning asosiy kriteriysi bo’lib qidiruv
vaqti hisoblanadi, chunki asosiy funksiyalar yozuvlami qidimv va qo’shishdan
iborat (ko’proq qidiruv amalga oshiriladi).
U holda, agar ikki elementni (ikkita qatomi taqqoslash) solishtirish uchun
kompilyator tomonidan sarf kilingan vaqtni birlik sifatida qabul qilsak, u holda, N
elementni o’zida ifodalovchi jadval uchun o’rta hisobda N/2 ta taqqoslashlar.
bajariladi. Bunday jadvalni to’ldirish juda sodda quyidagicha amalga oshiriladi:.
jadvalning oxiriga yangi elementni (T3) qo’shish va ushbu elementni qo’shish
uchun talab qilinadigan vaqt, jadvaldagi N elementlar sonidan bog’liq emas.
Ammo, agar N katta bo’Isa, u holda qidirish jarayoni ko’pgina vaqt sarflanishini
talab etadi. Bunday jadvalda qidirish vaqti (Tp) ni quyidagicha baholash mumkin:
TP = 0(N).
Identifikatorlar jadvalida qidirish ko’pincha, kompilyator bajarishi kerak
bo’lgan amal hisoblanganligi, va boshlang’ich dasturdagi turli identifikatorlar soni
etarli darajada ko’p bo’lishi sababli (bir necha yuzdan bir necha ming elementgacha),
identifikatorlar jadvalini tashkil etishning bunday usuli foydasiz usul hisoblanadi.
Agar jadvalning elementlari, qandaydir tabiiy tartibga mos ravishda, tartiblangan
bo’lsaqidirishni foydalirok amalga oshirilishi mumkin bo’ladi
Bizning holatda qidirish identifikator ismi bo’yicha, ya'ni alfavit tartibida to’g’ri
yoki teskari yo’nalishda, amalga oshiriladi. Tartiblangan N elementli ro’yxatda foydali
qidirish usuli bo’lib, binar yoki logarifmik qidirish usuli hisoblanadi. Topish kerak
bo’lgan belgini jadval o’rtasida (N+l)/2 element bilan solishtiriladi. Agar ushbu
element qidirilayotgan element hisoblanmasa, u holda biz faqat 1 dan (N+l)/2-l
gacha raqamlangan elementlar blokini, yoki (N+l)/2+l dan N gacha bo’lgan
elementlar blokini qidirilayotgan element solishtirilgan elementdan katta yoki
kichikligiga bog’liq holda, qarab chiqishimiz shart. So’ngra jarayon ikki marta kichik
147
o’lchamli kerakli blok ustida takrorlanadi. Bu holat, yoki element topilguniga qadar,
yoki algoritm bitta yoki ikkita elementli navbatdagi blokga etguniga qadar davom
etadi (qidirilayotgan elementni ushbu elementlar bilan to’g’ridan to’g’ri taqqoslash
mumkin bo’ladi). Har bir qadamda bosh elementni saqlashi mumkin bo’lgan
elementlar soni, ikki marta qisqarganligi sababli, maksimal taqqoslashlar soni
l+log2(N) ga teng bo’ladi. U holda identifikatorlar jadvalidagi elementni qidirish vaqtini
quyidagicha baholash mumkin: Tp - 0(log2 N). N=128 bo’lgan holda, taqqoslash
uchun binar qidirish usulida, eng ko’pi bilan 8 ta taqqoslash talab etilishi mumkin,
tartiblanmagan jadvaldagi qidirish esa, o’rtacha 64 ta taqqoslashni talab etadi. Usulni,
har bir qadamda qaralayotgan ma'lumotlar soni ikki marta qisqarganligi sababli, «binar
qidirish», to’plamdagi kerakli elementni topish vaqti elementlaming umumiy sonidan
logarifmik bog’Iiqlikka ega bo’lganligi sababli, «logarifmik» deb ataladi.
Usulning kamchiligi identifikatorlar jadvalining tartiblanishini talab etilishidir.
Qidirish olib boriladigan ma'lumotlar to’plami tartiblangan bo’lishi kerak bo’lganligi
sababli, uning to’ldirilish vaqti to’plamdagi elementlar soniga bog’liq bo’ladi.
Identifikatorlar jadvali to’ldirilguniga, to’liq to’ldirilganligi, qadar qarab chiqiladi, shu
sababli tartiblanish sharti unga murojaatning barcha bosqichlarida bajarilishi talab
etiladi. Natijada, jadvalni qurish uchun faqat elementlami to’g’ri tartibli qo’shish
algoritmidan foydalanish mumkin.
Jadvalga har bir yangi elementni qo’shish uchun awal ushbu yangi elementni
qaerga joylashtirish joyini aniqlash zarur, so’ngra ma'Iumotni bo’lagini jadvalga
ko’chirishni, agar element uning oxiriga qo’shilmayotgan bo’Isa, bajarish kerak
bo’ladi. Agar tartiblangan to’plamlami tashkil etish uchun qo’llanilayotgan standart
algoritmlardan foydalansak, qo’shish joyini qidirish uchun binar qidirish
algoritmidan foydalansak, u holda jadvalga barcha elementlami joylashtirish uchun
zarur vaqtni quyidagicha baholash mumkin:
T3 = CXN*log2 N) + k*0(№ ).
Bu erda k — berilganlami ko’chirish va komptyuter tomonidan taqqoslashlami
bajarish amallarini vaqti o’rtasidagi moslikni aks ettiruvchi qandaydir koeffisientdir.
Natijada identifikatorlar jadvalida logarifmik qidirishni tashkil etishda kerakli
elementni qidirish vaqtini, jadvalga yangi elementni joylashtirish vaqtini ko’paytirish
hisobiga, sezilarli ravishda qisqartirishga erishamiz. Identifikatorlar jadvaligi yangi
elementlami qo’shish, ularga murojaat etishga nisbatan kam amalga oshirilishini
e'tiborga olsak, ushbu usulni tartiblanmagan usulga nisbatan foydaliroq deb
hisoblashga haqlimiz.
.Binar daraxt usuli bo’yicha identifikatorlar jadvalini qurish
Identifikatorlar jadvalida qidirilayotgan elementni qidirish vaqtini, uni
to’ldirishga sarflanadigan vaqtni ko’paytirmasdan, qisqartirish mumkin. Buning
uchun identifikatorlar jadvalini berilganlaming uzluksiz to’plami ko’rinishida
tashkil etishni rad qilish kerak bo’ladi. Kompilyator kamida yangi identifikatomi
jadvalga qo’shishda identifikator mavjudmi yoki yo’qligini tekshirishi kerak
bo’ladi, chunki ko’pgina dasturlash tillarida bironta ham identifikator bir martadan
ortiq ifodalanishi mumkin emas. SHunday qilib, har bir yangi elcmentni qo’shish
amali uchun bittadan kam bo’lmagan qidirish amalini bajarilishi kerak bo’ladi.
Jadvalni tashkil etishning shunday usuli mavjudki, unda jadval binar daraxt
ko’rinishini oladi. Daraxtning har bir tuguni jadvalning elementi bo’lib, ildiz tugun
esa, jadvalning to’ldirishda uchraydigan, birinchi element hisoblanadi. Daraxt
binar deb ataladi, chunki undagi har bir cho’qqi ikkitadan ortiq shohga ega bo’Iishi
mumkin emas (va, natijada, pastda yotuvchi ikkita cho’qqidan ortiq cho’qqiga ega
emas). Aniqlik uchun ushbu ikki shohni «o’ng» va «chap» deb ataladi.
Binar daraxtni to’Idirish algoritmini qaraymiz. Algoritm, identifikatorlarga ega
bo’lgan kiruvchi ma'lumotlar oqimi bilan ishlaydi deb hisoblaymiz (kompilyatorda
ushbu ma'lumotlar oqimi kiruvchi dastur matnini tahlili jarayonida keltirib
chiqariladi). Birinchi identifikator, daraxtning cho’qqisiga joylanadi. Barcha qolgan
identifikatorlar daraxtga quyidagicha kelib tushadilar. Daraxtni qurish jarayonida
elementlar bir biri bilan solishtiriladi va natijalarga qarab daraxtdagi keyingi yo’l
tanlanadi. Faraz qilaylik, yangi identifikatomi yozish kerak bo’Isin. Buning uchun
chap qismdaraxt tanlanadi, agar ushbu identifikator joriy identifikatqrdan kichik
bo’lsa, agar katta bo’lsa u holda o’ng qismdaraxt tanlanadi. Agar joriy tugun
oxirgi bo’lmasa, u holda keyingi tugunga o’tiladi (tanlangan yo’nalishga asosan)
vayana qo’shilgan identifikatomi joriy identifikator bilan solishtiramiz.
Ushbu usul uchun talab qilingan solishtirishlar soni va olinadigan daraxt
ko’rinishi identifikatorlami qanday tartibda kelib tushishigabog’liq.
Xesh-funksiyalar va xesh-manzillash
Xesh-funksiyalarning ish tamoyillari
Identifikatorlar jadvalini qidirish va to’ldirish vaqtining logarifmik bog’liqligi -
bu identifikatorlar jadvalini turli usullami qo’llagan holda tashkil etib erishilgan eng
yaxshi natijadir. Lekin aniq dasturlarda identifikatorlar soni shu darajada ko’pki,
hattoki qidirish vaqtining ulaming sonidan logarifmik bog’liqligini qonikarli deb
bo’Imaydi.
Xesh funksiyalar va xesh -manzillashdan foydalanilgan usullardan foydalanib
yanada yaxshiroq natijalami olish imkoni mavjud.