这个问题在这里已有答案:
对于大学项目,我必须使用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("%llu\n", 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 finished\n");
return 0;
}
经过一些测试,如果ELEMENTS_TO_SCAN大于500000(= 2000万的1/4),我不知道为什么,但终端上的输出是
Segmentation fault: 11
有人可以帮帮我吗?
你正在做一个局部变量声明(例如在堆栈上)。如果你正在处理更大的数组,考虑使它们全局化,或者使用动态数组 - 通常动态会更好。使用全局变量可以更容易地养成坏习惯。
Why are global variables bad, in a single threaded, non-os, embedded application
正如人们所指出的那样,这种类型的分配不能在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 finished\n");
free(toSort);
return 0;
}
正如你所指出的,合并是导致问题的那个。请注意,如果您使用以下内容:
int array[n];
你最终会遇到问题,这是给定的。如果您不知道在编译时将使用多少内存,请使用支持调整大小的数据结构(如链接列表)或动态分配它。