Merge pull request #5616 from drbaggy/master

Neater (faster and more readable) code for example 2

2 files changed, 79 insertions, 4 deletions

diff --git a/challenge-150/james-smith/README.md b/challenge-150/james-smith/README.md
index 1e048774b7..552d615280 100644
--- a/challenge-150/james-smith/README.md
+++ b/challenge-150/james-smith/README.md
@@ -70,3 +70,34 @@ say for grep{my$t=$_;!grep{!($t%$_)}@p2}1..$N;
 ```
 
 **Note** `say` without any parameters - outputs the contents of `$_` and then sends a carriage return. so `say for @A;` outputs all elements of the array `@A` on separate lines.
+
+## Follow up
+
+We can re-write the inefficient double `grep` more elegantly with nested `for`*each* loops. The new code becomes:
+
+```perl
+my ( $N, @p2 ) = ( @ARGV ? $ARGV[0] : 500 , 4 );
+
+P: for ( my $c = 3; $c*$c <= $N; $c += 2 ) {
+  $_ > $c  ? last : $c*$c % $_ || next P for @p2;
+  push @p2, $c*$c;
+}
+
+O: for my $t ( 1 .. $N ) {
+  $_ > $t  ? last :    $t % $_ || next O for @p2;
+  say  $t;
+}
+```
+
+### Notes:
+ * We optimize the inner loop by allowing it to finish early if:
+    * We have a prime^2 value greater than `$t`
+    * We have a square factor
+
+ * The difference in these two cases are:
+    * We end the inner loop and output the number as a square-free int (`last`)
+    * We skip to the next iteration of the outer loop (`next O`) without doing anything
+
+ * The optimized version gives anywhere between 75% and 90% speed up... (values of `$N` between 100 and 1,000,000)
+
+ * We have also re-written the prime generator to use the same `next {label}` trick, and this leads to a certain symmetry between the two loops. 
diff --git a/challenge-150/james-smith/perl/ch-2.pl b/challenge-150/james-smith/perl/ch-2.pl
index a6af28ddcd..95b4f2464c 100644
--- a/challenge-150/james-smith/perl/ch-2.pl
+++ b/challenge-150/james-smith/perl/ch-2.pl
@@ -4,11 +4,55 @@ use strict;
 
 use warnings;
 use feature qw(say);
+use Test::More;
+use Benchmark qw(cmpthese timethis);
+use Data::Dumper qw(Dumper);
 
-my($N,@p2) = (@ARGV?$ARGV[0]:500,4);
+cmpthese( 500_000, {
+  'grep' => sub { non_square(   100 ) },
+  'for'  => sub { non_square_x( 100 ) },
+});
 
-for(my$c=3;$c*$c<$N;$c+=2){
-  ($_>$c)?((push@p2,$c*$c),last):$c*$c%$_||last for@p2;
+cmpthese( 50_000, {
+  'grep' => sub { non_square(   1000 ) },
+  'for'  => sub { non_square_x( 1000 ) },
+});
+
+cmpthese( 5_000, {
+  'grep' => sub { non_square(   10_000 ) },
+  'for'  => sub { non_square_x( 10_000 ) },
+});
+
+cmpthese( 500, {
+  'grep' => sub { non_square(   100_000 ) },
+  'for'  => sub { non_square_x( 100_000 ) },
+});
+
+cmpthese( 100, {
+  'grep' => sub { non_square(   1_000_000 ) },
+  'for'  => sub { non_square_x( 1_000_000 ) },
+});
+
+sub non_square {
+  my($N,@p2) = ($_[0],4);
+  for(my$c=3;$c*$c<$N;$c+=2){
+    ($_>$c)?((push@p2,$c*$c),last):$c*$c%$_||last for@p2;
+  }
+  return grep{my$t=$_;!grep{!($t%$_)}@p2}1..$N;
 }
 
-say for grep{my$t=$_;!grep{!($t%$_)}@p2}1..$N;
+sub non_square_x {
+  my ( $N, @p2, @r ) = ( @ARGV ? $ARGV[0] : 500 , 4 );
+
+  P: for ( my $c = 3; $c*$c <= $N; $c += 2 ) {
+    $_ > $c  ? last : $c*$c % $_ || next P for @p2;
+    push @p2, $c*$c;
+  }
+
+  O: for my $t ( 1 .. $N ) {
+    $_ > $t  ? last :    $t % $_ || next O for @p2;
+    push @r, $t;
+  }
+
+  @r;
+}