Created
July 21, 2019 04:08
-
-
Save yzhernand/0e74d23bcd040e3a3106520763d55613 to your computer and use it in GitHub Desktop.
Perl Weekly Challenge #17 Challenge 1 - Solution with benchmarking and tests
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env perl | |
use v5.24; | |
use strict; | |
use warnings; | |
use feature qw(signatures); | |
no warnings "experimental::signatures"; | |
use Carp; | |
use Benchmark::Forking qw(cmpthese); | |
use Memoize; | |
=for comment | |
Create a script to demonstrate Ackermann function. The Ackermann function is defined as below, m and n are positive number: | |
A(m, n) = n + 1 if m = 0 | |
A(m, n) = A(m - 1, 1) if m > 0 and n = 0 | |
A(m, n) = A(m - 1, A(m, n - 1)) if m > 0 and n > 0 | |
=cut | |
memoize("A"); | |
sub A ( $m = 3, $n = 3) { | |
croak "Error: function only defined for nonnegative integers." | |
. "(got: m = $m, n = $n)" | |
if ( $m < 0 && $n < 0 ); | |
# A(m, n) = n + 1 if m = 0 | |
return $n + 1 if $m == 0; | |
# A(m, n) = A(m - 1, 1) if m > 0 and n = 0 | |
# A(m, n) = A(m - 1, A(m, n - 1)) if m > 0 and n > 0 | |
return A( $m - 1, ($n == 0) ? 1 : A($m, $n-1) ); | |
} | |
sub A_no_memo ( $m = 3, $n = 3 ) { | |
croak "Error: function only defined for nonnegative integers." | |
. "(got: m = $m, n = $n)" | |
if ( $m < 0 && $n < 0 ); | |
# A(m, n) = n + 1 if m = 0 | |
return $n + 1 if $m == 0; | |
# A(m, n) = A(m - 1, 1) if m > 0 and n = 0 | |
# A(m, n) = A(m - 1, A(m, n - 1)) if m > 0 and n > 0 | |
return A( $m - 1, ($n == 0) ? 1 : A($m, $n-1) ); | |
} | |
use Test::More tests => 5; | |
ok(A(1,2) == 4, "A(1,2) == 4"); | |
ok(A(2,2) == 7, "A(2,2) == 7"); | |
ok(A(2,4) == 11, "A(2,4) == 11"); | |
ok(A(3,3) == 61, "A(3,3) == 61"); | |
ok(A(3,4) == 125, "A(3,4) == 125"); | |
=for comment | |
cmpthese( | |
-10, | |
{ 'memo' => \&A, | |
'no_memo' => \&A_no_memo | |
} | |
); | |
Rate no_memo memo | |
no_memo 269501/s -- -68% | |
memo 850801/s 216% -- | |
=cut |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment