Специальные методы сортировки a

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

Теперь мы переходим к рассмотрению другой абстрактной задачи сортировки. Она возникает, когда сортируемый файл настолько велик, что не помещается целиком в оперативной памяти компьютера. Для описания таких ситуаций используется термин внешняя сортировка (external sorting). Существует множество различных видов устройств внешней сортировки, которые накладывают различные ограничения на элементарные операции, применяемые при их реализации. Все же будет полезно изучить методы сортировки, использующие две примитивные базовые операции: операцию считать данные из внешнего запоминающего устройства в оперативную память и операцию записать данные из оперативной памяти на внешнее запоминающее устройство. Предполагается, что стоимость этих двух операций настолько выше стоимости примитивных вычислительных операций, что последние можно полностью игнорировать. Например, в этой абстрактной модели полностью игнорируются затраты на сортировку в оперативной памяти! При очень большой оперативной памяти и неэффективных методах сортировки это предположение может оказаться неверным, но при расчете общей стоимости внешней сортировки в практических ситуациях эти затраты обычно можно учесть дополнительными коэффициентами.
В силу многообразия характеристик и стоимости внешних запоминающих устройств разработка методов внешней сортировки сильно зависит от состояния технологии на текущий момент. Эти методы могут оказаться очень сложными, а их производительность зависит от многих параметров; и в исследовании методов внешней сортировки могут оказаться недооцененными и невостребованными искусные методы - только в силу тех или иных изменений в технологии. По этой причине в данном разделе мы не будем заниматься вопросами разработки конкретных реализаций, а рассмотрим общие принципы внешней сортировки.
Кроме высокой стоимости операций чтения-записи, часто возникают и другие жесткие требования, предъявляемые к доступу к данным конкретными внешними устройствами. Например, для большинства типов устройств операции чтения и записи между внешним запоминающим устройством и оперативной памятью обычно наиболее эффективно выполняются при передаче крупных блоков данных. Кроме этого, внешние устройства очень большой емкости часто создаются так, что максимальной производительности они достигают при последовательном доступе к блокам данных. Например, невозможно прочитать элементы данных, находящиеся в конце магнитной ленты, не просмотрев элементы, хранящиеся в начале ленты - на практике доступ к элементам, записанным на магнитной ленте, ограничен теми элементами, которые расположены рядом с последними прочитанными элементами. Тем же свойством обладают и некоторые современные технологии. Поэтому в данном разделе мы сосредоточимся на изучении методов, которые последовательно считывают и записывают крупные блоки данных, неявно предполагая, что для машин и устройств интересующих нас типов доступны быстродействующие реализации этого вида доступа к данным.
При выполнении считывания или записи нескольких различных файлов мы будем полагать, что все эти файлы находятся на различных внешних запоминающих устройствах. На старых вычислительных машинах, в которых файлы хранились на сменных магнитных лентах, это предположение было обязательным требованием. При работе с магнитными дисками становятся возможными реализации алгоритмов, использующих единственное внешнее устройство, но все же обычно работа с несколькими устройствами более эффективна.
Первым шагом при создании высокоэффективной программы сортировки очень больших файлов является реализация эффективной программы копирования файла. Вторым шагом может быть реализация программы инвертирования порядка записей в файле. Все трудности, с которыми приходится сталкиваться при решении этих задач, возникают и при реализации внешней сортировки. (В процессе сортировки иногда приходится выполнять одну из этих операций.) Цель использования абстрактной модели состоит в том, чтобы отделить вопросы построения таких реализаций от вопросов разработки алгоритма.
Рассматриваемые нами алгоритмы сортировки организованы в виде последовательности проходов по всем данным, и стоимость того или иного метода внешней сортировки обычно определяется просто подсчетом количества таких проходов. Чаще всего требуется сравнительно небольшое число проходов - может быть, десять или меньше. Из этого следует, что уменьшение этого числа проходов хотя бы на один существенно повышает производительность алгоритма. Наше основное предположение заключается в том, что основную долю времени выполнения конкретного метода внешней сортировки составляют операции ввода и вывода данных. Следовательно, время выполнения внешней сортировки можно вычислить, умножив число выполняемых ею проходов на время, необходимое для считывания и записи всего файла.
Короче говоря, абстрактная модель внешней сортировки, которой мы в дальнейшем будем пользоваться, построена на предположении, что сортируемый файл слишком велик, чтобы полностью разместить его в оперативной памяти, и зависит от двух других параметров: времени выполнения сортировки (число проходов по данным) и количества доступных внешних устройств. Мы полагаем, что в нашем распоряжении имеются

