2

我试图在 C 中实现外部排序。

我最初必须从文件中读取 N 个整数（取决于主内存），以便我可以对它们应用快速排序，然后继续合并过程。

我可以想到这两种方式：

  1. 从文件中一个一个地读取 N 个整数并将它们放入一个数组中，然后对它们进行排序。
  2. 将大量数据读入一个大字符数组，然后使用 sscanf 从中读取整数。

第一种方法显然很慢，第二种方法使用大量额外内存（但我们的主内存有限）

有没有更好的办法？

4

4 回答 4

3

不要试图比你的操作系统更聪明，它可能支持一些聪明的内存管理功能，这会让你的生活更轻松，你的代码更快。

假设您使用的是符合 POSIX 的操作系统，那么您可以使用mmap(2)。

  1. 使用 mmap 将文件映射到内存中
  2. 解决
  3. 同步它

这样，操作系统将在空间紧张时处理交换数据，并在您需要时交换数据。

于 2013-03-25T11:01:46.150 回答
1

由于stdio文件操作是缓冲的，因此您不必担心第一个选项，尤其是在文件不大的情况下。请记住，您不是直接对文件进行操作，而是对该文件在内存中的表示。

例如，如果您一次扫描一个数字，系统将从文件中读取更大的部分（在我的系统上它是 4096 字节，或者如果文件更短，则读取整个文件）。

于 2013-03-25T11:01:20.737 回答
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 回答
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 回答