Pochta aloqasining texnologik (ishlab chiqarish) jarayonlari

N = n ^k yoki k = log_n N.
Demak, N = 1 000 000, n = 100, k = log1001000000 = 3 uchun
(saralashning birinchi bosqichi - yozma yozishmalarni har biri 10 000 yo'nalishli 100 ta guruhga bo'lish; saralashning ikkinchi bosqichi - saralashning birinchi bosqichida tuzilgan 100 ta guruhning har biri 100 tadan 100 ta guruhga bo'linishi; saralashning uchinchi bosqichi - saralashning ikkinchi bosqichida tuzilgan 10 000 ta guruhning har birida bitta yo'nalish bo'yicha 100 tadan guruhga bo'linishi).
Shuni ta'kidlash kerakki, saralash bosqichlarining qayd etilgan minimal soni faqat bitta pochta aloqasi ob'ektida amalga oshirilgan taqdirdagina amalga oshirilishi mumkin. Turli xil pochta ob'ektlarida saralash amalga oshirilganda, saralash yo'nalishlari soni harflarni saralash mashinasining haydovchilari yoki saralash kabinetining katakchalari soniga qarab emas, balki bunday saralash amalga oshiriladigan pochta aloqasi ob'ektlari soniga qarab belgilanadi. Natijada, shaxsiy kompyuterlarni saralashning haqiqiy soni minimaldan sezilarli darajada oshib ketishi mumkin. Pochta tarmoqlari ko'p darajali ierarxik tuzilmalarga ega bo'lib, ular ierarxiyaning eng yuqori darajasidagi pochta ob'ektlari soniga qarab bitta piramidaga (SPS-A) yoki bir nechta piramidalarga o'xshab ko'rinadi, ularning cho'qqilari "har biri" ga muvofiq o'zaro bog'langan. har biri bilan” tamoyili (SPS-B). UGPPS pochta tarmog'ining to'rt darajali ierarxik tuzilmalari 23-rasmda ko'rsatilgan.
Pochta aloqasi ob'ektlari orqali yozma yozishmalarni o'tkazish yo'nalishlarini tanlash imkoniyatini ta'minlash uchun ierarxiyaning yuqori darajasidagi tushayotgan ob'ektlarga yozma yozishmalar paketlari tushayotgan ob'ektlarga yozma yozishmalar paketlarini o'z ichiga olishi kerak. ierarxiyaning past darajasi; Belgilangan pochta jo'natmalari, o'z navbatida, ierarxiyaning pastroq darajasidagi tushuvchi ob'ektlarga xat pochtasi paketlarini o'z ichiga oladi va shunga o'xshash oxirgi paketlarda ierarxiyaning eng past darajasidagi tushuvchi ob'ektlarga xat pochtasi mavjud bo'ladi. .
Shunday qilib, to'rt darajali SPS-A tarmog'ida har bir tushuvchi ob'ektga GO da tuzilgan paketlar (masalan, konteynerlar) tegishli hududlarning har bir tushuvchi (tuman ob'ektlari) paketlarini o'z ichiga olishi kerak (masalan, sumkalar) va oxirgisi - tegishli hududlarning quyi oqim OS dan har biriga paketlar (masalan, post-paketlar).
Saralash bosqichlarini pochta ob'ektlari o'rtasida bo'lishning ko'plab variantlari mumkin.
Shunday qilib, N = 1 000 000, n = 100, k = log1001000000 = 3 (saralashning birinchi bosqichi yozma yozishmalarni har biri 10 000 yo'nalishli 100 ta guruhga bo'lish; saralashning ikkinchi bosqichi - 100 ta guruhning har birini bo'lish. saralashning birinchi bosqichida har biri 100 ta yoʻnalishli 100 ta guruhga shakllantiriladi; saralashning uchinchi bosqichi — saralashning ikkinchi bosqichida tuzilgan 10 000 ta guruhning har birini bitta yoʻnalishda 100 tadan guruhga boʻlish).
Shuni ta'kidlash kerakki, saralash bosqichlarining qayd etilgan minimal soni faqat bitta pochta aloqasi ob'ektida amalga oshirilgan taqdirdagina amalga oshirilishi mumkin. Turli xil pochta ob'ektlarida saralash amalga oshirilganda, saralash yo'nalishlari soni harflarni saralash mashinasining haydovchilari yoki saralash kabinetining katakchalari soniga qarab emas, balki bunday saralash amalga oshiriladigan pochta aloqasi ob'ektlari soniga qarab belgilanadi. Natijada, shaxsiy kompyuterlarni saralashning haqiqiy soni minimaldan sezilarli darajada oshib ketishi mumkin. Pochta tarmoqlari ko'p darajali ierarxik tuzilmalarga ega bo'lib, ular ierarxiyaning eng yuqori darajasidagi pochta ob'ektlari soniga qarab bitta piramidaga (SPS-A) yoki bir nechta piramidalarga o'xshab ko'rinadi, ularning cho'qqilari "har biri" ga muvofiq o'zaro bog'langan. har biri bilan” tamoyili (SPS-B). UGPPS pochta tarmog'ining to'rt darajali ierarxik tuzilmalari 23-rasmda ko'rsatilgan.
Pochta aloqasi ob'ektlari orqali yozma yozishmalarni o'tkazish yo'nalishlarini tanlash imkoniyatini ta'minlash uchun ierarxiyaning yuqori darajasidagi tushayotgan ob'ektlarga yozma yozishmalar paketlari tushayotgan ob'ektlarga yozma yozishmalar paketlarini o'z ichiga olishi kerak. ierarxiyaning past darajasi; Belgilangan pochta jo'natmalari, o'z navbatida, ierarxiyaning pastroq darajasidagi tushuvchi ob'ektlarga xat pochtasi paketlarini o'z ichiga oladi va shunga o'xshash oxirgi paketlarda ierarxiyaning eng past darajasidagi tushuvchi ob'ektlarga xat pochtasi mavjud bo'ladi. .
Shunday qilib, to'rt darajali SPS-A tarmog'ida har bir tushuvchi ob'ektga GO da tuzilgan paketlar (masalan, konteynerlar) tegishli hududlarning har bir tushuvchi (tuman ob'ektlari) paketlarini o'z ichiga olishi kerak (masalan, sumkalar) va oxirgisi - tegishli hududlarning quyi oqim OS dan har biriga paketlar (masalan, post-paketlar).
Saralash bosqichlarini pochta ob'ektlari o'rtasida bo'lishning ko'plab variantlari mumkin.

