Сортировку файлов называют внешней сортировкой потому что сортируются последовательности элементов

Обновлено: 15.01.2025

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

Разумеется, в этом случае, когда размер файла не велик и объём оперативной памяти достаточен для его размещения, можно прочитать файл в память, отсортировать полученный массив одним из методов внутренней сортировки, а затем отсортированный массив записать в файл. Однако, это не является типичным случаем; более того, в системах обработки данных такая ситуация встречается крайне редко.

Далее мы рассмотрим общий случай, когда сортируемый файл имеет объём значительно больше, чем объём доступный оперативной памяти. Такой файл сортируется поэтапно.

Наиболее часто внешняя сортировка применяется в системах управления базами данных при выполнении запросов, и от эффективности применяемых методов существенно зависит производительность СУБД.

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

Сортировка простым слиянием

Слияние означает объединение двух или более последовательностей в одну упорядоченную последовательность с помощью повторяющегося выбора из доступных в данный момент элементов [3].

Одна из сортировок на основе слияния называется сортировкой простым слиянием. Она выполняется следующим образом.

1. Файл А разбивается на два файла В и С. При этом первый элемент файла А помещается в файл В, второй элемент в файл С, третий - в файл В, четвертый - в файл С и т.д.
2. Файлы В и С сливаются в файл А, при этом одиночные элементы образуют упорядоченные пары.
3. Полученный файл А вновь обрабатывается, как указано в пунктах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
4. Повторяя предыдущие шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл.

Рассмотрим работу алгоритма на примере (рис. 82). Пусть задан файл А:

Рис. 82. Двухфазная сортировка простым слиянием

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

Количество проходов: к = [Iog2n], Файлы А, В и С будут 0(log2n) раз прочитаны и столько же раз записаны. По определению при каждом проходе все множество из п элементов копируется ровно 1 раз, следовательно, общее число пересылок М = n-[log2n]. Число сравнений еще меньше, чем М, так как при копировании остатка последовательности сравнения не производятся.

Поскольку сортировка слиянием использует внешнюю память, то временные затраты на операцию пересылки на несколько порядков превышают временные затраты на операции сравнения.

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

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

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

Однофазная сортировка простым слиянием

Фаза разделения файла А на два файла В и С не относится к сортировке. Она непродуктивна, хотя и занимает половину всех операций по переписи.

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

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

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

Рассмотрим выполнение однофазной сортировки на примере (рис. 83). Пусть задан файл Л:

Внешняя сортировка - это класс алгоритмов сортировки , которые могут обрабатывать огромные объемы данных . Внешняя сортировка требуется, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно RAM ), и вместо этого они должны находиться в более медленной внешней памяти , обычно на жестком диске . Таким образом, алгоритмы внешней сортировки являются алгоритмами внешней памяти и, следовательно, применимы в модели вычислений с внешней памятью .

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

СОДЕРЖАНИЕ

Модель

Алгоритмы внешней сортировки могут быть проанализированы в модели внешней памяти . В этой модели кэш или внутренняя память размера M и неограниченная внешняя память разделены на блоки размером B , а время работы алгоритма определяется количеством передач памяти между внутренней и внешней памятью. Как и их аналоги, не обращающие внимания на кэш , асимптотически оптимальные алгоритмы внешней сортировки достигают времени работы (в нотации Big O ), равного . О ( N B бревно M B ⁡ N B ) > \ log _ > > \ right)>

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

Одним из примеров внешней сортировки является алгоритм внешней сортировки слиянием , который представляет собой алгоритм слияния K-way . Он сортирует фрагменты, каждый из которых помещается в ОЗУ, а затем объединяет отсортированные фрагменты вместе.

Алгоритм сначала сортирует M элементов за раз и помещает отсортированные списки обратно во внешнюю память. Затем рекурсивно делает -WAY слияние на этих отсортированных списков. Чтобы выполнить это слияние, элементы B из каждого отсортированного списка загружаются во внутреннюю память, и минимум выводится повторно. M B >>

