Оператор - слияние
Cтраница 1
Оператор слияния Сл 1 ( Зл, т, /) должен учитывать направление упорядочения сливаемых массивов, информацию о котором он получает из шапки, и в зависимости от него выбирать для использования блок определения минимального или максимального элемента. Все сливаемые массивы, естественно, должны иметь одинаковое направление упорядочения, и на оператор слияния можно возложить функции контроля за выполнением этого условия. Оператор перемотки в случае двухсторонних магнитных лент не используется. [1]
Блок-схема оператора слияния изображена на рис. 7.1. Функции, выполняемые большинством блоков, непосредственно ясны из блок-схемы. Ниже даются пояснения лишь по некоторым блокам. [2]
Группу операторов слияния, исполняемых, начиная с момента освобождения одной из входных лент, назначаемой выходной, и вплоть до освобождения какой-либо другой входной ленты, будем называть этапом слияния. [3]
Для выполнения оператора слияния в ОЗУ выделяется m l участков памяти одинакового размера, называемых магазинами, каждый из которых закрепляется за одной из магнитных лент. Из них m участков, закрепленных за m входными лентами, называются входными магазинами. [4]
При выполнении оператора слияния описанным выше способом любая из магнитных лент всегда подготовлена к выполнению следующего запроса, и поэтому потери времени на поиск зоны исключаются. Однако мультипрограммные возможности цифровой машины не используются. Действительно, после исчерпания любого входного магазина обработка информации не может продолжаться, так как отыскиваемый минимальный элемент может оказаться как раз среди элементов, которые должны быть введены в этот магазин. [5]
После выполнения оператора слияния любого ранга список лент, участвующих в новом этапе слияния, начинает составляться заново. [6]
В процессе выполнения оператора слияния с участием т входных лент каждый элемент массива независимо от т должен йыть один раз считан с ленты и один раз записан на ленту. Это значит, что сложность выполнения оператора слияния не зависит от количества входных лент т и целиком определяется длиной объединенного массива. [7]
Рассмотрим основные характеристики оператора слияния. [8]
С увеличением т результативность оператора слияния монотонно возрастает, однако после / п 4ч - 5 это возрастание становится относительно медленным. [9]
На рис. 7.7 изображен блок операторов слияния. Блоки 34 - 36 выполняют 1 - й подэтап 1-го этапа процедуры упорядочения по данным, подготовленным блоком моделирования, блоки 37 - 35 - выполняют 2 - й подэтап 1-го этапа процедуры. Количество операторов слияния, выполняемых на каждом этапе, фиксируется переменной с. Блок 50 для каждого этапа формирует список входных лент, а операторы 53 и 54 непосредственно осуществляют слияние. [10]
Естественно было бы попытаться наложить на оператор слияния двух упорядоченных подмассивов дополнительное ограничение: объемы памяти, используемые оператором слияния дополнительно к объемам, занимаемым исходными объединяемыми подмассивами, должны быть минимальными. [11]
Степень неупорядоченности результирующего массива после выполнения оператора слияния равна нулю. [12]
Дальнейшее уточнение ведет уже к формулированию самого оператора слияния. При этом следует учитывать, что остаток подпоследовательности, оставшийся после слияния непустой подпоследовательности, добавляется простым копированием к выходной последовательности. [13]
 |
Зависимость эффективности оператора слияния от соотношения между объемами сливаемых подмассивов. [14] |
Сложность данного оператора несколько отличается от сложности оператора слияния в общем случае, так как часть элементов попадает в окончательно упорядоченный массив не только без сравнения, но и без пересылок. [15]
Страницы: 1 2 3