22-rasm.

23-rasm.

24-rasm.

25-rasm.

26-rasm.

27-rasm
19.2 Pochtalarni saralash rejalarini ishlab chiqish
Dasturiy ta'minotni saralash rejasi dasturiy ta'minotni saralash yo'nalishlarini saralash mashinasining drayverlari o'rtasida taqsimlashni tartibga soluvchi hujjatdir. Saralash rejasini tuzish vazifasi quyidagicha qo'yiladi: saralash mashinasida n ta A1, A2, ..., An disklari mavjud. Saralash uchun kelgan pochta jo'natmalari N1, N2, ..., Nm yo'nalishlari bo'yicha saralanishi kerak, ular haqidagi ma'lumotlar pochta indekslarida mavjud. Pochta jo'natmalarining p1, p2,..., pm yo'nalishlarining har biriga tegishli bo'lish ehtimoli berilgan va p1 ≥ p2 ≥…≥ p_m va p1 + p2 +…+ p_m = 1.
Ma'lumki, m > n, buning natijasida dasturiy ta'minot bosqichlar bo'yicha saralanishi kerak, ya'ni ular saralash mashinasidan bir necha marta o'tishi kerak. N_i yoʻnalishi boʻyicha murojaat qilingan PO si marta (s1 ≤ s2 ≤ …≤ s_m) saralanadi.
Bitta pochta xabarini saralashning o'rtacha sonini minimallashtirish kerak

