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.
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, "&lt;", $fn || die "can't open $fn for reading: $!";
  my (%keys, @order);
  while(&lt;$fh&gt;) {
    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 = @{ $_-&gt;[0] };
my %keys  = %{ $_-&gt;[1] };
while(@ARGV) {
  my ($order2, $keys2) = @{slurp shift @ARGV};
  $keys{$_} = delete $keys2-&gt;{$_}  for (grep { exists $keys2-&gt;{$_} } @order);
  for (grep { exists $keys2-&gt;{$_} } @{$order2}) {
    $keys{$_} = $keys2-&gt;{$_};
    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, "&lt;", $fn || die "can't open $fn for reading: $!";
  while(&lt;$fh&gt;) {
    chomp;
    $keys{substr $_, 0, $key_size} = substr $_, $key_size;
  }
  close $fh || die "can't close $fn: $!";
}

print "$_$keys{$_}\n"  for  keys %keys;