Сортировка вставки вызывает ошибку сегментации: 11 после масштабирования

Question

Я написал простую реализацию сортировки вставками, чтобы попытаться избавиться от ржавчины и начать, как я надеюсь, лучшее понимание алгоритмов в целом. Файл содержит 20 миллионов случайных чисел. Код ниже:

#include <fstream>
#include <time.h>
#include <cstdlib>

using namespace std;

void insertionSort(double numbers[], int array_size);

int main() {
    int count;
    double twentyMMNumbers[20000000];
    ifstream inputFile;
    time_t now;
    time(&now);

    inputFile.open("20KRandomsNumbers.data");       //Opens input file
    if(inputFile.fail())
    {
        printf("Cannot open inputFile");
        exit(1);
    }

    count = 0;
    printf("%d\n",count);
    inputFile >> twentyMMNumbers[count];
    printf("%f\n",twentyMMNumbers[count]);
    while(inputFile)
    {   //While loop
        count++;
        if(count < 20000000)
            inputFile >> twentyMMNumbers[count];
    }
    inputFile.close();  

    printf("%s\n", ctime(&now));    //BEFORE
    insertionSort(twentyMMNumbers, 20000000); //Insertion Sort 20KRandomNumbers
    printf("%s\n", ctime(&now)); //AFTER
    for(int i = 0; i < count; i++)
        printf("%f\n",twentyMMNumbers[i]);  
}

void insertionSort(double numbers[], int array_size)
{
  int i, j, index;
  for (i=1; i < array_size; i++)
  {
    index = numbers[i];
    j = i;
    while ((j > 0) && (numbers[j-1] > index))
    {
      numbers[j] = numbers[j-1];
      j = j - 1;
    }
    numbers[j] = index;
  }
}

Код работал нормально, когда в нем было только 20 000 записей, но теперь выдает:

Segmentation fault: 11

Это было вызвано моим увеличением размера массива? PS Если у вас есть какие-либо советы по оптимизации, не стесняйтесь указывать на это.

Answer 1

Как ни странно (учитывая это имя сайта), у вас переполнение стека.Вам нужно будет динамически распределять столько памяти в куче.

Для большей ясности эта строка:

double twentyMMNumbers[20000000];

должна быть

double* twentyMMNumbers = (double*)malloc(20000000*sizeof(double));

ИКонечно, вам необходимо освободить эту память перед выходом из программы (в качестве рекомендации):

free(twentyMMNumbers);

Answer 2

Он работает с меньшим размером массива, так что вот некоторые комментарии (так как это было в CodeReview) и некоторые исправления для больших размеров массива.

1, если вы хотите использовать массивы фиксированного размера, используйте константу вместо200000 (или 20000000) литералы.

2, Использование динамических массивов лучше.Выделите память после того, как вы прочитали первую строку и используйте прочитанный размер в качестве размера нового массива.Кроме того, я бы сохранял размер файла данных (первая строка файла) в отдельной переменной, а не в массиве.

int dataSize;
inputFile >> dataSize;
double *twentyMMNumbers = new double[dataSize];

Он выделяет точный объем памяти.Не больше, не меньше.

Также исправляет ошибку Ошибка сегментации .Для получения дополнительной информации проверьте этот вопрос: Ошибка сегментации на больших размерах массива

(Не забудьте выделить массив с помощью delete[].)

3, это не нужночитать весь файл, если у вас больше записей, чем размер массива.Я бы изменил цикл while:

while (inputFile) {   
    if (count >= dataSize) {

        break;
    }
    inputFile >> twentyMMNumbers[count];
    count++;
}
inputFile.close();  

Может быть, exit(-1) и сообщение об ошибке было бы лучше вместо break.

4, следующий комментарий не является обязательным:

//While loop

5, Вы должны передать реальный размер массива в функцию insertionSort, поэтому напишите это:

insertionSort(twentyMMNumbers, dataSize); 

Комментарий здесь также не нужен.

6, Улучшение обработки ошибок: что произойдет, если значение dataSize больше, чем число чисел в файле?

7, я бы извлек функцию printArray с последним for, а также функция readInput.

8, рассмотрите возможность использования печати в стиле C ++ вместо printf s:

cout << "Hello world!" << endl;

(требуется #include <iostream>.)

Answer 3

У вас проблема в цикле while:

while(inputFile)
{   //While loop
    count++;
    if(count < 20000000)
        inputFile >> twentyMMNumbers[count];
}

Этот цикл будет прерван, только если файл содержит <= 20000000 чисел. Если count становится 20000000, он больше не будет пытаться читать из <code>inputFile, но все равно будет использовать inputFile в качестве условия для продолжения цикла. И затем, когда число достигает максимального значения int, оно оборачивается и вы индексируете twentyMMNumbers с отрицательным числом. Это вполне может быть причиной того, что вы получите ошибку сегментации.

20000000 - это «магическое число» в вашем коде. Вместо того, чтобы писать везде, сделайте const int NumElements = 20000000 в начале вашего файла.