複数のソート済みファイルを 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 秒未満に減らしたいと思います。それをどのように行うことができるかについてのアイデアはありますか？
次の Perl スクリプトを使用して、それぞれ 300,000 行のファイルを 10 個作成しました。各行には 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;
}
Perl 5.18.0 では、10 個のファイルを生成するのに約 1.5 秒かかりました (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
$
これらの結果の解釈:
lsリストには、10 個のデータ ファイルが表示されます。forループは、入力ファイルが個別にソートされていることを確認します。merge私が書いたプログラムは約 0.5 秒で実行されます。sortマージ モード ( )のシステムは-m、約 10 秒で実行されます (最適化されていないコードがそれを非常に迅速に処理するのに、これほど時間がかかることに驚いています)。lsリストは、出力ファイルが同じサイズであることを示しています。cmpコマンドは、出力ファイルが同一であることを示しています。sort -cコマンドは、出力ファイルがソートされていることを示しています。私は別々に、その後、それぞれ 12 バイトの 1,000,000 レコードを含む 101 個のファイルを 52 秒で作成しました。ファイルを 20 秒でマージしました (約 1179 MiB の出力ファイルを生成しました — 1,236,000,000 バイト)。システムsortはそれらを 467 (7 分 47 秒) 秒 (別名「永遠」) でマージしました。sort -c出力ファイルがソートされていることを確認するのに約 90 秒かかりました。cmp2 つの大きなファイルを比較するのに 2 秒もかかりませんでした。
sortシステムのマージが非常に遅いことに興味があります。
sortは約 10 秒でジョブを実行できます。#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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 の長さの行を処理するように設計されています。getline()さらに長い行を処理するために POSIX を使用するように修正することは難しくありません 。これは、すべてのファイルを一度に開くことができることを前提としています (つまり、ほとんどのマシンで、制限を微調整することなく、約 250 個の入力ファイルの上限を意味します)。中間ファイルへの複数のマージを行うのではなく、すべてのファイルを開くことができない場合は停止します。