Внешняя сортировка

Цель: изучение внешней сортировки

Из мира "электронных" скоростей переместимся в мир меньших скоростей, мир с механическими перемещениями и влиянием инерции. Хотя диск и делает сотни оборотов в секунду, проходят миллисекунды до момента, когда нужный запоминающий элемент окажется под головкой чтения/записи. Поэтому если любой известный нам способ упорядочения в памяти применить "механически" к данным на диске, затраты времени окажутся, скорее всего, неприемлемыми.

Сортировку данных на магнитных дисках называют внешней.

Сложности при сортировке на диске.

Исследовать, а тем более конструировать внешнюю сортировку невозможно, не представляя, мало - мальски, специфики дисков.

Диски имеют запоминающие магнитные поверхности и вращаются с| большой постоянной скоростью под головками чтения/записи. Головка обслуживает одну поверхность.

При фиксированном положении головок доступ происходит к данным треков (окружностей), находящихся под головками. Совокупность этих треков назовем текущим цилиндром.

Головки крепятся на штанге, подобной "коромыслу" проигрывателя. После перемещения блока головок (поворота штанги) текущим становится следующий цилиндр. Цилиндры нумеруются в порядке их прохождения блоком головок при движении штанги в одну сторону. Расстоянием между элементами данных назовем разность номеров цилиндров, где они размещены.

Адресация (нумерация) элементов памяти на диске идет в пределах цилиндра с переходом по исчерпании его объема на следующий, потом на третий и т. д. Файл данных записывается по порядку адресов, но если свободного участка не хватило, продолжается в другом участке и, возможно, на другом цилиндре (случай фрагментации файла).

Изложена весьма упрощенная модель диска, но ее достаточно.

Хотя диски называют памятью прямого доступа, время обращения к данным гораздо большего порядка, чем время чтения/записи в основной памяти, по причине

а) задержки, связанной с ожиданием момента, когда нужный элемент цилиндра пройдет под головкой;
б) перемещения головок, когда требуются данные не из текущего цилиндра.

Прогон - это прохождение файла в одном направлении со считыванием данных в память и, возможно, их возвратом в файл.

{По возможности большую часть работы выполняйте с данными, вызванными в память, не обращаясь к диску до конца обработки этой части.}

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

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

Время внешней сортировки зависит от
а) внутренней сортировки частей файла;
б) многократного считывания и записи данных на диск;
в) ходов головки между актами считывания/записи;
г) действий в памяти при слиянии упорядоченных частей.

Сортировка методом поглощения.

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

Перед поглощением очередная часть файла считывается в зону "А" памяти, там упорядочивается и остается. Начало ранее упорядоченной части считывается в зону "В" и начинается слияние, прерываемое считыванием в зону "В", когда она опустошается. По мере заполнения зоны "С" записями акта слияния, содержимое ее переписывается в файл (на место поглощаемой части и далее в сторону конца файла). Если при слиянии взяты все записи поглощаемой части, поглощение завершается передачей в файл из зоны "С" остатка результата. Слияние также завершается, если исчерпана ранее упорядоченная часть. Поглощение ею очередной части произошло.

Ходов в данном методе будет мало и во время сортировки вы не услышите характерного поскрипывания механизма головок. Это дает экономию времени и при небольшом размере файла сортировка проходит быстро.

Челночное балансное слияние

На 1 этапе внутренней сортировки частей в файле создают М упорядоченных частей, по возможности большего размера R. К ним применяют прямое слияние.
Создают резервное дисковое пространство файла и располагают его непосредственно до или после сливаемых частей и перемещается к следующим частям по завершении слияния. Его размер не меньше размера R части. Резерв и пространство ближайшей части будут заполнено результатом слияния двух первых частей, при этом пространство 2-й части освободится и станет резервом, необходимым для слияния следующей пары частей и т. д.

По мере слияния частей резерв перемещается от начала файла к концу, потом обратно и т. д., как челнок. Поскольку место результата не удалено от сливаемых частей, ходы невелики, пока сами части небольшие. В процессе сортировки "челнок" увеличивают, ибо растут части:

а) слияние частей размером R (промежуточная ситуация)

Стрелками показано перемещение данных при слиянии.

Заметим, что резерв можно увеличивать, когда он в конце файла; это происходит один раз за 2 прогона челнока.

Все было бы хорошо, однако, челнок величиной в половину файла может занимать его начало.

Хорошо бы ограничить рост размера "челнока", ибо этот рост увеличивает размер ходов.

Путем модификации конечных этапов слияния добьемся, чтобы этот рост остановился на размере D = 1/6 размера файла.

Для этого однако надо, чтобы программа так определила исходные размер и положение резерва (в начале или в конце файла), чтобы в момент, когда останутся всего 3 больших части, резерв, имеющий размер D, стоял в начале файла.

в) этап слияния (с подэтапами), когда в файле 6 частей.

г) этап слияния "по половинам "(естественное слияние), когда частей 3. Концевая часть файла на этом этапе не используется.

д) заключительный этап слияния; сначала берем для слияния первую половину конечной части и всю начальную часть:

По окончании слияния 1 выясняется, надо ли сместить остаток начальной части, чтобы освободить место для конца результата и продолжить слияние ("подслияние"). Подслияние не нужно, если в ходе слияния начальная часть исчерпана, надо лишь вытеснить резерв в конец файла, переписав окончание.

И при слиянии 1, и при под слиянии размер резерва не меньше минимально требуемого.

Итак, на сегодняшнем занятии мы рассмотрели внешнюю сортировку.