Сети и системы почтовой связи (стр. 17 )

Алгоритмы, используемые в настоящее время для маршрутной сортировки ПО, носят эмпирический характер и не обеспечивают минимизации количества этапов сортировки. Для точного решения задачи соотношение общего количества направлений сортировки n, общего количества накопителей почтовых отправлений q и общего количества этапов сортировки s должно отвечать условию

qs ≥ n либо s =,

где - значение logq n, округленное до ближайшего большего целого числа. Поскольку при q ≥ n задача маршрутной сортировки тривиальна, рассмотрим реальный случай q < n . В этом случае для выполнения маршрутной сортировки необходимо составить сортировочные таблицы, определяющие номера накопителей, в которые должны направляться ПО, адресованные по определенным направлениям, на каждом из этапов сортировки.

Ниже приведен алгоритм составления сортировочных таблиц, основанный на представлении направлений сорти-ровки в виде чисел, записанных в позиционной системе счисления с основанием q. В такой системе счисления целое число N равняется N = ns-1qs-1 + ns-2qs-2 + … + n0q0, и записывается в виде s - разрядного числа N = ns-1 ns-2 … n0,

где ns-1, ns-2 …,n0 - цифры числа N, которые могут принимать значения 0, 1, …, q - 1. Например, десятичное число 1310 в двоичной, третичной и четверичной системах счисления приобретают вид:

1310 = 1×23 + 1×22 + 0×21 + 1×20 = 11012,

1310 = 1×32 + 1×31 + 1×30 = 1113,

1310 = 3×41 + 1×40 = 314.

Обозначим q накопителей, которые используются для маршрутной сортировки, как А0, А1, …, Аq - 1. Тогда алгоритм составления сортировочных таблиц заключается в следующем: на первом этапе сортировки ПО направляются в накопители, номера которых совпадают со значениями первых (младших) цифр направлений сортировки; на втором этапе – со значениями вторых цифр и т. д., на последнем этапе – со значениями последних (старших) цифр. Так, почтовое отправление по указанному направлению 13 будет направляться:

- при использовании двух накопителей А0, А1 – на первом, третьем и четвертом этапах сортировки в накопитель А1, а на втором этапе – в накопитель А0;

- при использовании трех накопителей А0, А1, А2 – на всех трех этапах сортировки в накопитель А1;

- при использовании четырех накопителей А0, А1, А2 А3 – на первом этапе сортировки в накопитель А1, а на втором этапе – в накопитель А3;

- при использовании десяти накопителей А0, А1 ., А0 – на первом этапе сортировки в накопитель А3, а на втором этапе – в накопитель А1.

Ниже приведены примеры построения сортировочных таблиц: табл. 19.1 – при q = 2, s = 4, n = 16; табл. 19.2 – при q = 3, s = 3, n = 27; табл. 19.3 – при q = 4, s = 2, n = 16; табл.19.4 – при q = 10, s = 2, n = 100. Для удобства сравнения направления сортировки в табл. 19.1-19.3 кроме десятичной системы счисления, представлены соответственно, в двоичной, троичной и четверичной системах счисления.

19.4 Организация многопрограммной сортировки почты

Сортировка почтовых отправлений в объектах почтовой связи требует использования разнообразных программ сортировки для обеспечения графиков отправления почты по соответствующим направлениям. Переход от одной прог-раммы сортировки к другой, в существующих системах автоматизированной обработки почты, нуждается в остановке сортировки и разгрузке накопителей сортировочной машины. Такая остановка приводит к значительным потерям времени, особенно в системах автоматизированной обработки посылок.

Как свидетельствуют фактические данные, реальная производительность систем автоматизированной обработки посылок (с учетом простоев, обусловленных изменениями программ сортировки) оказывается на порядок меньше ее технической производительности.

Анализ существующих программ сортировки свидетельствует, что предусматривается общая сортировка, де-тальная сортировка и выделение отдельных направлений сортировки.

