Fanidan tayyorlagan referati

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI FARG’ONA FILLIALI TT VA KT FAKULTETI DASTURIY INJINERING YO’NALISHI 650-20-GURUH TALABASI
TURSUNALIYEV FARRUX
DASTURLASH USLUBLARI VA PARADIGMALAR FANIDAN TAYYORLAGAN
REFERATI


MAVZU: 2.3. MALUMOTLAR
TUZULMALARI


Reja;
1. Malumotlar tuzulmasi tushuncha
2. Malumotlar tuzulmasi haqida malumotlar

Ma'lumotlar tuzilmalari

Kompilyatsiya paytida xotirani taqsimlashdan tashqari, dasturlarni bajarish jarayonida xotira bilan ishlash samaradorligini ta'minlaydigan alohida fanlar mavjud:
– yangi – o‘chirish – yig‘ma tipdagi xotira tizimiga dinamik so‘rovlar;
- ixchamlashtirish - katta integral ob'ektlarni joylashtirish uchun makonni siqish;
- "egizaklar" - turli o'lchamdagi bloklarga taqsimlanganda xotirani kengaytirish va uning haddan tashqari parchalanishining oldini olish usuli;
– stek – FILOga kirish intizomi;
- Setl - qayta ishlash xarakteri va bo'sh xotira mavjudligiga qarab to'plamlarni ifodalash uchun SD tomonidan dinamik ravishda tanlangan 17 dan ortiq turli SD.
Ko'pgina dasturlash tizimlarida ma'lumotlar tuzilmalarining odatiy amalga oshirilishi:
– kompilyatsiya paytida elementlarning o‘lchami va turi haqidagi ma’lumotlarni saqlaydigan pasportga ega vektorlar dasturni bajarishda mavjud emas;
- statik aniqlangan kalitlar yordamida turli elementlarning berilgan ro'yxatiga kirishni ta'minlaydigan yozuv yoki tuzilma;
- ma'lum bir manzilda turli vaqtlarda joylashgan turli APlarning berilgan ro'yxatini birlashtirish;
- ishlov berish bit kodlari bo'yicha mashina ko'rsatmalari chegarasidan tashqariga chiqmaydigan oz sonli sanab o'tiladigan elementlar to'plami;
- ikkita kirish intizomiga ruxsat beruvchi stek - FILO va vektor.
Mashinada ro'yxatlar belgilar ketma-ketligi sifatida emas, balki birma-bir bog'langan ro'yxatlarni amalga oshirishda Paskal tilidagi yozuvlarga o'xshash daraxtlarning qismlari sifatida mashina so'zlaridan tuzilgan tizimli shakllar sifatida saqlanadi.
- dastur bilan shug'ullanadigan iboralar hajmi va hatto sonini oldindan aytib bo'lmaydi. Bundan tashqari, ifodalarni joylashtirish uchun qattiq uzunlikdagi xotira bloklarini tashkil qilmaslik mumkin;
- , lekin agar ma'lumotlar chiziqli saqlangan bo'lsa, unda ortiqcha yoki bo'shatilgandan foydalanishni tashkil qiling
hujayra bloklaridan bo'shliqlar qiyin;
– Bir nechta iboralarning davomi boʻlgan iboralar faqat bir marta berilishi mumkin.
Har qanday vaqtda ro'yxatlar uchun ajratilgan xotiraning faqat bir qismi foydali ma'lumotlarni saqlash uchun ishlatiladi. Qolgan hujayralar bepul ro'yxat deb ataladigan oddiy ro'yxatda tashkil etilgan.
Lisp tilida xotira bilan ishlashning eng qiziqarli, inqilobiy mexanizmi bu takroriy xotirani avtomatlashtirish edi.

