use benchmarking to realise that flattening is wrong...

1 files changed, 103 insertions, 6 deletions

diff --git a/challenge-111/james-smith/perl/ch-1.pl b/challenge-111/james-smith/perl/ch-1.pl
index aae397ff35..02fa3c878a 100644
--- a/challenge-111/james-smith/perl/ch-1.pl
+++ b/challenge-111/james-smith/perl/ch-1.pl
@@ -5,6 +5,63 @@ use strict;
 use warnings;
 use feature qw(say);
 use Test::More;
+use Benchmark qw(cmpthese);
+
+## Today's is an interesting challenge ... to check to
+## see if a value is in the matrix....
+##
+## Initially this looks like we need to define some
+## efficient sorting algorithm to flatten the array
+## and then search it
+##
+## We implement this... but we compare it against some
+## alternative simple methods. We don't get the result
+## we expect...
+##
+## We use cmpthese to compare the performance...
+##
+## Our methods are:
+##
+##  find_val_search - this is the binary search on
+##                    the flattened array
+##  find_grep_map   - use grep to compare the value
+##                    on the flattened array
+##  find_map_grep   - foreach row use grep to compare
+##                    values, and join these together
+##                    with map
+##
+## Timings using Benchmark cmpthese
+##
+##            Rate   Search Grep-Map Map-Grep  Flatten
+## Search   4808/s       --     -11%     -33%     -43%
+## Grep-Map 5376/s      12%       --     -25%     -36%
+## Map-Grep 7143/s      49%      33%       --     -15%
+## Flatten  8403/s      75%      56%      18%       --
+##
+## Flatten is for comparison - it actually
+## does nothing other than flatten the array - this
+## highlights how efficient each algorithm is
+##
+## So we see that the map_grep solution is 50% more
+## efficient than the search algorith (this is true
+## for all search method algorithms which flatten
+## the array first);
+##
+## With this in mind we look for one final method
+## which doesn't flatten the matrix into a single
+## array... this time we perform a search for each
+## row - to find the row we are on...
+## and then use grep to search this...
+##
+##                  Rate  Map-Grep Flatten Don't flatten
+## Map-Grep       6667/s        --    -21%          -65%
+## Flatten        8475/s       27%      --          -55%
+## Don't flatten 18868/s      183%    123%            --
+##
+## We can see that this method is nearly 3 times
+## as efficient as the "most effective" search on the
+## matrix by using map in some way...
+##
 
 my $matrix = [
   [  1,  2,  3,  5,  7 ],
@@ -15,7 +72,7 @@ my $matrix = [
 ];
 
 ## Create a test set - numbers from -10 to 60...
-my %TEST_SET = map { $_ => 0 } (-10..60);
+my %TEST_SET = map { $_ => 0 } (my @KEYS = -10..60);
 
 ## Set all to 0, and then iterate through the
 ## elements of the matrix and set the numbers
@@ -24,18 +81,58 @@ my %TEST_SET = map { $_ => 0 } (-10..60);
 $TEST_SET{$_} = 1 foreach map { @{$_} } @{$matrix};
 
 ## Run the original PWC test examples...
-is( find_val( 35, $matrix ), 0 );
-is( find_val( 39, $matrix ), 1 );
+is( find_val_search(   35, $matrix ), 0 );
+is( find_val_search(   39, $matrix ), 1 );
+is( find_val_map_grep( 35, $matrix ), 0 );
+is( find_val_map_grep( 39, $matrix ), 1 );
+is( find_val_grep_map( 35, $matrix ), 0 );
+is( find_val_grep_map( 39, $matrix ), 1 );
+is( find_val_dnf(      35, $matrix ), 0 );
+is( find_val_dnf(      39, $matrix ), 1 );
 
 ## Now run our full test set - from -10 to 60. This covers
 ## all cases within the list and a few either side...
 
-is( find_val( $_, $matrix ), $TEST_SET{$_} )
-  foreach sort {$a<=>$b} keys %TEST_SET;
+is( find_val_dnf(      $_, $matrix ), $TEST_SET{$_} ) foreach @KEYS;
+is( find_val_search(   $_, $matrix ), $TEST_SET{$_} ) foreach @KEYS;
+is( find_val_map_grep( $_, $matrix ), $TEST_SET{$_} ) foreach @KEYS;
+is( find_val_grep_map( $_, $matrix ), $TEST_SET{$_} ) foreach @KEYS;
 
 done_testing();
 
-sub find_val {
+cmpthese(10_000, {
+  q(Don't flatten) => sub { find_val_dnf(      $_, $matrix ) foreach @KEYS; },
+  'Flatten'        => sub { flatten(           $_, $matrix ) foreach @KEYS; },
+  'Search'         => sub { find_val_search(   $_, $matrix ) foreach @KEYS; },
+  'Grep-Map'       => sub { find_val_grep_map( $_, $matrix ) foreach @KEYS; },
+  'Map-Grep'       => sub { find_val_map_grep( $_, $matrix ) foreach @KEYS; },
+});
+
+sub find_val_dnf {
+  my($v,$m) = @_;
+  return 0 if $v < $m->[0][0] || $v > $m->[4][4];
+  my $i = $v < $m->[3][0]
+        ? ( $v < $m->[1][0] ? 0 : $v < $m->[2][0] ? 1 : 2 )
+        : ( $v < $m->[4][0] ? 3 : 4                       );
+  return 0 + grep { $v == $_ } @{$m->[$i]};
+}
+
+sub flatten {
+  my @list = map { @{$_} } @{$_[1]};
+  return 1;
+}
+
+sub find_val_map_grep {
+  my($v,$m)=@_;
+  return 0 + map { grep { $_ == $v } @{$_} } @{$m};
+}
+
+sub find_val_grep_map {
+  my($v,$m)=@_;
+  return 0 + grep { $_ == $v } map { @{$_} } @{$m};
+}
+
+sub find_val_search {
   ## Flatten the array provided into a list...
   my( $val, $m, @list ) = ( $_[0], 0, map { @{$_} } @{$_[1]} );