Saralashni tashkil etishning ikkita asosiy usuli mavjud: yo'nalishlarni tanlash usuli va yo'nalishlarni guruhlash usuli. Shaklda. 25 da 10 ta haydovchi ishtirokida 100 yo'nalish bo'yicha saralash misollari ko'rsatilgan (a - yo'nalishlarni tanlash usuli bilan, b - yo'nalishlarni guruhlash usuli bilan, c estrodiol usulda). Ovallardagi raqamlar - yo'nalishlar guruhlari, aylanalardagi raqamlar - tanlangan yo'nalishlar, to'rtburchaklardagi raqamlar - saralash bosqichlari.
Birinchi usulga ko'ra, saralashning har bir bosqichida keyingi n 1 yo'nalishdagi dasturiy ta'minot n-1 drayvlarning har biriga, qolganlari n-chi (jamoa) haydovchiga yuboriladi, undan, Saralashning keyingi bosqichida barcha dasturiy ta'minot ularning yo'nalishlari bo'yicha saralanmaguncha n-1 yo'nalishlari yana taqsimlanadi (25-rasm, a)
Ikkinchi usulga ko'ra, saralashning har bir bosqichida dasturiy ta'minot saralash yo'nalishlariga ko'ra n ta guruhga bo'linadi, ularning har biri tegishli xotiraga yuboriladi, keyingi saralash bosqichida ko'rsatilgan dasturiy ta'minot guruhining har biri yana. n guruhga bo'lingan, har bir saqlash faqat bitta yo'nalishdagi dasturiy ta'minotni o'z ichiga oladi (25-rasm, b).
Amalda, odatda, birlashtirilgan saralash usuli qo'llaniladi, bunda saralashning birinchi yoki birinchi va keyingi bosqichlarida dasturiy ta'minotning bir qismi ajratiladi va dasturiy ta'minotning qolgan qismi drayvlarda faqat bitta yo'nalish topilmaguncha tartiblanadi. (25-rasm. c).

Adabiyotlar: [2] p-5, [3] p-4.

19.3. Pochtalarni marshrutga saralashni tashkil etish

Marshrutni saralash pochta jo'natmalarini pochta yo'nalishi yo'lida joylashgan pochta almashinuv punktlari (magistral, viloyat, tuman yo'nalishlari, shahar pochta bo'limlari bilan pochta almashinuvi yo'nalishlari, GSP yo'nalishlari) bo'yicha, shuningdek, qabul qiluvchilarga saralashda keng qo'llaniladi. ' pochta qutilari (pochtachilar marshrutlari). Rasmiy ravishda marshrutni saralash muammosi i, j,, k yo‘nalishlariga (i, j,… k = 0, 1,…, n 1) yuborilgan pochta jo‘natmalarining tartibsiz kirish ketma-ketligini o‘zgartirish muammosi sifatida qo‘yiladi. tartiblangan boshlang'ich ketma-ketlik 0, 1, …, n 1, bunda istalgan yo'nalishda murojaat qilingan UE soni ixtiyoriy butun son bo'ladi.

Bu masala, shuningdek, i, j, …, k (0 ≤ i, j, …, k ≤ n 1)) sonlarning qandaydir boshlang‘ich tartibsiz ketma-ketligini saralash (o‘zgartirish) bo‘yicha ma’lum matematik muammoning maxsus holati vazifasini ham bajaradi. chiqish tartibli ketma-ketligi 0 ≤ 1 ≤ … ≤n1.
Masalan, 03, 06, 05, 05, 10, 10, 00, 07, 08, 01, 05, 01, 03, 04, 15, 13, 00, 02, 02, 07, yoʻnalishlarida yoʻnaltirilgan dasturiy taʼminotlar ketma-ketligi. 07, 12, 03, 08 raqamlari 00, 00, 01, 01, 02, 02, 03, 03, 03, 04, 05, 05, 05, 06, 07, 07, 07, 08 qatoriga qayta formatlanishi kerak , 10, 10, 12, 13, 15.
Raqamlarni kiritish ketma-ketligi elementlarini almashtirishga asoslangan saralashning matematik masalasini hal qilishning ma'lum algoritmlari jismoniy dasturiy ta'minotni buyurtma qilish uchun amalda yaroqsiz. Marshrutni saralashni amalga oshirish uchun an'anaviy qo'lda yoki mashina dasturiy ta'minotini saralash texnologiyalaridan foydalanish tabiiydir.
Hozirda dasturiy ta'minot marshrutini saralashda foydalaniladigan algoritmlar empirik xarakterga ega va saralash bosqichlari sonini kamaytirmaydi.
Muammoni aniq hal qilish uchun saralash yo'nalishlarining umumiy soni n, pochta jo'natmalarining umumiy soni q va saralash bosqichlarining umumiy soni s nisbati shartga javob berishi kerak.