xotiradan foydalanish - "axlat yig'ish". 1960-yillarning boshidan boshlab bunday ishlarning usullariga ko'plab tadqiqotlar bag'ishlangan bo'lib, ular bugungi kungacha davom etmoqda va Java tilini amalga oshirishda shunga o'xshash mexanizm kiritilganligi sababli ancha faollashdi. Barcha bunday usullarning umumiy g'oyasi juda oddiy: - etarli xotira mavjud ekan, siz bu haqda tashvishlana olmaysiz va yangi ma'lumotlarni yangi xotira bloklariga joylashtirolmaysiz; - agar to'satdan bo'sh xotira bo'lmasa, unda "axlat yig'ish" ni bajarish kerak bo'ladi, uning davomida, ehtimol, dastur uchun keraksiz bo'lib qolgan bloklar paydo bo'ladi; - agar xotira topilsa, uni qayta sarflash mumkin.
"Garbage Collector" maxsus dasturi dasturlash tizimining cheklangan miqdordagi ishchi registrlaridan ko'rinadigan tugunlarni oddiygina belgilash orqali barcha xotira bloklariga kirish imkoniyatini tahlil qiladi. Bunday registrlar hisob-kitoblarning oraliq natijalarini, stekning faol qismini, assotsiatsiyalar ro'yxatini, atomlar jadvalini va boshqalarni o'z ichiga oladi. Belgilangandan so'ng, barcha belgilanmagan tugunlar bo'sh xotira ro'yxatiga birlashtiriladi, bu ularni qayta ishlatish uchun yangi qo'ng'iroqlarga o'tkazadi. CONS funktsiyasi. Bunday avtomatlashtirish kamchiliklardan xoli emas.
Bir qator noxush oqibatlar: hujayralarning keyingi qismini qidirishda oldindan aytib bo'lmaydigan uzunliklar (ish vaqti) va agar bunday qismlar hisoblashni davom ettirish uchun juda kichik bo'lsa, "tizimning haddan tashqari qizishi". Uskunaning ishlashi oshgani sayin, parallel jarayonlar va faol ma'lumotlar tuzilmalarini qo'shimcha xotira bloklariga proaktiv nusxalash asosida xotirani qayta ishlatish uchun oddiy va kamroq og'ir algoritmlar ishlab chiqildi. Bunday usullar murakkab belgilash va erishish imkoniyatini tahlil qilishni talab qilmaydi. Bundan tashqari, topshiriqlarga bo'lgan ehtiyoj deyarli yo'q qilinadi. Ular dasturlarda nomlar bilan almashtiriladi.
Xotira odatda ma'lumotlar tuzilmalarini tashkil etuvchi bir qator so'zlarni o'z ichiga olgan bloklarda taqsimlanadi. Xotiraning jismoniy hajmi, ma'lumotlarning mantiqiy uzunligi va hisob-kitoblarni davom ettirish uchun foydali bo'lgan ma'lumotlarning tarkibi sezilarli darajada farq qilishi mumkin. Xotira bilan ishlash samaradorligidagi yo'qotishlarni minimallashtirish binar daraxtlarni dinamik qayta ishlash orqali ta'minlanadi - ba'zi maydonlarning to'liq bo'lmaganligi sababli ishlamay qolish vaqti yo'q. Bunday daraxtning har bir tugunida ikkita yozilgan ko'rsatgichni (CAR va CDR, chap va o'ng) saqlash uchun etarli bo'lgan kichik joy mavjud. Koʻrsatkich bilan yozish kerak
ma'lumotlar va ularni qayta ishlash operatsiyalari muvofiqligini operativ dinamik nazorat qilish. NIL, atomlar, ro'yxatlar, raqamlar, satrlar - bularning barchasi amalga oshiriladigan farqli ma'lumotlar turlari. Lisp-ning tipsiz ekanligi haqidagi ta'kid eskirgan va endi dasturning bajarilishi dinamikasida tipni boshqarishning to'liqligini tan olish bilan almashtirildi.
Ilgari, tipsizlik dastur matnida o'zgaruvchilar nomlarining qiymat turlari bilan statik bog'lanishning yo'qligi edi. Kompilyatsiya qilish uchun Lisp dasturlari bepul o'zgaruvchilarning qiymat turlari haqidagi ma'lumotlar bilan to'ldirilishi kerak, ammo har bir dastur kompilyatsiya qilish uchun omon qolmaydi. Ma'lumotlar turini avtomatik aniqlashni qo'llab-quvvatlaydigan ilovalar mavjud. Lisp tilida qiymat ma'lumotlari turlarining funktsional tasnifi mavjud, ya'ni. amalga oshirish jihatidan farqlanadi.
Assotsiatsiya ro'yxatidan foydalangan holda tarjimonning yuqoridagi ta'rifining samaradorligi ko'p jihatdan dasturdagi ajralib turadigan atomlar soniga bog'liq. Bunday qaramlik odatda ma'lumotlarga kalit orqali kirishni ta'minlaydigan ajratish funktsiyalari (xesh-funksiyalar) mexanizmi bilan yumshatiladi. Kalit sifatida atom nomi ishlatiladi. Atomning xossalari soni cheklanmagan. Xususiyatlar o'rnatilgan, tizimli yoki dasturchi kiritishi mumkin. Atom qiymatlari, o'rnatilgan operatsiyalar manzillari, funksiya ifodalarini aniqlash o'rnatilgan xususiyatlarga misollardir.

Odatda, mashina so'zlar, baytlar, registrlar kabi sobit o'lchamdagi ma'lumotlar bloklari g'oyasi bilan bog'liq. Funktsional dasturlash va OOP kattaroq konstruktsiyalarga - oldindan cheksiz uzunlikdagi ma'lumotlar tuzilmalariga qaratilgan. Bunday tuzilmalar ierarxik ma'lumotlar strukturasining joriy darajasidagi tarkibiy qismlarning ixtiyoriy soniga ishlov berishga moslashtirilgan maxsus stek yordamida juda samarali amalga oshiriladi. U odatdagi stekdan joriy darajaning oxiriga ko'rsatgichni ajratish bilan farq qiladi. Natijada, stek daraja chegaralariga havolalarni saqlaydi, bu esa istalgan istalgan darajaga qaytishga, xususan, kutilmagan vaziyatlarda qayta ishlash jarayonini tiklashga imkon beradi.
Funktsional dasturlarning sezilarli ishlash zaxirasi sof funktsiyalarning rasmiy analoglari bo'lgan, ammo bajarilganda nojo'ya ta'sirlar bilan birga keladigan halokatli funktsiyalar bilan ta'minlanadi. Ushbu yondashuv, agar kerak bo'lsa, topshiriqlardan foydalanmasdan, oddiygina uslubda tuzatilgan dasturlarning samaradorligini oshirishga imkon beradi.
saqlangan ma'lumotlarga ruxsat etilgan o'zgarishlar chegaralarini aniq biladigan dasturchining javobgarligi ostidagi funktsiyalarning halokatli analoglarini jalb qilish.
Grafik ko'rinishni ro'yxatlarning xotiradagi tasviri bilan bog'lashning bevosita foydasi quyidagi misol yordamida ro'yxatlar bilan ishlaydigan funktsiyalarni ko'rib chiqish orqali ko'rsatilgan: Diagramma tushuntirish