将排序的多个文件合并为1个已排序的文件

我必须将多个已排序的文件合并为1个已排序的文件。 目前我正在读取每个文件的一个数据条目（12个字节），将最大值写入输出文件并递增我从中复制数据的输入文件的指针，就像合并排序的合并步骤一样。

即

while (n){ //read one data element (12 bytes) //find maximum //write the maximum //increment file pointer containing of file containng maximum } 

该过程重复n =约3000000次。 问题是需要花费大量时间（约30秒）。 我想将拍摄时间减少到10秒以下。 关于如何做到的任何想法？

Answer 1

你不应该从文件中读取12个字节。 从每个文件中读取4k左右的缓冲区，并在必要时使用缓冲区进行排序，刷新缓冲区。 也以4k左右的块来写输出

如果文件大小足够小，则将整个文件加载到内存中，排序，然后写入输出。

Answer 2

数据生成

我使用这个Perl脚本创建了10个文件，每个文件包含300,000行，每行包含11个字符（主要是数字）和换行符：

 #!/usr/bin/env perl use strict; use warnings; # Generate sorted, merge-worthy data die "Usage: num-files lines-per-file" unless scalar(@ARGV) == 2; my $num_files = $ARGV[0]; my $num_lines = $ARGV[1]; die "Enter a number of files between 2 and 999" unless $num_files >= 2 && $num_files <= 999; die "Enter a number of lines between 2 and 9,999,999" unless $num_files >= 2 && $num_files <= 9_999_999; my $base = "datafile"; my $digits = length($num_files . ''); my $format = "$base.%.${digits}d"; foreach my $i (1..$num_files) { my $file = sprintf $format, $i; open my $fh, '>', $file or die "Failed to create $file"; foreach my $n (1..$num_lines) { printf $fh "%.7d-%.3d\n", $n + 60 * $i, $i; } close $fh; } 

生产10个文件需要大约1.5秒的Perl 5.18.0（在MacBook Pro，2.3 GHz Intel Core i7,16 GiB 1333 MHz RAM，良好的老式旋转磁盘;有用，但不是非常强大）。 设计数据时文件之间存在重叠，但每行都是唯一的，并标识它来自的文件（这是$offset的目的，并将序列号放在文件编号之前的文件中）。 在测试3个文件时，例如，在文件1和2中的数据交错存在之前，文件1中有一些数据，然后从所有3个文件中，然后文件1用完，文件2.它提供了不同的覆盖率。合并算法的一部分（但您可以创建更多场景）。

然后我创建了一个merge程序，如下面的“代码”部分所示。 没什么好看的。 它从Jon Bentley的“More Programming Pearls”中提取了一些堆管理算法; 原件被引用为评论。 唯一棘手的一点是比较例程的意义：这引起了我一些错误的答案，以及间接的水平。

时间安排结果

在代表~35 MiB数据的10个文件上运行时：

 $ ls -l datafile.?? -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.01 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.02 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.03 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.04 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.05 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.06 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.07 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.08 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.09 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 20:37 datafile.10 $ $ for file in datafile.??; do echo $file; sort -c $file; done datafile.01 datafile.02 datafile.03 datafile.04 datafile.05 datafile.06 datafile.07 datafile.08 datafile.09 datafile.10 $ time ./merge datafile.?? > datafile.out real 0m0.510s user 0m0.314s sys 0m0.074s $ time ./merge datafile.?? > datafile.out real 0m0.513s user 0m0.317s sys 0m0.080s $ time sort -m datafile.?? > datafile.merge real 0m10.061s user 0m9.960s sys 0m0.083s $ time sort -m datafile.?? > datafile.merge real 0m10.039s user 0m9.921s sys 0m0.082s $ ls -l datafile.* -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.01 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.02 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.03 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.04 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.05 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.06 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.07 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.08 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 14:09 datafile.09 -rw-r--r-- 1 jleffler staff 3600000 Sep 15 20:37 datafile.10 -rw-r--r-- 1 jleffler staff 36000000 Sep 15 20:42 datafile.merge -rw-r--r-- 1 jleffler staff 36000000 Sep 15 20:41 datafile.out $ cmp datafile.out datafile.merge $ sort -c datafile.out $ 

解释这些结果：

1. 第一个ls列表显示了10个数据文件。
2. for循环检查输入文件是按排序顺序单​​独进行的。
3. 我写的merge程序运行大约0.5秒。
4. 合并模式（ -m ）中的系统sort大约在10秒内运行（当我的非优化代码处理得太快时，我很惊讶它需要很长时间）。
5. 第二个ls列表显示输出文件大小相同。
6. cmp命令显示输出文件相同。
7. sort -c命令显示输出文件按排序顺序排列。

我分别创建了101个文件，每个文件在52秒内有1,000,000条记录，每条12字节。 我在20秒内合并了文件（生成大约1179 MiB的输出文件 – 1,236,000,000字节）。 系统sort在467（7m47s）秒（也称为“永远”）中合并它们。 sort -c花了大约90秒来检查输出文件是按排序顺序排列的。 比较两个大文件花了不到2秒的cmp 。

我很感兴趣，合并时系统sort太慢了。

解释结果

• 在我的Mac上，可以在大约半秒内合并来自10个输入文件的~35 MiB数据。
• 系统sort可以在大约十秒钟内完成工作。
• 通过推断（假设我的机器不再是火箭，如果有的话），应该可以在不到20秒的时间内在Windows机器上合并~35 MiB（让你在性能上有40倍的差异，我不赞成我认为你应该需要）。
• 所以，你的代码需要30秒才需要太长时间 – 问题是’为什么’。 你应该仔细研究你的算法和数据结构。

码

 #include  #include  #include  #include  #include  typedef struct File { const char *file; FILE *fp; char *line; size_t reserve; /* Space allocated for line */ size_t length; /* Space used by current line */ } File; extern void err_exit(const char *fmt, ...); extern void read_line(File *current); extern void write_line(File *current); extern void heapify(size_t *heap, size_t heap_size, File *inputs); extern void siftup(size_t *heap, size_t lo, size_t hi, File *inputs); extern void siftdown(size_t *heap, size_t lo, size_t hi, File *inputs); extern int compare(File *inputs, size_t i1, size_t i2); const char *arg0; int main(int argc, char **argv) { File inputs[argc]; arg0 = argv[0]; /* Open files for reading - load first lines */ for (int i = 1; i < argc; i++) { File *current = &inputs[i]; current->file = argv[i]; if ((current->fp = fopen(current->file, "r")) == 0) err_exit("failed to open file %s for reading", current->file); current->reserve = 128; if ((current->line = malloc(current->reserve)) == 0) err_exit("failed to allocate %zu bytes memory", current->reserve); current->length = 0; read_line(current); } #if defined(CHECK_FUNDAMENTALS) for (int i = 1; i < argc; i++) printf("%d: %zu - %s\n", i, inputs[i].length, inputs[i].file); #endif size_t heap_size = argc - 1; size_t heap[argc]; // heap[0] unused for (int i = 1; i < argc; i++) heap[i] = i; #if defined(CHECK_FUNDAMENTALS) printf("Heap before:\n"); for (int i = 1; i < argc; i++) printf("%d: %zu - %s", i, heap[i], inputs[heap[i]].line); #endif heapify(heap, heap_size, inputs); #if defined(CHECK_FUNDAMENTALS) printf("Heap after:\n"); for (int i = 1; i < argc; i++) printf("%d: %zu - %s", i, heap[i], inputs[heap[i]].line); #endif #if defined(CHECK_FUNDAMENTALS) printf("Compare two lines:\n"); printf("1: %s\n", inputs[1].line); printf("2: %s\n", inputs[2].line); int r12 = compare(inputs, 1, 2); int r21 = compare(inputs, 2, 1); int r11 = compare(inputs, 1, 1); printf("1 vs 2: %d\n", r12); printf("2 vs 1: %d\n", r21); printf("1 vs 1: %d\n", r11); #endif while (heap_size > 0) { File *current = &inputs[heap[1]]; write_line(current); read_line(current); if (current->line == 0) heap[1] = heap[heap_size--]; if (heap_size > 0) { siftdown(heap, 1, heap_size, inputs); #if defined(CHECK_FUNDAMENTALS) printf("Heap check:\n"); for (int i = 1; i < argc; i++) printf("%d: %zu - %s", i, heap[i], inputs[heap[i]].line); #endif } } return 0; } int compare(File *inputs, size_t i1, size_t i2) { return strcmp(inputs[i1].line, inputs[i2].line); } void heapify(size_t *heap, size_t heap_size, File *inputs) { for (size_t i = 1; i <= heap_size; i++) siftup(heap, 1, i, inputs); } /* J Bentley: More Programming Pearls ** ** Heap in array x, indexed from 1, not 0 as is normal in C. ** Implementation will allocate but not use array[0]. ** ** function siftup(l, u, i, p) { ** # pre maxheap(l, u-1) ** # post maxheap(l, u) ** i = u ** while (1) { ** # maxheap(l, u) except between i and its parent ** if (i <= l) break ** p = int(i/2) ** if (x[p] >= x[i]) break ** swap(p, i) ** i = p ** } ** } ** ** function siftdown(l, u, i, c) { ** # pre maxheap(l+1, u) ** # post maxheap(l,u) ** i = l ** while (1) { ** # maxheap(l, u) except between i and its children ** c = 2*i ** if (c > u) break ** if (c + 1 <= u && x[c+1] > x[c]) c++ ** if (x[i] >= x[c]) break ** swap(c, i) ** i = c ** } ** } */ void siftup(size_t *heap, size_t lo, size_t hi, File *inputs) { size_t i = hi; while (1) { if (i <= lo) break; size_t p = i / 2; if (compare(inputs, heap[p], heap[i]) <= 0) break; size_t t = heap[p]; heap[p] = heap[i]; heap[i] = t; i = p; } } void siftdown(size_t *heap, size_t lo, size_t hi, File *inputs) { size_t i = lo; while (1) { size_t c = 2 * i; if (c > hi) break; if (c + 1 <= hi && compare(inputs, heap[c+1], heap[c]) < 0) c++; if (compare(inputs, heap[i], heap[c]) <= 0) break; size_t t = heap[c]; heap[c] = heap[i]; heap[i] = t; i = c; } } void read_line(File *current) { char buffer[4096]; if (fgets(buffer, sizeof(buffer), current->fp) != 0) { size_t length = strlen(buffer) + 1; if (length > current->reserve) { void *space = realloc(current->line, length); if (space == 0) err_exit("failed to reallocate %zu bytes memory", length); current->line = space; current->reserve = length; } strcpy(current->line, buffer); current->length = length - 1; } else { fclose(current->fp); current->fp = 0; free(current->line); current->line = 0; current->length = 0; current->reserve = 0; } } void write_line(File *current) { if (fwrite(current->line, sizeof(char), current->length, stdout) != current->length) err_exit("short write of line from %s of length %zu", current->file, current->length); } void err_exit(const char *fmt, ...) { int errnum = errno; va_list args; fprintf(stderr, "%s: ", arg0); va_start(args, fmt); vfprintf(stderr, fmt, args); va_end(args); if (errnum != 0) fprintf(stderr, " (%d: %s)", errnum, strerror(errnum)); putc('\n', stderr); exit(EXIT_FAILURE); } 

该代码旨在处理长达4 KiB的线路; 修改它以使用POSIX getline()来处理更长的行并不难。 它假设所有文件可以一次打开（这意味着大多数机器上的大约250个输入文件的上限没有调整限制）。 如果它无法打开所有文件而不是多次合并到中间文件，它将停止。