20. Внешняя сортировка. Особенности внешней сортировки. Сортировка поглощением. Временная сложность алгоритма.

 

            Внешняя сортировка оперирует с данными, которые принадлежат к внешним файлам. Обозначим R размер файла, B - размер буфера чтения (или вывода) в оперативной памяти, С -  действительная постоянная, удовлетворяющая двойному неравенству: 1<=С<10. Отношение R/B позволяет условно разделить все файлы на малые, средние, большие и гигантские.

            Если R/B ~ С, то соответствующий файл считают малым,

            если R/B ~ 10С, то файл средний,

            если R/B ~ 100С, то файл большой,

            если R/B ~ 1000С и более, то файл гигантский.

            Тексты процедур внешней сортировки, рассматриваемых в этой главе, не приводятся в данном пособии ввиду их большого объема.

 

§ 1. Составляющие сложности сортировки на диске

           

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

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

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

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

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

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

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

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

            Выражение сложности внешней сортировки учитывает время:

            1. внутренней сортировки частей файла;

            2. многократного считывания и записи данных на диск;

            3. ходов головки между процедурами считывания/записи;

            4. действий в памяти при слиянии упорядоченных частей.

 

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

 

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

            В начале сортировки считывается окончание файла, упорядочивается в памяти и возвращается на место.

            Схема поглощения частей (номера соответствуют очередности поглощения) представлена на рис 4.1.

            Рис. 4.1. Схема поглощения частей.

 

            Перед поглощением очередная часть файла считывается в зону “А” памяти, там упорядочивается и остается. Начало ранее упорядоченной части считывается в зону “В”, после чего начинается слияние (см. §4 гл. III), прерываемое считыванием в зону “В”, когда она опустошается.

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

            Если при слиянии взяты все записи поглощаемой части, поглощение завершается передачей из зоны “С” в файл остатка результата. Слияние также завершается, если исчерпана ранее упорядоченная часть. Поглощение ею очередной части произошло.

            Затем выполняется ход от конца файла до начала ближайшей неупорядоченной части. К концу процесса количество ходов достигнет, таким образом, значения М-1, причем с каждым разом ход будет все длиннее - начиная от сегмента размером 2Z и кончая сегментом размером МZ. Таким образом, в среднем размер прогона составит 0.5МZ. Этот размер и опредеяет среднюю сложность этапа. Для всех этапов получаем оценку 0.5МZ (М-1), откуда сложность метода поглощения составит T(М)=O(ZM^2).

            Этот метод годится для сортировки данных в маленьких файлах, тогда как в случаях, когда количество частей файла М велико, он имеет низкую производительность.