|
Uch tomonlama razryadli tezkor saralash
MSD-saralashni amalga oshirish uchun tezkor kortni moslashtirishning yana bir imkoniyati bu tugmachalarning yuqori baytida uch baytlikdan foydalanish, keyingi baytga faqat o'rta pastki faylda o'tish (yuqori baytlari yuqori baytlariga teng bo'lgan tugmalar bilan). markaziy element). Ushbu usul osongina amalga oshirilishi mumkin (bitta deklaratsiya bayonoti va 7.5 dasturidan uch tomonlama ajratish kodi etarli) va har xil vaziyatlarga moslashtirilishi mumkin. Ushbu uslubning to'liq tatbiq etilishi Dastur 10.3 da ko'rsatilgan.
Aslini olib qaraganda, uch tomonlama radixli tezkor kontsertni bajarish faylni tugmachalarning eng muhim belgilariga ko'ra saralashga (quicksort yordamida) tenglashtiriladi va keyin bu usulni qolgan tugmalarga rekursiv ravishda qo'llaydi. Satrlarni saralashda bu usul odatdagi tezkor saralash va MSD tartiblashdan ko'ra yaxshiroq ishlaydi. Aslida, uni ikkita algoritmning gibridi deb qarash mumkin.
Uch tomonlama radiksli tezkor kortni standart MSD-sort bilan taqqoslaganingizda, u faylni faqat uch qismga bo'linishini va shu sababli tezkor multipath bo'linishidan foydalanmasligini sezasiz, ayniqsa saralashning dastlabki bosqichlarida. Boshqa tomondan, MSD-ni saralashning keyingi bosqichlarida ko'plab bo'sh konteynerlar paydo bo'ladi, 3 tomonlama radixli tezkor takrorlash tugmachalari, tor doiradagi tugmachalar, kichik fayllar va MSD saralashni sekinlashtiradigan boshqa holatlar uchun yaxshi ishlaydi.
Ushbu MSD saralash asosan uch tomonli bo'linish tezkor kodiga teng (Dastur 7.5), lekin undan quyidagilar bilan farq qiladi: (1) kalitlarga kirish baytlarga kirish bilan almashtiriladi, (2) joriy bayt pozitsiyasi parametr sifatida rekursiv dastur va (3) o'rta pastki fayl uchun rekursiv chaqiriqlar keyingi baytga o'tadi. Indekslar satrlar chegarasidan tashqariga chiqmasligini ta'minlash uchun keyingi baytga rekursiv qo'ng'iroqlar qilishdan oldin markaziy qiymat 0 ga tengligini tekshirib ko'riladi. Agar markaziy qiymat 0 bo'lsa, chap pastki fayl bo'sh, o'rtadagi pastki fayl teng kalitlarga to'g'ri keladi va o'ng pastki fayl keyingi ishlov berishni talab qiladigan uzunroq qatorlarga to'g'ri keladi.
#define ch(A) digit(A, d)
template
void quicksortX(Item a[], int l, int r, int d)
{ int i, j, k, p, q; int v;
if (r-l <= M) { insertion(a, l, r); return; }
v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
while ( i < j )
{ while (ch(a[ + + i]) < v) ;
while (v < ch(a[-- j ] ) ) if (j == l) break;
if (i > j) break;
exch(a[i], a[j]);
if (ch(a[i]) == v) { p++; exch(a[p], a[i]); }
if (v == ch(a[j])) { q—; exch(a[j], a[q]); }
}
if (p == q)
{ if (v != '\0') quicksortX(a, l, r, d+1); return; }
if (ch(a[i]) < v) i++;
for (k = l; k <= p; k+ + , j--) exch(a[k], a[j]);
for (k = r; k >= q; k--, i++) exch(a[k], a[i]);
quicksortX(a, l, j, d);
if ((i == r) && (ch(a[i]) == v)) i+ + ;
if (v != '\0') quicksortX(a, j + 1, i-1, d+1);
quicksortX(a, i, r, d);
}
rasm. 10.11. Uch tomonlama radixli tezkor korsort
Fayl uch qismga bo'lingan: a dan i gacha bo'lgan harflar, j harflaridan boshlangan so'zlar va k dan z gacha bo'lgan harflar bilan boshlangan so'zlar. Keyin saralash rekursiv tarzda davom etadi.
Bo'limning kalitning turli qismlarida turli xil naqshlarga moslashishi ayniqsa muhimdir. Bundan tashqari, unga yordamchi qator kerak emas. Ushbu afzalliklar, agar ko'p sonli fayllar mavjud bo'lsa, unda uch tomonlama bo'linishlar ketma-ketligi yordamida ko'p yo'lli bo'linishni amalga oshirish uchun qo'shimcha almashinuvlar zarurligi bilan muvozanatlashadi.
Shakl. 10.11 - rasmda ko'rsatilgan uchta harfli so'zlarni saralashda ushbu usul qanday ishlashiga misol. 10.7 va shakl. 10.12 rekursiv qo'ng'iroqlarning tuzilishini ko'rsatadi. Har bir tugun to'liq uchta rekursiv chaqiruvga to'g'ri keladi: birinchi bayt qiymati kichikroq tugmachalar uchun (chap bola), birinchi bayt qiymati bir xil bo'lgan kalitlar uchun (o'rta bola) va kattaroq birinchi bayt qiymati (o'ng bola).
Agar tartiblash uchun kalitlar 10.2-bo'limdagi mavhumlikka amal qilsa, standart tezkor tortish va 6-9-boblarda muhokama qilingan barcha boshqa tartiblash texnikalarini MSD saralash deb hisoblash mumkin, chunki taqqoslash funktsiyasi avval kalitning eng muhim qismiga kiradi (qarang. Mashq 10.3).
rasm. 10.12. Uch tomonli radixli koksortning rekursiv tuzilishi
Muntazam va uch daraxtlarning bu kombinatsiyasi shaklda ko'rsatilgan uchlikdagi 26 tomonlama tugunlarni almashtirishga mos keladi. 10.10-rasmda ko'rsatilgandek, uchlik ikkilik qidiruv daraxtlariga. 10.13. O'rta havola bilan tugaydigan ildizdan pastga tushadigan har qanday yo'l fayl kalitini belgilaydi - yo'l bo'ylab o'rta havolalar tomonidan ko'rsatilgan belgilar yordamida. Shakl. 10.10da 1035 ta bo'sh havola ko'rsatilmagan, bu rasmda ushbu daraxtdagi 155 ta bo'sh havola ko'rsatilgan.
Har bir bo'sh ma'lumot mos bo'lmagan idishga to'g'ri keladi, shuning uchun bu farq MSD saralashida paydo bo'ladigan bo'sh konteynerlar sonini qanchalik keskin kamaytirishi mumkinligini ko'rsatadi.
rasm. 10.13. Uch tomonlama radiksli tezkor uchli tugunlarning misoli
Uch tomonlama radixli tezkor MSD-ni bo'sh paqir muammosini uch tomonlama bo'linishni amalga oshirish yo'li bilan hal qiladi: bitta bayt qiymati yo'q qilinadi, qolganlari esa qayta ishlanadi.
Ushbu harakat triening har bir M-yo'l tugunini, MSD saralash chaqiruvlarining rekursiv tuzilishini tavsiflovchi daraxtni almashtirishga mos keladi, har bir bo'sh bo'lmagan konteyner ichki tugunga ega bo'lgan uchlamchi daraxt bilan. To'liq tugunlar uchun (chapda) bu o'zgarish vaqtni talab qiladi va xotirani ozgina tejaydi, ammo bo'sh tugunlar uchun (o'ngda) vaqt minimal va xotirani tejash muhim ahamiyatga ega.
Do'stlaringiz bilan baham: |
