0
我尝试使用辅助存储实现基于磁盘的合并分类。实现如下所示。检查辅助存储的基于磁盘的合并分类的性能
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）中运行。
我通常使用迭代自下而上的合并排序，而不是像在这里完成的自上而下递归排序。如果在块足够小时使用'std :: sort'，则可以获得更高的效率，而不是调用'merge_sort'直至块大小为1. –
感谢您的评论。当我尝试进行优化和重构时，我会考虑它们。 – chatterboy