#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(:all :hireswallclock);
my @list1 = qw( 1 3 5 7 );
my @list2 = qw( 2 4 6 8 );
#my @list1 = (1 .. 100);
#my @list2 = (1 .. 100);
my $count = 10000;
my $routines = {
Baseline => sub { baseline(\@list1, \@list2) },
Integers => sub { solution_0(\@list1, \@list2) },
Queue => sub { solution_1(\@list1, \@list2) },
LR_1 => sub { LR_solution_1(\@list1, \@list2) },
LR_2 => sub { LR_solution_2(\@list1, \@list2) },
blokhead => sub { print_sums(\@list1, \@list2) },
};
my $buffer;
open OUT, '>', \$buffer or die "Can't open STDOUT: $!";
my $results = timethese($count, $routines);
cmpthese($results);
sub baseline {
# Simple solution
# O(N*M) memory, O(N*M) time
my @list1 = @{shift()};
my @list2 = @{shift()};
my @result = ();
for my $val1 (@list1) {
for my $val2 (@list2) {
push @result, $val1+$val2;
}
}
print OUT join "\n", (sort {$a <=> $b} @result);
}
sub solution_0 {
# Integer solution
# O(N+M) memory, O(N*M*len()) time
my @list1 = @{shift()};
my @list2 = @{shift()};
my $value = $list1[0]+$list2[0];
while ($value <= $list1[-1]+$list2[-1]) {
for my $scalar1 (@list1) {
for my $scalar2 (@list2) {
print OUT "$value\n" if $value == $scalar1 + $scalar2;
}
}
$value++;
}
}
sub solution_1 {
# queue solution
# O(2*N+M) memory, O(N^2*M) time
my ($list_ref1, $list_ref2) = @_;
my @list1;
my @list2;
if (@$list_ref1 <= @$list_ref2) {
@list1 = @$list_ref1;
@list2 = @$list_ref2;
} else {
@list1 = @$list_ref2;
@list2 = @$list_ref1;
}
my @queue = map $_+$list2[0], @list1;
push @queue, $list1[-1]+$list2[-1];
shift @list1;
for my $element1 (@list1) {
for (@list2) {
print OUT shift(@queue), "\n";
my $sum = $_+$element1;
my $count = 0;
$count++ until $sum <= $queue[$count];
splice @queue, $count, 0, $sum;
}
}
pop @queue;
print OUT join "\n", @queue;
}
sub LR_solution_1 {
#Limbic~Region's first posted solution
use constant VAL => 0;
use constant IDX => 1;
use constant SUM => 2;
my ($list_ref1, $list_ref2) = @_;
my @list1;
my @list2;
if (@$list_ref1 <= @$list_ref2) {
@list1 = @$list_ref1;
@list2 = @$list_ref2;
} else {
@list1 = @$list_ref2;
@list2 = @$list_ref1;
}
my @merge_list = map {[$_, 0, $_ + $list2[0]]} @list1; # Map over smaller list if known
while (@merge_list) {
my ($min, $index) = ($merge_list[0][SUM], 0);
for (1 .. $#merge_list) {
($min, $index) = ($merge_list[$_][SUM], $_) if $merge_list[$_][SUM] < $min;
}
print OUT "$min\n";
$merge_list[$index][IDX]++;
if ($merge_list[$index][IDX] > $#list2) {
splice(@merge_list, $index, 1);
}
else {
$merge_list[$index][SUM] = $merge_list[$index][VAL] + $list2[$merge_list[$index][IDX]];
}
}
}
sub LR_solution_2 {
#Limbic~Region's second posted solution
my ($list_ref1, $list_ref2) = @_;
my @list1;
my @list2;
if (@$list_ref1 <= @$list_ref2) {
@list1 = @$list_ref1;
@list2 = @$list_ref2;
} else {
@list1 = @$list_ref2;
@list2 = @$list_ref1;
}
my @merge_list = ((0) x scalar @list1); # use smaller of 2 lists
while (1) {
my ($min, $idx);
for (my $i = 0; $i < @merge_list; ++$i) {
next if $merge_list[$i] > $#list2;
my $sum = $list1[$i] + $list2[$merge_list[$i]];
($min, $idx) = ($sum, $i) if ! defined $min || $sum < $min;
}
last if ! defined $min;
print OUT "$min\n";
$merge_list[$idx]++;
}
}
sub print_sums {
# blokhead's solution
my ($listA, $listB) = @_;
my $min = $listA->[0] + $listB->[0] - 1;
while ($min < $listA->[-1] + $listB->[-1]) {
my $nextmin = undef;
my $multiplicity = 0;
no warnings; # Throws warnings on uninitialized value comparisons
for my $i (0 .. $#$listA) {
for my $j (0 .. $#$listB) {
my $sum = $listA->[$i] + $listB->[$j];
if ($sum > $min and ($sum < $nextmin or not defined $nextmin)) {
($nextmin, $multiplicity) = ($sum, 1);
} elsif ($sum == $nextmin) {
$multiplicity++;
}
}
}
print OUT ( ($nextmin) x $multiplicity);
$min = $nextmin;
}
}
####
Benchmark: timing 100 iterations of Baseline, Integers, LR_1, LR_2, Queue, blokhead...
Baseline: 0.554613 wallclock secs ( 0.54 usr + 0.01 sys = 0.55 CPU) @ 181.82/s (n=100)
(warning: too few iterations for a reliable count)
Integers: 32.3786 wallclock secs (32.37 usr + 0.00 sys = 32.37 CPU) @ 3.09/s (n=100)
LR_1: 18.7755 wallclock secs (18.77 usr + 0.00 sys = 18.77 CPU) @ 5.33/s (n=100)
LR_2: 69.7311 wallclock secs (69.73 usr + 0.00 sys = 69.73 CPU) @ 1.43/s (n=100)
Queue: 2.55908 wallclock secs ( 2.55 usr + 0.00 sys = 2.55 CPU) @ 39.22/s (n=100)
blokhead: 95.6313 wallclock secs (95.62 usr + 0.01 sys = 95.63 CPU) @ 1.05/s (n=100)
Rate blokhead LR_2 Integers LR_1 Queue Baseline
blokhead 1.05/s -- -27% -66% -80% -97% -99%
LR_2 1.43/s 37% -- -54% -73% -96% -99%
Integers 3.09/s 195% 115% -- -42% -92% -98%
LR_1 5.33/s 409% 271% 72% -- -86% -97%
Queue 39.2/s 3650% 2635% 1169% 636% -- -78%
Baseline 182/s 17287% 12578% 5785% 3313% 364% --
####
Benchmark: timing 100000 iterations of Baseline, Integers, LR_1, LR_2, Queue, blokhead...
Baseline: 1.62766 wallclock secs ( 1.63 usr + 0.00 sys = 1.63 CPU) @ 61349.69/s (n=100000)
Integers: 7.29155 wallclock secs ( 7.28 usr + 0.01 sys = 7.29 CPU) @ 13717.42/s (n=100000)
LR_1: 7.017 wallclock secs ( 7.02 usr + 0.00 sys = 7.02 CPU) @ 14245.01/s (n=100000)
LR_2: 7.79621 wallclock secs ( 7.80 usr + 0.00 sys = 7.80 CPU) @ 12820.51/s (n=100000)
Queue: 3.60201 wallclock secs ( 3.60 usr + 0.00 sys = 3.60 CPU) @ 27777.78/s (n=100000)
blokhead: 9.88667 wallclock secs ( 9.89 usr + 0.00 sys = 9.89 CPU) @ 10111.22/s (n=100000)
Rate blokhead LR_2 Integers LR_1 Queue Baseline
blokhead 10111/s -- -21% -26% -29% -64% -84%
LR_2 12821/s 27% -- -7% -10% -54% -79%
Integers 13717/s 36% 7% -- -4% -51% -78%
LR_1 14245/s 41% 11% 4% -- -49% -77%
Queue 27778/s 175% 117% 103% 95% -- -55%
Baseline 61350/s 507% 379% 347% 331% 121% --