• 
  N сортируемых записей, расположенных на внешнем устройстве,
  
• 
  объем оперативной памяти, достаточный для размещения M записей, и
  
• 
  2Р внешних устройств, которыми можно пользоваться во время сортировки.
  

Пометим внешнее устройство, на котором находится файл входных данных, меткой 0, а остальные внешние устройства - метками 1, 2, ..., 2P - 1. Цель сортировки заключается в том, чтобы поместить записи на устройство 0 в отсортированном виде. Как мы вскоре увидим, существует зависимость между P и общим временем выполнения сортировки, и было бы хорошо получить явное выражение этой зависимости, чтобы иметь возможность сравнивать различные стратегии.
Существует много причин, в силу которых эта идеализированная модель может не соответствовать действительности. Тем не менее, как и всякая хорошая абстрактная модель, она отображает наиболее важные аспекты реальной ситуации и очерчивает точные рамки, внутри которых можно проводить исследования алгоритмических идей, многие из которых непосредственно применяются в практических ситуациях.
Большая часть методов внешней сортировки основана на следующем общем принципе: выполняется первый проход по сортируемому файлу, в процессе которого производится его разбиение на блоки с размером, примерно равным объему доступной оперативной памяти, и эти блоки сортируются. Затем отсортированные блоки сливаются - если необходимо, за несколько проходов по файлу, при этом с каждым проходом размер отсортированных блоков возрастает, пока весь файл не станет упорядоченным. Такой подход называется сортировкой-слиянием (sort-merge), он с успехом используется на практике с пятидесятых годов прошлого столетия, когда компьютеры впервые стали широко применяться в коммерческих приложениях.
Простейшая стратегия сортировки-слияния, называемая сбалансированное многопутевое слияние (balanced multiway merging), показана на рис. 11.12. Этот метод состоит из прохода, выполняющего начальное распределение (initial distribution), за которым следуют несколько проходов многопутевого слияния (multiway merging pass).
Во время начального прохода входные данные распределяются по внешним устройствам P, P + 1, ..., 2P - 1 в виде отсортированных блоков данных по M записей (за исключением, возможно, последнего блока, который меньше остальных, если N не кратно M). Такое распределение нетрудно выполнить: мы считываем первые M записей с входного устройства, сортируем их и записываем упорядоченный блок на устройство P ; затем считываем с входного устройства следующие M записей, сортируем их и записываем упорядоченный блок на устройство P + 1 и т.д. Если мы достигли устройства 2P - 1, и еще есть необработанные данные (т.е. если N > PM), мы записываем на устройство P второй отсортированный блок, затем второй блок на устройство P + 1 и т.д., до исчерпания всех входных данных. По завершении распределения количество отсортированных блоков, размещенных на каждом устройстве, равно N/PM, округленному до ближайшего целого числа в ту или другую сторону. Если N кратно M, то размеры всех блоков равны M (если это не так, то размер M имеют все блоки, за исключением последнего). Для небольших N количество блоков может оказаться меньше P, тогда одно или несколько устройств будут пустыми.
На первом проходе многопутевого слияния устройства в интервале от P до 2P - 1 рассматриваются как входные, а устройства в интервале от 0 до P - 1 как выходные.