Количество программ сортировки совпадает с количеством направлений общей сортировки. Номер или название программы сортировки определяется тем направлением общей сортировки, по которому осуществляется детальная сортировка.

Построение сортировочной таблицы q = 2, s = 4, n = 16

Етап сорти-ровки	Нако-питель	Номера направлений сортировки
Двоичная система счисления	Десятичная система счисления
1.	А0 А1	0000, 0010, 0100, 0110, 1000, 1010, 1100, 1110 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111	00, 02, 04, 06, 08, 10, 12, 14 01, 03, 05, 07, 09, 11, 13, 15
2.	А0 А1	0000, 0001, 0100, 0101, 1000, 1001, 1100, 1101 0010, 0011, 0110, 0111, 1010, 1011, 1110, 1111	00, 01, 04, 05, 08, 09, 12, 13 02, 03, 06, 07, 10, 11, 14, 15
3.	А0 А1	0000, 0001, 0010, 0011, 1000, 1001, 1010, 1011 0100, 0101, 0110, 0111, 1100, 1101, 1110, 1111	00, 01, 02, 03, 08, 09, 10, 11 04, 05, 06, 07, 12, 13, 14, 15
4.	А0 А1	0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111	00, 01, 02, 03, 04, 05, 06, 07 08, 09, 10, 11, 12, 13, 14, 15

Построение сортировочной таблицы q = 3, s = 3, n = 27

Етап сорти-ровки	Нако-питель	Номера направлений сортировки
Троичная система счисления	Десятичная система счисления
1.	А0 А1 А2	000, 010, 020, 100, 110, 120, 200, 210, 220 001, 011, 021, 101, 111, 121, 201, 211, 221 002, 012, 022, 102, 112, 122, 202, 212, 222	00, 03, 06, 09, 12, 15, 18, 21, 24 01, 04, 07, 10, 13, 16, 19, 22, 25 02, 05, 08, 11, 14, 17, 20, 23, 26
2.	А0 А1 А2	000, 001, 002, 100, 101, 102, 200, 201, 202 010, 011, 012, 110, 111, 112, 210, 211, 212 020, 021, 022, 120, 121, 122, 220, 221, 222	00, 01, 02, 09, 10, 11, 18, 19, 20 03, 04, 05, 12, 13, 14, 21, 22, 23 06, 07, 08, 15, 16, 17, 24, 25, 26
3.	А0 А1 А2	000, 001, 002, 010, 011, 012, 020, 021, 022 100, 101, 102, 110, 111, 112, 120, 121, 122 200, 201, 202, 210, 211, 212, 220, 221, 222	00, 01, 02, 03, 04, 05, 06, 07, 08 09, 10, 11, 12, 13, 14, 15, 16, 17 18, 19, 20 21, 22, 23, 24, 25, 26

Построение сортировочной таблицы q = 4, s = 2, n = 16

Етап сорти-ровки	Нако-питель	Номера направлений сортировки
Четверичная система счисления	Десятичная система счисления
1.	А0 А1 А2 А3	00, 10, 20, 30 01, 11, 21, 31 02, 12, 22, 32 03, 13, 23, 33	00, 04, 08, 12 01, 05, 09, 13 02, 06, 10, 14 03, 07, 11, 15
2.	А0 А1 А2 А3	00, 01, 02, 03 10, 11, 12, 13 20, 21, 22, 23 30, 31, 32, 33	00, 01, 02, 03 04, 05, 06, 07 08, 09, 10, 11 12, 13, 14, 15

Общая сортировка предусматривает деление первичного (входного) потока ПО на крупные (обобщенные) направления например: Север, Юг, Восток, Запад, Центр.

Детальная сортировка предусматривает деление первичного потока или вторичного потока, созданного почтовыми отправлениями одного из общих направлений на конкретные направления с которыми осуществляется обмен почты.

Для ПО адресованных в крупные города выделяются отдельные направления сортировки и предусматриваются соответствующие накопители.