Многопутевое слияние и выбор с замещением

Рассмотрим процесс порождения начальных отрезков, которые затем подвергаются слиянию. Пусть имеется Р возрастающих отрезков. Очевидным способом их слияния является следующий: из первых ключей каждого отрезка выбрать минимальный, соответствующую запись передать на выход и исключить из входных данных, затем этот процесс повторяется. Если Р велико, то целесообразно использовать дерево выбора из Р элементов. Пример 4-х путевого слияния изображен на рис. 39.

 
 

Рис.39 4х-путевое слияние

 

Техника выбора с замещением может использоваться на первой фазе внешней сортировки. В этом случае Р выбирается достаточно большим. Каждая запись при выводе замещается очередной записью из исходных данных. Если у новой записи ключ меньше, чем у только что выведенной, то она помечается как не участвующая в дальнейшем выборе, а значение Р уменьшается на единицу и процесс продолжается.

Пример. Пусть исходная последовательность ключей:
2 7 12 3 8 9 4 1 5 11 10 6 и Р=4

Процесс вывода начальных сортированных отрезков иллюстрируется таблицей:

Содержимое памяти Вывод
(4)
(4) (1)
(4) (1) (5)
(4) (1) (11) (5) Конец отрезка

 

В скобки заключены ключи, не участвующие в дальнейшем выборе. Таким путем удается получить упорядоченные последовательности длиннее Р, что важно, так как время внешней сортировки слиянием в значительной мере зависит от числа начальных отрезков. Э.Ф.Мур предложил изящный способ доказательства того, что средняя длина порождаемого отрезка равна , проведя аналогию со снегоочисти­телем, движущимся по кругу. Пусть на кольцевую дорогу непре­рыв­но падают снежинки (записи). Снежинки исчезают из системы (запи­си выводятся), когда они сбрасываются за пределы дороги. Точки дороги обозначаются вещественными числами x (0 £ x £1). Снежинка, падающая в точку х, соответствует входной записи с ключом х, а снегоочиститель имитирует процесс вывода. В установившемся режиме общее число снежинок на дороге в точности равно Р. Каждый раз, когда снегоочиститель проходит точку 0, заканчивается формирование нового отрезка. На рис.40 изображено поперечное сечение дороги, когда система находится в

 
 

установившемся режиме.

Рис. 39 Аналогия со снегоочистителем

 

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








Дата добавления: 2014-12-02; просмотров: 1196;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.