Например, для сортировки 900 мегабайт данных с использованием всего 100 мегабайт оперативной памяти:

Прочтите 100 МБ данных в основной памяти и отсортируйте их обычным способом, например быстрой сортировкой .
Запишите отсортированные данные на диск.
Повторяйте шаги 1 и 2 до тех пор, пока все данные не будут разделены на отсортированные фрагменты размером 100 МБ (есть 900 МБ / 100 МБ = 9 фрагментов), которые теперь необходимо объединить в один выходной файл.
Прочтите первые 10 МБ (= 100 МБ / (9 фрагментов + 1)) каждого отсортированного фрагмента во входные буферы в основной памяти и выделите оставшиеся 10 МБ для буфера вывода. (На практике это может обеспечить лучшую производительность, если увеличить выходной буфер, а входной - немного меньше.)
Выполните 9-этапное слияние и сохраните результат в выходном буфере. Каждый раз, когда буфер вывода заполняется, записывайте его в окончательно отсортированный файл и очищайте его. Когда какой-либо из 9 входных буферов опустеет, заполните его следующими 10 МБ из связанных с ним отсортированных порций размером 100 МБ до тех пор, пока данные из этого фрагмента не перестанут быть доступными. Это ключевой шаг, который заставляет внешнюю сортировку слиянием работать извне - поскольку алгоритм слияния выполняет только один проход последовательно через каждый из фрагментов, каждый фрагмент не нужно загружать полностью; скорее, при необходимости могут быть загружены последовательные части блока.

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

Дополнительные пропуска

Предыдущий пример представляет собой двухпроходную сортировку: сначала сортировка, затем слияние. Сортировка заканчивается одним k- way слиянием, а не серией двусторонних проходов слияния, как при типичной сортировке слиянием в памяти. Это связано с тем, что каждый проход слияния считывает и записывает каждое значение с диска и на диск, поэтому уменьшение количества проходов более чем компенсирует дополнительные затраты на слияние k- way.

Ограничение однопроходного слияния состоит в том, что по мере увеличения количества блоков память будет разделена на большее количество буферов, поэтому каждый буфер будет меньше. В конце концов, операции чтения становятся настолько малыми, что больше времени тратится на поиски диска, чем на передачу данных. Типичный магнитный жесткий диск может иметь время доступа 10 мс и скорость передачи данных 100 МБ / с, поэтому каждый поиск занимает столько же времени, сколько и передача 1 МБ данных.

Таким образом, для сортировки, скажем, 50 ГБ в 100 МБ ОЗУ, использование одного прохода слияния с 500 путями неэффективно: мы можем прочитать только 100 МБ / 501 ≈ 200 КБ из каждого фрагмента за один раз, поэтому 5/6 из время диска уходит на поиск. Использование двух проходов слияния решает проблему. Тогда процесс сортировки может выглядеть так:

Выполните начальный этап сортировки фрагментов, как и раньше, чтобы создать отсортированные фрагменты размером 500 × 100 МБ.
Запустите первый проход слияния, объединяя порции 25 × 100 МБ за раз, в результате чего получаются отсортированные фрагменты размером 20 × 2,5 ГБ.
Выполните второй проход слияния, чтобы объединить отсортированные фрагменты размером 20 × 2,5 ГБ в один отсортированный результат размером 50 ГБ.

Хотя для этого требуется дополнительный проход данных, каждое чтение теперь занимает 4 МБ, поэтому на поиск тратится только 1/5 времени диска. Повышение эффективности передачи данных во время проходов слияния (от 16,6% до 80% - почти 5-кратное улучшение) более чем компенсирует удвоенное количество проходов слияния.

Как и сортировка в памяти, эффективная внешняя сортировка требует времени O ( n log n ): линейное увеличение размера данных требует логарифмического увеличения числа проходов, и каждый проход требует линейного числа операций чтения и записи. При использовании больших объемов памяти, предоставляемых современными компьютерами, логарифмический коэффициент растет очень медленно. При разумных предположениях, по крайней мере, 500 ГБ данных можно отсортировать с использованием 1 ГБ основной памяти, прежде чем третий проход станет предпочтительным, и во много раз больше данных можно отсортировать до того, как четвертый проход станет полезным. Носители с малым временем поиска, такие как твердотельные накопители (SSD), также увеличивают объем, который можно отсортировать, прежде чем дополнительные проходы улучшат производительность.

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

Сортировка по внешнему распределению

Сортировка по внешнему распределению аналогична быстрой сортировке . Алгоритм находит приблизительно точки поворота и использует их для разделения N элементов на подмассивы приблизительно одинакового размера, каждый из которых меньше следующего, а затем выполняет рекурсию до тех пор, пока размеры подмассивов не станут меньше размера блока . Когда подмассивы меньше размера блока, сортировку можно выполнить быстро, потому что все операции чтения и записи выполняются в кэше , а в модели внешней памяти требуются операции. M B >> О ( 1 )

Однако нахождение точных точек поворота было бы недостаточно быстрым, чтобы сделать сортировку по внешнему распределению асимптотически оптимальной . Вместо этого мы находим чуть меньше разворотов. Чтобы найти эти точки поворота, алгоритм разбивает N входных элементов на части , берет все элементы и рекурсивно использует алгоритм медианы медиан для поиска точек поворота. M B >> N M >> M 16 B <\ displaystyle <\ sqrt <\ tfrac >>> M B <\ displaystyle <\ sqrt <\ tfrac >>>

Существует двойственность или фундаментальное сходство между алгоритмами, основанными на слиянии и распределении.

Представление

Тест Sort Benchmark , созданный компьютерным ученым Джимом Греем , сравнивает внешние алгоритмы сортировки, реализованные с использованием точно настроенного оборудования и программного обеспечения. В успешных реализациях используются несколько приемов:

Одним из примеров внешней сортировки является алгоритм внешней сортировки слиянием, который сортирует фрагменты, каждый из которых помещается в ОЗУ, а затем объединяет отсортированные фрагменты вместе. Сначала мы делим файл на прогоны так, чтобы размер прогона был достаточно мал, чтобы поместиться в основную память. Затем сортируйте каждый прогон в основной памяти, используя алгоритм сортировки слиянием. Наконец, объедините полученные прогоны вместе в последовательно большие прогоны, пока файл не будет отсортирован.

Ниже приведены шаги, используемые в реализации C ++.

using namespace std;

// Элемент, который будет сохранен

// индекс массива, из которого взят элемент

// Прототип служебной функции для замены двух минимальных узлов кучи

void swap(MinHeapNode* x, MinHeapNode* y);

// Класс для Min Heap

MinHeapNode* harr; // указатель на массив элементов в куче

int heap_size; // размер кучи мин

// Конструктор: создает минимальную кучу заданного размера

MinHeap(MinHeapNode a[], int size);

// сложить поддерево с корнем по заданному индексу

void MinHeapify( int );

// получить индекс левого потомка узла по индексу i

// получить индекс правого потомка узла по индексу i

int right( int i)

// чтобы получить рут

// заменить корень новым узлом x и heapify ()

void replaceMin(MinHeapNode x)

// Конструктор: строит кучу из заданного массива a []
// заданного размера

MinHeap::MinHeap(MinHeapNode a[], int size)

harr = a; // сохранить адрес массива

int i = (heap_size - 1) / 2;

// Рекурсивный метод кучи ветки дерева с корнем
// по заданному индексу. Этот метод предполагает, что
// поддеревья уже сложены

void MinHeap::MinHeapify( int i)

int smallest = i;

if (l < heap_size && harr[l].element < harr[i].element)

if (r < heap_size && harr[r].element < harr[smallest].element)

// Утилита для замены двух элементов

void swap(MinHeapNode* x, MinHeapNode* y)

MinHeapNode temp = *x;

// Объединяет два подмассива arr [].
// Первый подмассив - это arr [l..m]
// Второй подмассив - это arr [m + 1..r]