bu yerda [log_q n] log_q n qiymatining eng yaqin katta butun songa yaxlitlangan qiymati. Marshrutni saralash masalasi q ≥ n uchun ahamiyatsiz bo'lgani uchun q < n haqiqiy holatni ko'rib chiqamiz. Bunday holda, marshrutni saralashni amalga oshirish uchun har bir saralash bosqichida ma'lum yo'nalishlarga yo'naltirilgan dasturiy ta'minot yuborilishi kerak bo'lgan disklar sonini aniqlaydigan saralash jadvallarini tuzish kerak.
Quyida q asosli pozitsion sanoq sistemasida yozilgan sonlar sifatida tartiblash yo‘nalishlarini ko‘rsatish asosida tartiblash jadvallarini tuzish algoritmi keltirilgan. Bunday sanoq sistemasida N butun soni N = n_s-1 + qs_s-1 + n_s-2 q_s-2 + ... + n_o q₀ ga teng va s - bit soni N = n_s-1 n_s-2 .. shaklida yoziladi.
Bu erda n_s-1, n_s-2 ..., n₀ N sonining raqamlari bo'lib, ular 0, 1, ..., q 1 qiymatlarini qabul qilishi mumkin. Masalan, ikkilik, uchinchi darajali 1310 o'nlik soni va to'rtlamchi sanoq tizimlari quyidagi shaklda bo'ladi:
13₁₀ = 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 1101₂,
13₁₀ = 1×3² + 1×3¹ + 1×3⁰ = 111₃,

13₁₀ = 3×4¹ + 1×4⁰ = 31₄.

Marshrutlarni saralash uchun ishlatiladigan q diskni A0, A1, ..., Aq 1 deb belgilaymiz. Keyin tartiblash jadvallarini tuzish algoritmi quyidagicha: tartiblashning birinchi bosqichida raqamlari bo'lgan disklarga PO yuboriladi. saralash yo'nalishlarining birinchi (pastki) raqamlari qiymatlariga mos kelish; ikkinchi bosqichda - ikkinchi raqamlarning qiymatlari va boshqalar bilan; oxirgi bosqichda - oxirgi (eng yuqori) raqamlarning qiymatlari bilan. Shunday qilib, ko'rsatilgan 13-yo'nalishdagi pochta jo'natmalari yuboriladi:
- ikkita A0, A1 uzatgichdan foydalanganda - saralashning birinchi, uchinchi va to'rtinchi bosqichlarida A1 uzatgichga va ikkinchi bosqichda - A0 uzatgichga;
- uchta A0, A1, A2 uzatgichga foydalanganda - A1 uzatgichga saralashning barcha uch bosqichida;
- to'rtta A0, A1, A2 A3 uzatgichlarini ishlatganda A1 omboriga saralashning birinchi bosqichida va ikkinchi bosqichda- A3 uzatgichga;
- o'nta A0, A1 ., A0 uzatgichlardanfoydalanganda - saralashning birinchi bosqichida A3 drayvga, ikkinchi bosqichda - A1 uzatgichga.
Quyida jadvallarni saralash misollari keltirilgan: Jadval. 30 - q = 2 da, s = 4, n = 16; tab. 31 - q = 3 da, s = 3, n = 27; tab. 32 - q = 4 da, s = 2, n = 16; Jadvaldagi tartiblash yo'nalishini solishtirish qulayligi uchun. 30-32, o'nlik sanoq sistemasiga qo'shimcha ravishda, mos ravishda ikkilik, uchlik va to'rtlik sanoq sistemalarida keltirilgan.
19.4 Ko'p dasturli pochtani saralashni tashkil etish
Pochta ob'ektlarida pochta jo'natmalarini saralash tegishli manzillarga pochta jo'natish jadvallarini taqdim etish uchun turli xil saralash dasturlarini qo'llashni talab qiladi. Mavjud avtomatlashtirilgan pochtani qayta ishlash tizimlarida bir saralash dasturidan ikkinchisiga o'tishda tartiblashni to'xtatish va saralash mashinasi drayverlarini tushirish kerak. Bunday to'xtash, ayniqsa, posilkalarni qayta ishlashning avtomatlashtirilgan tizimlarida sezilarli vaqt yo'qotishlariga olib keladi.
Haqiqiy ma'lumotlardan ko'rinib turibdiki, posilkalarni qayta ishlashning avtomatlashtirilgan tizimlarining haqiqiy ishlashi (saralash dasturlaridagi o'zgarishlar tufayli ishlamay qolish vaqtini hisobga olgan holda) uning texnik ko'rsatkichlaridan pastroq bo'lgan tartibdir.
Mavjud saralash dasturlarini tahlil qilish shuni ko'rsatadiki, umumiy saralash, batafsil saralash va alohida saralash yo'nalishlarini ajratish ko'zda tutilgan.
Saralash dasturlari soni umumiy tartiblash yo'nalishlari soni bilan bir xil. Saralash dasturining raqami yoki nomi batafsil saralash amalga oshiriladigan umumiy saralash yo'nalishi bilan belgilanadi.