Рубрики

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

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

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

Необходимое условие для алгоритма / кода:
MergeSort : используется для сортировки отдельных прогонов (прогон — это часть файла, которая достаточно мала для размещения в основной памяти)
Merge K Sorted Arrays : Используется для объединения отсортированных трасс.

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

Inputs:  
input_file  : Name of input file. input.txt
output_file : Name of output file, output.txt
run_size : Size of a run (can fit in RAM)
num_ways : Number of runs to be merged

Output:
1) Read input_file such that at most 'run_size' elements
   are read at a time. Do following for the every run read
   in an array.
      a) Sort the run using MergeSort.
      b) Store the sorted run in a temporary file, say 'i' 
         for i'th run.
2) Merge the sorted files using the approach discussed here

Следующее — реализация C ++ вышеупомянутых шагов.

// C ++ программа для реализации внешней сортировки с использованием
// Сортировка слиянием
#include <bits/stdc++.h>

using namespace std;

  

struct MinHeapNode

{

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

    int element;

  

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

    int i;

};

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

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

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

class MinHeap

{

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

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

  

public:

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

    MinHeap(MinHeapNode a[], int size);

  

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

    void MinHeapify(int);

  

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

    int left(int i) { return (2 * i + 1); }

  

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

    int right(int i) { return (2 * i + 2); }

  

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

    MinHeapNode getMin() {  return harr[0]; }

  

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

    // новый корень

    void replaceMin(MinHeapNode x)

    {

        harr[0] = x;

        MinHeapify(0);

    }

};

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

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

{

    heap_size = size;

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

    int i = (heap_size - 1) / 2;

    while (i >= 0)

    {

        MinHeapify(i);

        i--;

    }

}

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

void MinHeap::MinHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

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

        smallest = l;

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

        smallest = r;

    if (smallest != i)

    {

        swap(&harr[i], &harr[smallest]);

        MinHeapify(smallest);

    }

}

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

void swap(MinHeapNode* x, MinHeapNode* y)

{

    MinHeapNode temp = *x;

    *x = *y;

    *y = temp;

}

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

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

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 = r - m;

  

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

    int L[n1], R[n2];

  

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

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

        L[i] = arr[l + i];

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

        R[j] = arr[m + 1 + j];

  

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

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

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

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

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

            arr[k++] = L[i++];

        else

            arr[k++] = R[j++];

    }

  

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

       любые * /

    while (i < n1)

        arr[k++] = L[i++];

  

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

       любые * /

    while(j < n2)

        arr[k++] = R[j++];

}

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

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

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

{

    if (l < r)

    {

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

        // большие л и ч

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

  

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

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);

  

        merge(arr, l, m, r);

    }

}

  

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

{

    FILE* fp = fopen(fileName, mode);

    if (fp == NULL)

    {

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

        exit(EXIT_FAILURE);

    }

    return fp;

}

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

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

{

    FILE* in[k];

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

    {

        char fileName[2];

  

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

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

  

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

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

    }

  

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

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

  

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

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

    MinHeapNode* harr = new MinHeapNode[k];

    int i;

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

    {

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

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

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

            break;

  

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

    }

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

  

    int count = 0;

  

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

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

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

    while (count != i)

    {

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

        MinHeapNode root = hp.getMin();

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

  

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

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

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

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

        {

            root.element = INT_MAX;

            count++;

        }

  

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

        hp.replaceMin(root);

    }

  

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

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

        fclose(in[i]);

  

    fclose(out);

}

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

void createInitialRuns(char *input_file, int run_size,

                       int num_ways)

{

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

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

  

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

    FILE* out[num_ways];

    char fileName[2];

    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;

  

    int i;

    while (more_input)

    {

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

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

        {

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

            {

                more_input = false;

                break;

            }

        }

  

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

        mergeSort(arr, 0, i - 1);

  

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

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

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

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

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

  

        next_output_file++;

    }

  

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

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

        fclose(out[i]);

  

    fclose(in);

}

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

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 main()

{

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

    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());

  

    fclose(in);

  

    externalSort(input_file, output_file, num_ways,

                run_size);

  

    return 0;

}

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

Ссылки :
https://en.wikipedia.org/wiki/External_sorting
http://web.eecs.utk.edu/~leparker/Courses/CS302-Fall06/Notes/external-sorting2.html

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes