External Sort — Saralanadigan ma’lumot operativ xotiraga sig‘maganda disk yoki boshqa tashqi xotiradan foydalanib tartiblash usullari oilasi. Bu tushuncha algoritmlar va ma’lumotlar tuzilmalarida natijani aniq ifodalash, murakkablikni tahlil qilish hamda muqobil yechimlarni solishtirish uchun ishlatiladi.
Matematik ifoda
External merge sort kirishni xotiraga sig‘adigan bloklarga bo‘ladi, har blokni ichki saralab run fayllar yaratadi, so‘ng ularni ko‘p yo‘lli merge bilan birlashtiradi. Bufferlar ketma-ket I/O ni ko‘paytirib, tasodifiy disk murojaatini kamaytiradi.
External Sortni tushunishda uning matematik ta’rifi bilan dasturiy ko‘rinishini ajratish muhim. Matematik model qaysi obyektlar va munosabatlar ruxsat etilishini belgilaydi; implementatsiya esa ularni massiv, ro‘yxat, xarita yoki boshqa tuzilma orqali saqlaydi. Bir xil model turli xotira va vaqt xususiyatlariga ega ko‘rinishlarda amalga oshirilishi mumkin. Shuning uchun “to‘g‘ri” tanlov faqat ta’rifga emas, bajariladigan so‘rovlar, kirish hajmi va yangilanish chastotasiga ham bog‘liq.
Hisoblashdagi vazifasi
Ma’lumotlar omboridagi ORDER BY, loglarni vaqt bo‘yicha tartiblash, katta indeks qurish va batch ETL External Sortdan foydalanadi. Fan-in miqdori mavjud xotira va ochiq fayl deskriptorlari bilan cheklanadi; bir necha merge bosqichi talab qilinishi mumkin.
External Sortning foydasi faqat yakuniy javob bilan o‘lchanmaydi. U masalani qaysi qismlarga ajratish, qaysi invariantni saqlash va natijani qanday tekshirish mumkinligini ham ko‘rsatadi. Algoritm tanlanganda preprocessing, asosiy so‘rov, yangilash va natijani tiklash xarajatlari alohida baholanadi. Bir martalik hisoblash uchun ma’qul usul doimiy yangilanadigan xizmat uchun qimmat bo‘lishi mumkin.
Chegaralar va talqin
Asosiy xarajat CPU taqqoslashidan ko‘ra o‘qilgan va yozilgan bloklar sonidir. Vaqtinchalik joy odatda ma’lumot hajmiga yaqin bo‘lishi mumkin. Jarayon uzilsa run fayllarni aniqlash, tozalash yoki checkpointdan davom ettirish siyosati zarur.
External Sort bilan ishlovchi dastur kirish shartlarini aniq tekshirishi kerak. Tugun yoki element identifikatorlari, yo‘nalish, vazn, tenglik va dublikat qoidalari oldindan kelishilmasa, nazariy jihatdan to‘g‘ri algoritm noto‘g‘ri model ustida ishlashi mumkin. Testlar minimal holat, bo‘sh kirish, uzilgan yoki takroriy ma’lumot, teng qiymatlar va eng yomon tartibni qamrab oladi. Katta kirishda natijaning o‘zi bilan birga xotira sarfi, bajarilish vaqti va I/O hajmi ham o‘lchanadi.
Kichik misol
100 GB fayl va 1 GB ishchi xotirada taxminan yuzta boshlang‘ich run hosil bo‘ladi. Yetarli fan-in bo‘lmasa ular avval guruhlarda, keyin yakuniy bosqichda birlashtiriladi.
Amaliy hujjatda External Sort uchun kuzatiladigan kafolatlar alohida yoziladi: natijaning aniqligi, deterministikligi, murakkablik chegarasi va xato holatidagi xatti-harakat. Nazariy Big O bahosi kirish o‘sgandagi tendensiyani beradi, lekin kesh lokaliteti, disk murojaati va ma’lumot taqsimoti real tezlikka ta’sir qiladi. Shu bois kichik etalon implementatsiya bilan natijani solishtirish, so‘ng real ish yukida profil olish ishonchli tekshiruv usulidir.
+## Invariantlarni tekshirish
Har run ichida tartib, merge natijasida esa global tartib va kirishdagi yozuvlar soni tekshiriladi. Hash yoki record identifikatorlari yo‘qolgan va takrorlangan yozuvlarni aniqlaydi; disk to‘lishi sinovi vaqtinchalik fayllarning xavfsiz tozalanishini tekshiradi. External Sort implementatsiyasi uchun bu tekshiruvlar oddiy unit testdan kengroq bo‘lib, modelning asosiy matematik shartlarini nazorat qiladi. Etalon bilan farq topilsa, tasodifiy kirish minimal qarshi misolgacha kichraytiriladi; shu misol regressiya testiga qo‘shiladi.
Bog‘liq tushunchalar
external sort, external merge sort, merge sort, run, buffer, I/O complexity