2

Cで外部ソーティングを実装しようとしています。

最初にファイルからN個の整数（メインメモリに応じて固定）を読み取って、クイックソートを適用してからマージプロセスを続行できるようにする必要があります。

私はこれらの2つの方法を考えることができます：

  1. ファイルからN個の整数を1つずつ読み取り、配列に入れてから並べ替えます。
  2. 大量のデータを大きなchar配列に読み取り、sscanfを使用してそこから整数を読み取ります。

1番目の方法は明らかに遅く、2番目の方法は多くの余分なメモリを使用しています（ただし、メインメモリは限られています）

より良い方法はありますか？

4

4 に答える 4

3

OSよりも賢くしようとしないでください。おそらく、いくつかの賢いメモリ管理機能をサポートしているので、作業が楽になり、コードが速くなります。

POSIX準拠のオペレーティングシステムを使用していると仮定すると、mmap（2）を使用できます。

  1. mmapを使用してファイルをメモリにマップします
  2. 並べ替える
  3. 同期する

このように、OSは、スペースが狭いときにデータのスワップアウトを処理し、必要なときにデータをスワップインします。

于 2013-03-25T11:01:46.150 に答える
1

以下の関数を使用して、ファイルからintを1つずつ読み取り、外出先で並べ替えとマージを続行できます。

この関数は、ファイル名と整数のカウントを引数として取り、ファイルからintを返します。

int read_int (const char *file_name, int count)
{
  int err = -1;
  int num = 0;

  int fd = open(filename, O_RDONLY);
  if(fd < 0)
  {
    printf("error opening file\n");
    return (fd);
  }

  err = pread(fd, &num, sizeof(int), count*sizeof(int));
  if(err < 0)
  {
    printf("End of file reached\n");
    return (err);
  }

  close(fd);
  return (num);  
}
于 2013-03-25T10:27:43.327 に答える
1

ファイル操作はバッファリングされるためstdio、特にファイルが大きくない場合は、最初のオプションについて心配する必要はありません。ファイルを直接操作しているのではなく、メモリ内のそのファイルを表現していることを忘れないでください。

たとえば、一度に1つの数値をスキャンすると、システムはファイルからはるかに大きなセクションを読み取ります（私のシステムでは、4096バイト、または短い場合はファイル全体）。

于 2013-03-25T11:01:20.737 に答える
0

読むと同時に並べ替えるのが最善の方法です。配列ではなくリンクリストにデータを保存すると、並べ替えがより効率的になります

fscanf()ファイルから整数ごとに読み取るために使用できます。ファイルから整数を読み取った時点でソートしてみてください。つまり、ファイルから整数を読み取るときは、読み取りが終了したときに配列を並べ替えるために、適切な場所の配列に整数を配置します。

次の例では、ファイルを整数ごとに読み取り、読み取りと同時に並べ替えて挿入します。整数はリンクリストではなく配列に保存されます

void sort_insert(int x, int *array, int len)
{
    int i=0, j;
    for(i=0; i<(len-1); i++)
    {
        if (x > array[i])
            continue;
        for (j=(len-1); j>i; j--)
            array[j] = array[j-1];
        break;
    }
    array[i] = x;
}

void main() {
    int x, i;
    int len = 0;
    int array[50];
    FILE *fp = fopen("myfile.txt", "r");

    while (len<50 && fscanf(fp, " %d",&x)>0)
    {
        len++;
        sort_insert(x, array, len);
    }
    for (i=0; i<len; i++)
    {
        printf("array[%d] = %d\n", i, array[i]);
    }

}
于 2013-03-25T10:05:41.240 に答える