C++で学ぶ外部ソート（External Sorting）の仕組みと実装例

外部ソート（External Sorting）とは

外部ソートは、膨大な量のデータを扱えるカテゴリのソートアルゴリズムです。この手法は、メインメモリ（RAM）には収まりきらず、補助記憶装置（ハードディスク）上に保存されているような、大きなメモリを必要とするデータセットのソートに適用されます。

外部ソートの基本的な考え方

外部ソートで用いられるソートの考え方は、マージソート（merge sort）と非常に似ています。マージソートと同様に、次の2つのフェーズで構成されます。

• ソートフェーズ：メモリに収まるサイズの小さなデータセットをそれぞれソートします。
• マージフェーズ：ソート済みの小さなデータセットを1つのデータセットに統合します。

外部ソートは、一度に処理できない巨大なデータセットに対して使用されます。データはまず小さなチャンク（塊）に分割され、各チャンクがソートされた後、データファイルとして保存されます。

アルゴリズムの手順

1. ステップ1：ファイルから入力データを読み込み、メモリサイズ単位のデータセットとして取り込みます。
2. ステップ2：各ミニデータセットをマージソートを用いてソートします。
3. ステップ3：ソート済みのデータをファイルに保存します。
4. ステップ4：ソート済みの各データファイルをマージ（統合）します。

アルゴリズムの動作を示すサンプルプログラム

C++での実装例

#include <bits/stdc++.h>
using namespace std;

struct MinHeapNode {

    int element;
    int i;
};

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

class MinHeap {

    MinHeapNode* harr;
    int heap_size;

    public:
        MinHeap(MinHeapNode a[], int size);
        void MinHeapify(int);
        int left(int i) {
          return (2 * i + 1);
        }
        int right(int i) {
            return (2 * i + 2);
        }
        MinHeapNode getMin() {
            return harr[0];
        }
        void replaceMin(MinHeapNode x) {
            harr[0] = x;
            MinHeapify(0);
        }
};

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;
}

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];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    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++];
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}

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

    if (l < r) {
        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;
}

void mergeData(char* opFile, int n, int k) {

    FILE* in[k];
    for (int i = 0; i < k; i++) {
        char fileName[2];
        snprintf(fileName, sizeof(fileName), "%d", i);
        in[i] = openFile(fileName, "r");
    }
    FILE* out = openFile(opFile, "w");
    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;
    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 initialiseData( char* ipFile, int memory, int num_ways) {

    FILE* in = openFile(ipFile, "r");
    FILE* out[num_ways];
    char fileName[2];
    for (int i = 0; i < num_ways; i++) {

        snprintf(fileName, sizeof(fileName), "%d", i);
        out[i] = openFile(fileName, "w");
    }
    int* arr = (int*)malloc( memory * sizeof(int));
    bool more_input = true;
    int next_opFile = 0;

    int i;
    while (more_input) {
        for (i = 0; i < memory; i++) {
            if (fscanf(in, "%d ", &arr[i]) != 1) {
                more_input = false;
                break;
            }
        }
        mergeSort(arr, 0, i - 1);
        for (int j = 0; j < i; j++)
            fprintf(out[next_opFile], "%d ", arr[j]);
        next_opFile++;
    }
    for (int i = 0; i < num_ways; i++)
        fclose(out[i]);

    fclose(in);
}

void externalSort( char* ipFile, char* opFile, int num_ways, int memory) {

    initialiseData(ipFile, memory, num_ways);
    mergeData(opFile, memory, num_ways);
}

int main() {

    int num_ways = 10;
    int memory = 1000;

    char ipFile[] = "inputFile.txt";
    char opFile[] = "outputFile.txt";

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

    srand(time(NULL));
    for (int i = 0; i < num_ways * memory; i++)
        fprintf(in, "%d ", rand());
    fclose(in);
    externalSort(ipFile, opFile, num_ways, memory);
    return 0;
}

コードのポイント解説

• MinHeapNode構造体：要素値（element）と、その要素が属するファイルの番号（i）を保持します。
• MinHeapクラス：複数のファイルの先頭要素から最小値を効率的に取り出すための最小ヒープを実装しています。
• mergeSort関数：メモリに読み込んだ各チャンクのデータをソートします。
• initialiseData関数：入力ファイルをメモリサイズごとに分割して読み込み、各チャンクをソートした上で複数の一時ファイルに書き出します（ソートフェーズ）。
• mergeData関数：最小ヒープを利用したk-wayマージにより、すべてのソート済みファイルを1つの出力ファイルに統合します（マージフェーズ）。

入力と出力

入力データとしては順序がバラバラのデータファイル（inputFile.txt）を使用し、処理の結果として出力ファイル（outputFile.txt）にはソート済みの配列が書き出されます。このように外部ソートを用いることで、メインメモリの容量を超える大規模なデータでも効率的にソートすることが可能になります。