2
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ How are you going to check which code is the fastest? \$\endgroup\$ – ProgramFOX Mar 7 '14 at 15:26
  • \$\begingroup\$ How should my program know how long the key is? \$\endgroup\$ – Peter Taylor Mar 7 '14 at 15:35
  • \$\begingroup\$ @PeterTaylor using ENV var or cli arguments are perfectly valid solutions. Edited the example to reflect that. \$\endgroup\$ – Steve Schnepp Mar 7 '14 at 15:42
  • \$\begingroup\$ @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. \$\endgroup\$ – Steve Schnepp Mar 7 '14 at 15:45
  • 2
    \$\begingroup\$ Winner per language is a good idea, except that this site only allows one winner. \$\endgroup\$ – Hosch250 Mar 7 '14 at 18:18
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
\$\endgroup\$
  • 1
    \$\begingroup\$ Can this program process a 15Gib dataset + 4 * 10Mib like specified by the OP on a machine with less RAM? \$\endgroup\$ – rubik Mar 9 '14 at 8:20
  • \$\begingroup\$ 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. \$\endgroup\$ – skibrianski Mar 9 '14 at 15:48
  • \$\begingroup\$ @rubik thx, I didn't say that the machine had less RAM, but I used a 15GiB file to make it obvious :) \$\endgroup\$ – Steve Schnepp Mar 10 '14 at 15:43
  • \$\begingroup\$ 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. \$\endgroup\$ – skibrianski Mar 11 '14 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.