Частичный просмотр

Cтраница 1

Частичные просмотры. Изъятие и возвращение строк. [1]

Частичный просмотр 2 должен достичь предыдущего уровня. Это делается перераспределением убывающих строк. Слияние степени k - 1 на ту ленту, на которой нет убывающих строк, очищает одну ленту с убывающими строками и приводит одну ленту к идеальному уровню. На рис. 15.10 лента 74 получает строки от трехпоточного слияния, чтобы получить 14 возрастающих строк. Исчерпываемой лентой с убывающими строками является Тг. [2]

Частичные просмотры не предполагаются. Значения для сбалансированного и осциллирующего слияний даны в виде формул, а для многоэтапного и каскадного в виде таблицы. [3]

Частичные просмотры пытаются сместить количество просмотров от flog2Af ] ближе к log2 M. Заметим, что обратное чтение не слишком усложняет рис. 13.9, где Го, Ту и Г2 читаются в обратном направлении при формировании строки на Та. Все строки, формируемые в течение двух частичных просмотров, являются убывающими. [4]

Совершенное слияние. Число перед скобками указывает количество.| Несовершенное слияние ( log3 12 4. [5]

Принцип частичного просмотра можно использовать другим способом, работая с большим числом данных, чем те, что составляют просмотр. [6]

Совершенное слияние. Число перед скобками указывает количество.| Несовершенное слияние ( log3 12 4. [7]

Альтернативой копированию является частичный просмотр, где понятие просмотра ослаблено, и сортировка переходит не от просмотра к просмотру, а от этапа к этапу. Вернемся к рис. 9.12. Строка 33 - копия строки 25, которая создается в конце просмотра 2 и освобождает область C / D. Однако при других стратегиях управления памятью копировать эту строку было бы не обязательно. Ее можно было бы оставить там, где она есть, совсем не изменив характер последующих слияний. Поскольку она в равной степени доступна из любой позиции, ее перемещать абсолютно незачем. При этом слияния на рис. 9.1, по правде говоря, не образуют просмотра, так как обрабатываются не все данные. Частичный просмотр или этап завершен, и следующий начинается с состояния, изображенного на рис. 9.13, с той лишь разницей, что последовательность 4, 9, 16 расположена в другом месте. [8]

Заключительные частичные просмотры. Просмотр 2 сокращен до однопоточного слияния. [9]

Можно усилить стратегию частичного просмотра, подсчитывая все время количество оставшихся строк и сливая лишь столько строк, сколько нужно, чтобы количество получаемых строк было равно степени слияния. Это приводит к состоянию, отмеченному окончание на рис. 13.8, когда число строк равно порядку слияния. [10]

В этом примере каждый частичный просмотр перемещает 114 длин строк. При методе фиктивных величин шесть просмотров переместили бы 750 длин строк. [11]

Заключительные частичные просмотры. Просмотр 2 сокращен до однопоточного слияния. [12]

Обратное чтение может усложнить стратегию частичного просмотра. Если строки, которые должны оставаться на месте, имеют обратный порядок ( как на рис. 13.7), то надо установить считывающие головки так, чтобы кгждая строка имела тот же порядок, что и все остальные строки. [13]

Распределение Рейнольдса.| Распределение Мендозы.| Вертикальное и горизонтальное распределения. [14]

Мендоза и Рейнольде подробно описали алгоритмы частичных просмотров для различных промежуточных состояний. [15]

Страницы: 1 2 3 4