Ошибка сегментации сортировки слиянием только на больших массивах - PullRequest
Новая
       19

Ошибка сегментации сортировки слиянием только на больших массивах

0 голосов
/ 02 февраля 2020

Я работаю над реализацией нескольких различных методов сортировки, и по какой-то причине мой алгоритм сортировки слиянием не будет работать с большими наборами данных. Сортировка будет работать для 115 000 слов, но перестает работать, когда достигает 135 000 слов. Как только я получаю этот максимум, я получаю ошибку сегментации. Я не понимаю, откуда происходит ошибка сегмента. Сортировка успешно работает для текстовых файлов, содержащих строки от 5K до 125K.

Массив readFile инициализируется количеством слов в текстовом файле. При отладке кажется, что последние числа, которые передаются в функцию mergeSort(), следующие: 

#0  0x0000000000402a87 in merge (inputString=0x7fffffbde790, from=0, mid=67499, to=134999) at mergeSort.cpp:102
    n1 = 67500
    n2 = 67500
    i = 0
    j = 0
    k = 32767
    L = <error reading variable L (value requires 2160000 bytes, which is more than max-value-size)>
    R = <error reading variable R (value requires 2160000 bytes, which is more than max-value-size)>
#1  0x0000000000402921 in mergeSort (inputString=0x7fffffbde790, from=0, to=134999) at mergeSort.cpp:88
    mid = 67499

void mergeSort(string readFile[], int from, int to) {
    if (from < to) {
        int mid = from + (to - from) / 2;
        mergeSort(readFile, from, mid);
        mergeSort(readFile, mid + 1, to);
        merge(readFile, from, mid, to);
    }
}

void merge(string readFile[], int from, int mid, int to) {
    int n1 = mid - from + 1;
    int n2 = to - mid;

    string L[n1];
    string R[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = readFile[from + i];
    }
    for (int i = 0; i < n2; i++) {
        R[i] = readFile[mid + i + 1];
    }

    int i = 0;
    int j = 0;
    int k = from;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            readFile[k] = L[i];
            i++;
        } else {
            readFile[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        readFile[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        readFile[k] = R[j];
        j++;
        k++;
    }
}

1 Ответ

1 голос
/ 02 февраля 2020

Вы выделяете временные массивы как автоматические c переменные в функции merge. Когда размер этих массивов становится слишком большим, вам не хватает места в стеке, чтобы выделить их и получить неопределенное поведение (например, переполнение стека ).

Для обработки произвольно больших массивов вы должны выделить временные массивы с malloc или new и освободите их соответственно. Чтобы ограничить количество выделений, вы можете выделить временный массив в оболочке и передать его рекурсивно в функцию mergeSort.

Вот простое исправление, выделяющее временные массивы в функции merge: 

void merge(string readFile[], int from, int mid, int to) {
    int n1 = mid - from + 1;
    int n2 = to - mid;

    string *L = new string[n1];
    string *R = new string[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = readFile[from + i];
    }
    for (int i = 0; i < n2; i++) {
        R[i] = readFile[mid + i + 1];
    }

    int i = 0;
    int j = 0;
    int k = from;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            readFile[k] = L[i];
            i++;
        } else {
            readFile[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        readFile[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        readFile[k] = R[j];
        j++;
        k++;
    }
    delete[] L;
    delete[] R;
}

Вот более сложная версия, возможно, более эффективная, с выделением одного временного массива: 

void merge(string readFile[], size_t from, size_t mid, size_t to, string aux[]) {
    size_t i, j, k;

    for (i = from; i < to; i++) {
        aux[i] = readFile[i];
    }

    i = from;
    j = mid;
    k = from;

    while (i < mid && j < to) {
        if (aux[i] <= aux[j]) {
            readFile[k++] = aux[i++];
        } else {
            readFile[k++] = aux[j++];
        }
    }
    while (i < mid) {
        readFile[k++] = aux[i++];
    }
    while (j < to) {
        readFile[k++] = aux[j++];
    }
}

void mergeSort(string readFile[], size_t from, size_t to, string aux[]) {
    if (to - from > 1) {
        size_t mid = from + (to - from) / 2;
        mergeSort(readFile, from, mid, aux);
        mergeSort(readFile, mid, to, aux);
        merge(readFile, from, mid, to, aux);
    }
}

void mergeSort(string readFile[], size_t n) {
    string *aux = new string[n];
    mergeSort(readFile, 0, n, aux);
    delete[] aux;
}
...