void merge( int arr[], int l, int m, int r)

int n1 = m - l + 1;

/ * создать временные массивы * /

/ * Копировать данные во временные массивы L [] и R [] * /

for (i = 0; i < n1; i++)

for (j = 0; j < n2; j++)

/ * Объединить временные массивы обратно в arr [l..r] * /

i = 0; // Начальный индекс первого подмассива

j = 0; // Начальный индекс второго подмассива

k = l; // Начальный индекс объединенного подмассива

/ * Копировать оставшиеся элементы L [], если есть

/ * Скопировать оставшиеся элементы R [], если есть

/ * l - левый индекс, а r - правый индекс

подмассив arr для сортировки * /

void mergeSort( int arr[], int l, int r)

// То же, что (l + r) / 2, но избегает переполнения для

int m = l + (r - l) / 2;

// Сортировка первой и второй половин

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

FILE * openFile( char * fileName, char * mode)

FILE * fp = fopen (fileName, mode);

perror ( "Error while opening the file.\n" );

// Объединяет k отсортированных файлов. Имена файлов предполагаются
// быть 1, 2, 3, . k

void mergeFiles( char *output_file, int n, int k)

for ( int i = 0; i < k; i++)

// преобразовать i в строку

snprintf(fileName, sizeof (fileName), "%d" , i);

// Открываем выходные файлы в режиме чтения.

in[i] = openFile(fileName, "r" );

// Финальный выходной файл

FILE *out = openFile(output_file, "w" );

// Создать минимальную кучу с k узлами кучи. Каждый узел кучи

// имеет первый элемент выходного файла нуля

MinHeapNode* harr = new MinHeapNode[k];

for (i = 0; i < k; i++)

// прерывание, если нет выходного файла пусто и

// индекс у меня будет нет. входных файлов

if ( fscanf (in[i], "%d " , &harr[i].element) != 1)

harr[i].i = i; // Индекс чистого файла вывода

MinHeap hp(harr, i); // Создать кучу

// Теперь один за другим получаем минимальный элемент из min

// куча и заменить его следующим элементом.

// работать до тех пор, пока все заполненные входные файлы не достигнут EOF

// Получить минимальный элемент и сохранить его в выходном файле

MinHeapNode root = hp.getMin();

fprintf (out, "%d " , root.element);

// Найти следующий элемент, который заменит текущий

// корень кучи. Следующий элемент принадлежит тому же

// входной файл в качестве текущего минимального элемента.

if ( fscanf (in[root.i], "%d " , &root.element) != 1 )

// Заменить корень на следующий элемент входного файла

// закрываем входные и выходные файлы

for ( int i = 0; i < k; i++)

// Используя алгоритм сортировки слиянием, создаем начальные прогоны
// и делим их поровну между выходными файлами

