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

Тимофей: Мы с Гошей определились с алгоритмами для решения задач Кондратия!

Алла: И что за алгоритмы вы взяли?

Гоша: Для определения нарушителей применим сортировку подсчётом, а для сортировки городов по «треш-индексу» — сортировку слиянием.

Рита: Вы что, разве не слышали новости? Прогнозируется настолько быстрый прирост жителей, что данные не поместятся в оперативной памяти одного компьютера.

Алла: Как не поместятся?

Рита: Очень просто. Для работы алгоритмов, про которые Тимофей рассказывал, все обрабатываемые данные нужно хранить в памяти компьютера. Но если объём данных больше, чем объём памяти, это сделать не получится. Алгоритм не сможет отработать.

Гоша: Что же теперь делать?

Тимофей: Отставить панику! Это не первый случай в истории, когда данных очень много.

Вообще при большом объёме данных можно выделить две проблемы:

Для их сортировки недостаточно оперативной памяти. Поэтому приходится пользоваться памятью на жёстком диске. А она работает ощутимо медленнее оперативной.
Сортировка занимает много времени. Отсортировать массивы из миллиардов элементов даже при хорошо реализованных алгоритмах — непростая задача.

Первая проблема — как раз наш случай. Нам нужно отсортировать данные, когда не хватает оперативной памяти. Такая сортировка называется внешней. Когда мы сортируем данные с помощью сортировки слиянием в оперативной памяти, на стадии слияния каждый из входных массивов последовательно просматривается с начала до конца, а выходной массив записывается последовательно.

Подобный алгоритм может быть полезен при работе с лентами. Лента — абстрактная структура данных, в которой содержатся данные для сортировки. Рассмотрим операцию слияния двух лент. Она называется двухпутевое слияние. Входные данные — две отсортированные ленты, выходные — третья отсортированная лента.

Чанк — фрагмент данных, который помещается в оперативной памяти. Решим задачу, задействуя всю доступную оперативную память. При этом будем обрабатывать за раз максимум фрагментов. Допустим, исходная лента содержит 8 чанков.

Первый этап:

Считываем первый чанк.
Сортируем его внутренней сортировкой — сортировкой в оперативной памяти.
Отправляем чанк на первую временную ленту.

На схеме исполнитель — абстракция, которая выполняет сортировку в оперативной памяти.

Второй этап:

Сортируем второй чанк.
Отправляем его на временную ленту.

Третий этап:

Сливаем первую и вторую временные ленты.

Таким же образом считываем, сортируем и выводим на временные ленты третий и четвертый чанки.

Временные ленты также сливаются.

Здесь мы не можем использовать меньшее количество лент.

Далее сливаем ленты, который содержат чанки 12 и 34. Получаем ленту 1234.

Чтобы получить ленту 5678 потребуются 4 временные ленты. А вместе с лентой 1234 — 5 лент.

Оценим сложность алгоритма. Количество внутренних сортировок равно количеству чанков в исходных данных —

k

Общая сложность внутренней сортировки равна:

Сложность каждой операции слияния — $O(n)$ .
Количество операций слияния — $O(\log k)$ .
Общая сложность — $O(n \log n)$ .
Сложность по памяти — $O(\log k)$ .

Сложность алгоритма с использованием внешней памяти не увеличилась по сравнению с алгоритмом в оперативной памяти.

Гоша: Здорово! Теперь мы можем решить обе задачи.