# Merging text files based on a prefix key

Imagine an ordered file set : file1, file2, ... fileN.

Each file is a textual file that is made of lines that have the same format : A concatenation of a fixed-size key (the same among all the file set) and a variable length value.

The merging algorithm is very similar to UPSERT :

• To merge 2 files:
• Iterate on all lines of the first file.
• If the key of the current line is not in the second file, emit the current line.
• If the key of the current line is in the second file, emit only the line of the second file
• For each line of the second file that has a key not present in the first file emit the line of the second file.
• If more than 2 files are to be merged, each file is merged to the result of the previous merge. The result of merge(file1, file2, file3, file4) is defined as the result of merge(merge(merge(file1, file2), file3), file4).

As an example, we take the length of the key of 4 :

$cat file1 0010THIS_IS_LINE_1_FROM_FILE1 0011THIS_IS_LINE_2_FROM_FILE1 00A0THIS_IS_LINE_3_FROM_FILE1$ cat file2
0010THIS_IS_LINE_1_FROM_FILE2
0100THIS_IS_LINE_2_FROM_FILE2
$cat file3 0100EMPTY_LINE 0011EMPTY_LINE  Will result in : $ merge --key-size=4 file1 file2 file3
0010THIS_IS_LINE_1_FROM_FILE2
0011EMPTY_LINE
00A0THIS_IS_LINE_3_FROM_FILE1
0100EMPTY_LINE


Several precisions :

• Textual data is made of printable ASCII7 chars plus tabs and spaces.
• Preserving order is nice, but not required
• Uniqueness of key is obviously required
• Multicore-aware algorithms are allowed.
• The first file is usually bigger than the others.
• How are you going to check which code is the fastest? Mar 7 '14 at 15:26
• How should my program know how long the key is? Mar 7 '14 at 15:35
• @PeterTaylor using ENV var or cli arguments are perfectly valid solutions. Edited the example to reflect that. Mar 7 '14 at 15:42
• @ProgramFOX i'll be using time on a 15GiB + 4x10MiB dataset on a 4-way i5. I'm adding the fact that the 1rst file is usually bigger than the others. Mar 7 '14 at 15:45
• Winner per language is a good idea, except that this site only allows one winner.
– user10766
Mar 7 '14 at 18:18

# perl, memory-constrained:

Since rubik mentioned it, here's code for when you haven't the memory to keep all of your keys in memory. Basically we just use the filesystem as a dumb key/value store (you could easily use eg DBM or what have you instead).

#!/usr/bin/perl -w

use strict;
use warnings;

use File::Spec ();
use File::Path qw(make_path remove_tree);
use File::Glob ':globally';
use Path::Iterator::Rule;

my $key_size =$ARGV[0] =~ /--key-size=(\d+)/ ?
(shift @ARGV, $1) : 4; my$BASE = File::Spec->catfile( File::Spec->tmpdir(), "merger" );

sub pathify {
my ($key,$mkdirs) = @_;
my @path = ($BASE, split //,$key);
my $dirpart = File::Spec->catdir( @path ); make_path($dirpart )  if  $mkdirs; return File::Spec->catfile($dirpart, $key ); } sub set { my ($key, $value) = @_; open my$fh, '>', pathify($key, 1) || die "open(w)$key failed: $!"; print {$fh } $value; close$fh;
}

sub get {
my ($key) = @_; open my$fh, '<', pathify($key) || die "open(r)$key failed: $!"; chomp(my$x = <$fh>); close$fh;
return $x; } remove_tree($BASE );

my %keys;
while(@ARGV) {
my $fn = shift; open my$fh, "<", $fn || die "can't open$fn for reading: $!"; while(<$fh>) {
chomp;
set( substr($_, 0,$key_size), substr($_,$key_size) );
}
close $fh || die "can't close$fn: $!"; } my$next = Path::Iterator::Rule->new->file->iter( $BASE ); while( defined($_ = $next->() ) ) { (undef,undef,$_) = File::Spec->splitpath( $_ ); print$_.get($_)."\n"; } remove_tree($BASE );


I felt bad about using a non-core module, Path::Iterator::Rule, but it wasn't worth reinventing the wheel just to avoid the dependency - it's a great module.

You could adapt this to preserve order by changing what is stored in the file from just the $value to include the$order and $value as well. This is trivial because we only ever add keys to the end of the list. # perl I'm sure this can be done a few percent faster in some other language, but perl makes this super quick to implement at the optimal big-O level, and likely performs well enough. This code preserves order. #!/usr/bin/perl -w use strict; use warnings; my$key_size = $ARGV[0] =~ /--key-size=(\d+)/ ? (shift @ARGV,$1) : 4;

sub slurp {
my $fn = shift; open my$fh, "<", $fn || die "can't open$fn for reading: $!"; my (%keys, @order); while(<$fh>) {
chomp;
my $key = substr$_, 0, $key_size; push @order,$key;
$keys{$key} = substr $_,$key_size;
}
close $fh || die "can't close$fn: $!"; return [ \@order, \%keys ]; }$_ = slurp shift @ARGV;
my @order = @{ $_->[0] }; my %keys = %{$_->[1] };
while(@ARGV) {
my ($order2,$keys2) = @{slurp shift @ARGV};
$keys{$_} = delete $keys2->{$_}  for (grep { exists $keys2->{$_} } @order);
for (grep { exists $keys2->{$_} } @{$order2}) {$keys{$_} =$keys2->{$_}; push @order,$_;
}
}

print "$_$keys{$_}\n" for @order;  Test output: ski@anito$ perl merger.pl --key-size=4 file1 file2  file3
0010THIS_IS_LINE_1_FROM_FILE2
0011EMPTY_LINE
00A0THIS_IS_LINE_3_FROM_FILE1
0100EMPTY_LINE


And here's a slightly faster version that doesn't preserve order:

#!/usr/bin/perl -w

use strict;
use warnings;

my $key_size =$ARGV[0] =~ /--key-size=(\d+)/ ?
(shift @ARGV, $1) : 4; my %keys; while(@ARGV) { my$fn = shift;
open my $fh, "<",$fn || die "can't open $fn for reading:$!";
while(<$fh>) { chomp;$keys{substr $_, 0,$key_size} = substr $_,$key_size;
}
close $fh || die "can't close$fn: $!"; } print "$_$keys{$_}\n"  for  keys %keys;

• Can this program process a 15Gib dataset + 4 * 10Mib like specified by the OP on a machine with less RAM? Mar 9 '14 at 8:20
• Hmm, I missed that bit. It probably wouldn't work as written above if you have less than ~15GiB ram. The easiest fix would probably be to tie() the hash to a DBM file. Mar 9 '14 at 15:48
• @rubik thx, I didn't say that the machine had less RAM, but I used a 15GiB file to make it obvious :) Mar 10 '14 at 15:43
• Yeah, I didn't see the 15GiB bit at first. Who has time to read comments? ;-) BTW, I have 16GiB of memory on my server downstairs, so it's not entirely a given that the data set can't fit in memory. My other entry keeps the data on disk instead of in memory. Mar 11 '14 at 12:19