Многопутевое слияние и выбор с замещением
Рассмотрим процесс порождения начальных отрезков, которые затем подвергаются слиянию. Пусть имеется Р возрастающих отрезков. Очевидным способом их слияния является следующий: из первых ключей каждого отрезка выбрать минимальный, соответствующую запись передать на выход и исключить из входных данных, затем этот процесс повторяется. Если Р велико, то целесообразно использовать дерево выбора из Р элементов. Пример 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) | Конец отрезка |
| … |
В скобки заключены ключи, не участвующие в дальнейшем выборе. Таким путем удается получить упорядоченные последовательности длиннее Р, что важно, так как время внешней сортировки слиянием в значительной мере зависит от числа начальных отрезков. Э.Ф.Мур предложил изящный способ доказательства того, что средняя длина порождаемого отрезка равна 2Р, проведя аналогию со снегоочистителем, движущимся по кругу. Пусть на кольцевую дорогу непрерывно падают снежинки (записи). Снежинки исчезают из системы (записи выводятся), когда они сбрасываются за пределы дороги. Точки дороги обозначаются вещественными числами x (0 £ x £1). Снежинка, падающая в точку х, соответствует входной записи с ключом х, а снегоочиститель имитирует процесс вывода. В установившемся режиме общее число снежинок на дороге в точности равно Р. Каждый раз, когда снегоочиститель проходит точку 0, заканчивается формирование нового отрезка. На рис.40 изображено поперечное сечение дороги, когда система находится в
 |
установившемся режиме.
Рис. 39 Аналогия со снегоочистителем
Из рисунка видно, что количество снега, удаляемого за один оборот, вдвое превосходит количество снега, присутствующего на дороге в любой момент.
Дата добавления: 2014-12-02; просмотров: 1173;