0

サイズが約5GBで、約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 * array = 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

32ビットオペレーティングシステムバージョン、または少なくとも32ビットコンパイラを使用しているように聞こえます。その結果、ib 32ビットポインタと最大4ギガのメモリ(OSによってはそれ以下)が生成されます。64ビットOSに切り替えて、64ビットコンパイラでコンパイルします。

32ビットOSの問題は、すべてのデータが1つのフラットメモリスペースにある必要がある「ナイーブ」アルゴリズムに十分なメモリをアドレス指定できないことです。同じ理由で、mmapを使用しても役に立ちません。32ビットモードに固執する必要がある場合は、ファイルを使用して、部分的に並べ替えをマージする必要があります。

于 2012-12-01T23:33:50.227 に答える
0

まず、データセットがこれほど大きい場合はデータベースを使用します。その後、データにアクセス/挿入/更新/削除する簡単な方法とともに、これを無料で入手できます。

ただし、質問に答えるために、メモリの割り当てに問題がある場合は、代わりにメモリマップトファイルを使用してみてください。LinuxまたはUNIXの場合は、mmapを参照してください。

于 2012-12-01T22:32:23.910 に答える