0

我正在尝试对一个数组进行排序，该数组的元素是从一个大小约为 5 GB 且包含大约 500000 个数据元素的文件中读取的。

在数据大小为 300.000.000 之后，由于分段错误，程序在排序过程中出错并终止。

我认为问题的发生是由于分配给程序的内存空间不足。如何在我的 C 代码中更改它？

你能帮我解决这个问题吗？谢谢你。

int arraysize = atoi(argv[1]);
int* array    = malloc(sizeof(int)*arraysize);
int* temp     = malloc(sizeof(int)*arraysize);
int i;

FILE *fi;
char buffer[20];
fi = fopen("DATASET.dat", "r");

for(i=0; i<arraysize; i++){
  fgets(buffer, 20, fi);
  array[i] = atoi(buffer);
}

fclose(fi);

//function is called to perform the sorting
mergesort_array(array, arraysize, temp);
4

3 回答 3

1

int* 数组 = malloc(sizeof(int) arraysize); int temp = malloc(sizeof(int)*arraysize);

通常，每当您分配内存时，请检查分配是否成功：

int *array = NULL, *temp = NULL;

if (NULL == (array = malloc(sizeof(int)*arraysize)))
{
    fprintf(stderr, "Out of memory allocating %d bytes\n", sizeof(int)*arraysize);
    abort();
}
if (NULL == (temp = malloc(sizeof(int)*arraysize)))
{
    fprintf(stderr, "Out of memory allocating %d bytes\n", sizeof(int)*arraysize);
    abort();
}

然后，一种可能性是在磁盘上实现合并排序，使用整数文件（您也可以 mmap() 文件）。

但我觉得奇怪的是，在堆上分配 300000 个整数 - 最多 4.8 兆字节，使用 64 位整数 - 会导致分配错误，所以我认为这是合并排序实现中的问题；也许与递归实现有关。

我会先用完整的调试信息编译程序，然后用gdb.

一个“简单”的 malloc 问题

必须处理表示数字的非常大的 ASCII 字符串数组，您可以首先将其转换为整数文件。

FILE *fi, *fo, *ft;
char buffer[20];
int  array[4096], b = 0;

fi = fopen("DATASET.dat", "r");
if (NULL == fi)
{
    fprintf(stderr, "Cannot open input file\n");
    abort();
}
fo = fopen("INTEGER.dat", "w");
if (NULL == fo)
{
    fprintf(stderr, "Cannot open output file\n");
    abort();
}
ft = fopen("TEMP.dat", "w");
if (NULL == ft)
{
    fprintf(stderr, "Cannot open output file\n");
    abort();
}
for(i=0; i<arraysize; i++){
   fgets(buffer, 20, fi);
   array[b++] = atoi(buffer);
   if (4096 == b)
   {
       if (b != fwrite(buffer, sizeof(int), b, fo))
       {
           fprintf(stderr, "write error\n");
           abort();
       }
       if (b != fwrite(buffer, sizeof(int), b, ft))
       {
           fprintf(stderr, "write error\n");
           abort();
       }
       b = 0;
   }
}
if (b)
{
    if (b != fwrite(buffer, sizeof(int), b, fo))
    {
        fprintf(stderr, "write error\n");
        abort();
    }
    if (b != fwrite(buffer, sizeof(int), b, ft))
    {
        fprintf(stderr, "write error\n");
        abort();
    }
}
fclose(fi); fi = NULL;
fclose(fo); fo = NULL;
fclose(ft); ft = NULL;

现在你有一个INTEGER.dat由固定大小的整数组成的文件。就所有意图和目的而言，它是内存中数组的文件副本。临时数组也是如此。

您可以告诉系统将该文件视为内存中的一个数组。

int *sort = NULL;
int *temp = NULL;

// Temp is not shown -- identical treatment as sort

fd = open ("INTEGERS.dat", O_RDWR);
if (fd == -1)
{
    fprintf(stderr, "cannot reopen output\n");
    abort();
}
if (MAP_FAILED == (sort = mmap (0, arraysize*sizeof(int), PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)))
{
    fprintf(stderr, "mmap error\n");
    abort();
}
if (-1 == close (fd))
{
    fprintf(stderr, "error closing output file\n");
    return 1;
}

do_sort(sort, temp, arraysize);

if (-1 == munmap (sort, arraysize*sizeof(int)))
{
    fprintf(stderr, "error releasing mmap for %s\n", "sort");
    abort();
}
于 2012-12-01T22:42:55.587 回答
1

Sounds like you are using 32 bit operating system version, or at least 32 bit compiler, resulting ib 32 bit pointers, and max 4 gigs of memory (or even less, depending on OS). Switch to 64 bit OS and compile with 64 bit compiler.

Problem with 32 bit OS is, it simply cannot address enough memory for your "naive" algorithm, which requires all data to be in one flat memory space. Using mmap would not help either, for same reason. If you have to stick with 32 bit mode, you have to merge sort in parts, using files.

于 2012-12-01T23:33:50.227 回答
0

首先，如果您的数据集这么大，我会使用数据库。然后，您可以免费获得它以及访问/插入/更新/删除数据的简单方法。

但是，要回答您的问题并且您在分配内存时遇到问题，请尝试改用内存映射文件。如果在 Linux 或 UNIX 上，请参阅mmap 。

于 2012-12-01T22:32:23.910 回答