使用辅助存储检查基于磁盘的合并排序的性能

Question

我尝试用辅助存储实现基于磁盘的归并排序。实现如下。

fd - 数据集的文件描述符将被排序

fd2 - 辅助存储的文件描述符

#define LENGTH 100
#define SEARCH_BEGIN 4
int merge_sort_d(int fd, int fd2, int s, int e) {
    int i, m;
    int l, r;
    char lv[LENGTH], rv[LENGTH];
    char buf[LENGTH];
    if (s >= e) return 1;
    m = (s + e) / 2;
    merge_sort_d(fd, fd2, s, m);
    merge_sort_d(fd, fd2, m+1, e);
    l = s;
    r = m+1;
    memset(lv, 0, LENGTH);
    memset(rv, 0, LENGTH);
    lseek(fd2, 0, SEEK_SET);
    while (l <= m && r <= e) {
        lseek(fd, 1LL*SEARCH_BEGIN + 1LL*l*LENGTH, SEEK_SET);
        read(fd, (void *)lv, LENGTH);
        lseek(fd, 1LL*SEARCH_BEGIN + 1LL*r*LENGTH, SEEK_SET);
        read(fd, (void *)rv, LENGTH);
        if (strncmp(lv, rv, LENGTH) < 0) {
            write(fd2, (void *)lv, LENGTH);
            ++l;
        } else {
            write(fd2, (void *)rv, LENGTH);
            ++r;
        }
    }
    for (; l <= m; ++l) {
        lseek(fd, 1LL*SEARCH_BEGIN + 1LL*l*LENGTH, SEEK_SET);
        read(fd, (void *)lv, LENGTH);
        write(fd2, (void *)lv, LENGTH);
    }
    for (; r <= e; ++r) {
        lseek(fd, 1LL*SEARCH_BEGIN + 1LL*r*LENGTH, SEEK_SET);
        read(fd, (void *)rv, LENGTH);
        write(fd2, (void *)rv, LENGTH);
    }
    lseek(fd, 1LL*SEARCH_BEGIN + 1LL*s*LENGTH, SEEK_SET);
    lseek(fd2, 0, SEEK_SET);
    memset(buf, 0, LENGTH);
    for (i=s; i<=e; ++i) {
        read(fd2, (void *)buf, LENGTH);
        write(fd, (void *)buf, LENGTH);
    }
    return 1;
}

在实现基于磁盘的归并排序后，我测试了一些小案例来检查它是否正确运行。它在小情况下看起来足够快，但是当运行它具有超过 20G 的大数据集时（后来最终大小超过 500G）。它需要 2 个小时，我混淆它真的在 O(nlogn) 中运行。当然还有一些基于磁盘的算法和数据结构的额外时间。

我很好奇它是否真的在 O(nlogn) 中运行。

Answer 1

该算法的复杂度为 O(N logN)，但性能不仅仅是要排序的记录数。

不断搜索和文件访问非常慢。您应该在一个块中读取多条记录，因为读取 16 条记录（或 200 条）的时间与读取一条记录的时间差别不大。

在您的主 for 循环中，您正在读取已有的数据。仅读取新记录（对应于 l 或 r 中的哪一个被更改）会有很大帮助，尽管上面提到的多记录读取会好得多。

你最后一个循环，如果你使用大块（许多记录）而不是一次复制一个，那么你将数据从 fd2 复制到 fd 会快得多。这同样适用于中间的两个循环，您可以在其中复制其中一侧的剩余部分，并且 r 循环是多余的，因为您会立即在最后一个循环中复制相同的数据。

有关对磁盘上的大文件进行排序的所有详细信息，请参阅 Knuth 的 计算机编程艺术 的第 5 章（第 3 卷）。（第二版5.4节讲的是外部排序。）

Answer 2

标准的内存合并排序确实 log(n) 遍历数据，每次遍历都合并连续的较大列表。在第一遍中，您合并每个包含一个项目的列表。接下来，它的列表每个包含两个项目，然后是四个，等等。使用这种方法，您可以让 log(n) 遍历数据，并在每次遍历期间查看 n 个项目。因此 O(n log n) 复杂度。

该方法对于内存中排序非常有效，因为访问一个项目的成本不是很高。但是，对于基于磁盘的排序，它变得非常昂贵，因为访问每个项目的成本非常高。基本上，您正在读取和写入整个文件 log(n) 次。如果您有 20 GB 的 100 字节记录，则表示文件遍历了 25 次或更多次。所以你的排序时间会以文件读写25次的时间为主。

外部排序是一种非常不同的动物。这个想法是尽可能减少磁盘I/O。你分两次完成。在第一遍中，您将尽可能多的数据读入内存并使用快速排序、合并排序或其他内存中排序算法对其进行排序，然后将该块写入磁盘。然后将文件的下一个块读入内存，对其进行排序，然后写入磁盘。

完成第一遍后，磁盘上就会有一些排序好的块。如果您有一个 20 GB 的文件，并且您的计算机上有 4 GB 的可用内存，那么您将有五个块，每个块的大小约为 4 GB。（请注意，您实际上可能有五个略小于 4 GB 的块，以及第六个非常小的块）。调用chunk数量k.

请注意，在第一遍完成后，您已经读取和写入了每条记录一次。

在第二遍中，您合并了多个块。这是通过一堆 k 项完成的。这个想法是你用每个块中的第一个项目初始化堆。您 select 那些 k 项目中最小的（位于堆的顶部），并将其写入输出文件。然后，您从包含您刚刚删除的项目的块中取出下一个项目，并将其添加到堆中。重复此过程，直到清空所有块。

第一遍是 O(n log n)。实际上，它是 k*((n/k) log(n/k))，计算结果为 n log n。第二遍是 O(n log k).

这里的重要部分是，在第二遍中，您再次阅读并写入每一项。您已将磁盘 I/O 从读取和写入每个项目 log(n) 次减少到读取和写入每个项目两次。这将运行 比您编写的代码快 很多。

同样重要的是要注意这两种算法确实被认为是 O(n log n)。 I/O 常数是杀手。第二种算法实际上进行了更多的计算，但它节省了如此多的磁盘 I/O 时间，以至于它比理论上更快的算法更快。

External sorting article on Wikipedia gives a decent explanation, and the GeeksforGeeks article 给出了一个 C++ 的工作示例。

使用辅助存储检查基于磁盘的合并排序的性能

Checking the performance for disk-based merge sort with auxiliary storage

c++

sorting

algorithm

file-descriptor