void createInitialRuns( char *input_file, int run_size,

// Для большого входного файла

FILE *in = openFile(input_file, "r" );

// выводим скретч файлы

for ( int i = 0; i < num_ways; i++)

// преобразовать i в строку

snprintf(fileName, sizeof (fileName), "%d" , i);

// Открываем выходные файлы в режиме записи.

out[i] = openFile(fileName, "w" );

// выделить достаточно большой динамический массив

// для размещения прогонов размером run_size

int * arr = ( int *) malloc (run_size * sizeof ( int ));

bool more_input = true ;

int next_output_file = 0;

// записать элементы run_size в arr из входного файла

for (i = 0; i < run_size; i++)

if ( fscanf (in, "%d " , &arr[i]) != 1)

// сортировка массива с использованием сортировки слиянием

mergeSort(arr, 0, i - 1);

// записываем записи в соответствующий рабочий файл

// не могу предположить, что цикл выполняется до run_size

// поскольку длина последнего прогона может быть меньше, чем run_size

for ( int j = 0; j < i; j++)

fprintf (out[next_output_file], "%d " , arr[j]);

// закрываем входные и выходные файлы

for ( int i = 0; i < num_ways; i++)

// Для сортировки данных, хранящихся на диске

void externalSort( char * input_file, char *output_file,

int num_ways, int run_size)

// читаем входной файл, создаем начальные прогоны,

// и присваиваем прогоны к исходным выходным файлам

createInitialRuns(input_file, run_size, num_ways);

// Объединяем прогоны, используя K-way merging

mergeFiles(output_file, run_size, num_ways);

// Программа драйвера для тестирования выше

// Количество разделов входного файла.

int num_ways = 10;

// Размер каждого раздела

int run_size = 1000;

char input_file[] = "input.txt" ;

char output_file[] = "output.txt" ;

FILE * in = openFile(input_file, "w" );

srand ( time (NULL));

for ( int i = 0; i < num_ways * run_size; i++)

fprintf (in, "%d " , rand ());

externalSort(input_file, output_file, num_ways,

Этот код не будет работать на онлайн-компиляторе, так как требует разрешения на создание файла. Когда запускается локальный компьютер, он генерирует пример входного файла «input.txt» с 10000 случайными числами. Он сортирует числа и помещает отсортированные числа в файл «output.txt». Он также генерирует файлы с именами 1, 2, .. для хранения отсортированных прогонов.

Эта статья предоставлена Aditya Goel . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Следует пояснить, почему речь идет именно о последовательных файлах, т.е. о файлах, которые можно читать запись за записью в последовательном режиме, а писать можно только после последней записи. Методы внешней сортировки появились, когда наиболее распространенными устройствами внешней памяти были магнитные ленты. Для лент чисто последовательный доступ был абсолютно естественным. Когда произошел переход к запоминающим устройствам с магнитными дисками, обеспечивающими "прямой" доступ к любому блоку информации, казалось, что чисто последовательные файлы потеряли свою актуальность. Однако это ощущение было ошибочным.

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

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

Сортировка со слиянием

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

Один из популярных алгоритмов внутренней сортировки со слияниями основан на следующих идеях (для простоты будем считать, что число элементов в массиве, как и в нашем примере, является степенью числа 2). Сначала поясним, что такое слияние. Пусть имеются два отсортированных в порядке возрастания массива p[1], p[2], . p[n] и q[1], q[2], . q[n] и имеется пустой массив r[1], r[2], . r[2n], который мы хотим заполнить значениями массивов p и q в порядке возрастания. Для слияния выполняются следующие действия: сравниваются p[1] и q[1], и меньшее из значений записывается в r[1]. Предположим, что это значение p[1]. Тогда p[2] сравнивается с q[1] и меньшее из значений заносится в r[2]. Предположим, что это значение q[1]. Тогда на следующем шаге сравниваются значения p[2] и q[2] и т.д., пока мы не достигнем границ одного из массивов. Тогда остаток другого массива просто дописывается в "хвост" массива r.

Пример слияния двух массивов показан на рисунке 1.

Рис. 1

Для сортировки со слиянием массива a[1], a[2], . a[n] заводится парный массив b[1], b[2], . b[n]. На первом шаге производится слияние a[1] и a[n] с размещением результата в b[1], b[2], слияние a[2] и a[n-1] с размещением результата в b[3], b[4], . слияние a[n/2] и a[n/2+1] с помещением результата в b[n-1], b[n]. На втором шаге производится слияние пар b[1], b[2] и b[n-1], b[n] с помещением результата в a[1], a[2], a[3], a[4], слияние пар b[3], b[4] и b[n-3], b[n-2] с помещением результата в a[5], a[6], a[7], a[8], . слияние пар b[n/2-1], b[n/2] и b[n/2+1], b[n/2+2] с помещением результата в a[n-3], a[n-2], a[n-1], a[n]. И т.д. На последнем шаге, например (в зависимости от значения n), производится слияние последовательностей элементов массива длиной n/2 a[1], a[2], . a[n/2] и a[n/2+1], a[n/2+2], . a[n] с помещением результата в b[1], b[2], . b[n].

Для случая массива, используемого в наших примерах, последовательность шагов показана в таблице 1.

Читайте также: