C语言 20000000 个元素限制的数组

Question

对于一个大学项目，我必须使用 MergeSort 对包含 2000 万条记录的 CSV 文件进行排序(以 2^64 位表示，例如 10000000 或 7000000，所以我使用了unsigned long long(。所以，我开发了这个C文件：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Path to the dataset
#define DATASET_PATH "/Volumes/HDD/Lorenzo/Unito/2 Anno/ASD/Progetto/Progetto 2017-2018/laboratorio-algoritmi-2017-18/Datasets/ex1/integers.csv"
#define ELEMENTS_TO_SCAN 1000000 // the numbers of elements to be scanned
void mergeSort(unsigned long long * arrayToSort, int leftIndex, int rightIndex);
void merge(unsigned long long * arrayToSort, int left, int center, int right);
void read();
void printArray();
// from "Introduction to Algorithms" of T. H. Cormen
void mergeSort(unsigned long long * arrayToSort, int leftIndex, int rightIndex){
if(leftIndex < rightIndex){
int center = (leftIndex + rightIndex) / 2;
mergeSort(arrayToSort, leftIndex, center);
mergeSort(arrayToSort, center + 1, rightIndex);
merge(arrayToSort, leftIndex, center, rightIndex);
}
}
// from "Introduction to Algorithms" of T. H. Cormen
void merge(unsigned long long * arrayToSort, int left, int center, int right){
int n1 = center - left + 1;
int n2 = right - center; 
unsigned long long leftSubArray[n1+1];
unsigned long long rightSubArray[n2+1];
leftSubArray[n1] = ULLONG_MAX; // here Cormen use infinite
rightSubArray[n2] = ULLONG_MAX; // here Cormen use infinite
for(int i = 0; i < n1; i++)
leftSubArray[i] = arrayToSort[left + i];
for(int j = 0; j < n2; j++)
rightSubArray[j] = arrayToSort[center + j + 1];
int i = 0;
int j = 0;
int k = 0;
for(k = left; k <= right; k++){
if(leftSubArray[i] <= rightSubArray[j]){
arrayToSort[k] = leftSubArray[i];
i++;
} else {
arrayToSort[k] = rightSubArray[j];
j++;
}
}
}
// it reads all the dataset, and saves every line (wich contains a single element)
// in a position of an array to sort by MergeSort.
void read(char pathToDataset[], unsigned long long arrayToFill[]) {
FILE* dataset = fopen(pathToDataset, "r");
if(dataset == NULL ) { 
printf("Error while opening the file.n");
exit(0); // exit failure, it closes the program
}
int i = 0;
while (i < ELEMENTS_TO_SCAN && fscanf(dataset, "%llu", &arrayToFill[i])!=EOF) { 
//printf("%llun", arrayToFill[i]); // ONLY FOR DEBUG, it wil print 20ML of lines!
i++;
}
printf("nRead %d lines.n", i); 
fclose(dataset);
}
void printArray(unsigned long long * arrayToPrint, int arrayLength){
printf("[");
for(int i = 0; i < arrayLength; i++) {
if (i == arrayLength-1) {
printf("%llu]", arrayToPrint[i]);
}
else {
printf("%llu, ", arrayToPrint[i]);
}
}
}
int main() {
unsigned long long toSort [ELEMENTS_TO_SCAN] = {};
read(DATASET_PATH, toSort);
mergeSort(toSort,0,ELEMENTS_TO_SCAN-1);
printf("Merge finishedn");
return 0;
}

经过一番测试，如果ELEMENTS_TO_SCAN大于500000(= 2000万的1/4(，我不知道为什么，但是终端上的输出是

Segmentation fault: 11

有人可以帮助我吗？

Answer 1

您正在执行局部变量声明(例如在堆栈上(。如果您正在处理较大的数组，请考虑将它们设为全局，或使用动态数组 — 一般来说，动态会更好。使用全局变量更容易养成坏习惯。

为什么全局变量在单线程、非操作系统、嵌入式应用程序中是不好的

分段错误 11，因为 C 中的 40 MB 数组

Answer 2

正如人们指出的那样，这种类型的分配不能在 Stack 上完成。我会尝试动态分配它，为此您只需要像这样更改代码：

int main() {
unsigned long long *toSort;
toSort = (unsigned long long) malloc(ELEMENTS_TO_SCAN*sizeof(unsigned long long));
read(DATASET_PATH, toSort);
mergeSort(toSort,0,ELEMENTS_TO_SCAN-1);
printf("Merge finishedn");
free(toSort);
return 0;
}

正如您所指出的，合并是导致问题的合并。请注意，如果您使用以下内容：

int array[n];

你最终会遇到问题，这是给定的。如果您不知道在编译时将使用多少内存，请使用支持像链表一样调整大小的数据结构或动态分配它。