我必须将多个已排序的文件合并为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秒以下。 关于如何做到的任何想法?
你不应该从文件中读取12个字节。 从每个文件中读取4k左右的缓冲区,并在必要时使用缓冲区进行排序,刷新缓冲区。 也以4k左右的块来写输出
如果文件大小足够小,则将整个文件加载到内存中,排序,然后写入输出。
数据生成
我使用这个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-%.3dn", $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 $
解释这些结果:
我分别创建了101个文件,每个文件在52秒内有1,000,000条记录,每条12字节。 我在20秒内合并了文件(生成大约1179 MiB的输出文件 – 1,236,000,000字节)。 系统sort
在467(7m47s)秒(也称为“永远”)中合并它们。 sort -c
花了大约90秒来检查输出文件是按排序顺序排列的。 比较两个大文件花了不到2秒的cmp
。
我很感兴趣,合并时系统sort
太慢了。
解释结果
码
#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 - %sn", 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: %sn", inputs[1].line); printf("2: %sn", 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: %dn", r12); printf("2 vs 1: %dn", r21); printf("1 vs 1: %dn", 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个输入文件的上限没有调整限制)。 如果它无法打开所有文件而不是多次合并到中间文件,它将停止。
以上就是c/c++开发分享将排序的多个文件合并为1个已排序的文件相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/560537.html