2017年5月19日金曜日

開発環境

Think Perl 6: How to Think Like a Computer Scientist (Laurent Rosenfeld(著)、Allen B. Downey(著)、Oreilly & Associates Inc)のPart 1(Starting with the basics)、Chapter 10(Hashes)の Exercise: 10-1、10-2.を取り組んでみる。

Exercise: 10-1、10-2.

コード(Emacs)

#!/usr/bin/env perl6
# -*- coding: utf-8 -*-

say '1.';
my @words = 'words.txt'.IO.lines;
my %words;
for @words {
    %words{$_} = 1;
}

my @words0 = <think perl 6 aa zymurgy a zzzzzzzzzz>;

say 'hash';
my $t = now;
for @words0 {
    say $_ if %words{$_}:exists;
}
say now - $t;

sub bisect(@array, $item) {
    sub inner($idx1, $idx2) {
        return False unless $idx1 <= $idx2;

        my $idx = Int(($idx1 + $idx2) / 2);
        my $middle = @array[$idx];

        return True if $item eq $middle;
        return inner($idx1, $idx - 1) if $item lt $middle;
        return inner($idx + 1, $idx2);
    }
    return inner(0, @array.end);
}
say 'bisect(binary search)';
$t = now;
for @words0 {
    say $_ if bisect(@words, $_);
}
say now - $t;

say '2.';
sub ack($m, $n) {
    return $n + 1 if $m == 0;
    return ack($m - 1, 1) if $m > 0 and $n == 0;
    return ack($m - 1, ack($m, $n - 1));
}

my %ackmemo;
sub ack-memo($m, $n) {    
    return $n + 1 if $m == 0;
    return %ackmemo{$m}{$n} if %ackmemo{$m}{$n}:exists;
    if $n == 0 {
        %ackmemo{$m}{$n} = ack-memo($m - 1, 1);
    } else {
        %ackmemo{$m}{$n} = ack-memo($m - 1, ack-memo($m, $n - 1));
    }
    return %ackmemo{$m}{$n}
}

$t = now;
say ack(3, 4);
say now - $t;

$t = now;
say ack-memo(3, 4);
say now - $t;

dd %ackmemo;

for %ackmemo.keys.sort {
    say $_, ' => ', %ackmemo{$_};
}

# say ack-memo 4, 4;
for 5..7 {
    say "ack(3, $_)";
    $t = now;
    say ack(3, $_);
    say now - $t;

    $t = now;
    say ack-memo(3, $_);
    say now - $t;
}

入出力結果(Terminal, REPL)

$ ./sample1.pl
1.
hash
think
aa
zymurgy
0.0012601
bisect(binary search)
think
aa
zymurgy
0.00382127
2.
125
0.0173883
125
0.0067921
Hash %ackmemo = {"1" => ${"1" => 3, "10" => 12, "100" => 102, "101" => 103, "102" => 104, "103" => 105, "104" => 106, "105" => 107, "106" => 108, "107" => 109, "108" => 110, "109" => 111, "11" => 13, "110" => 112, "111" => 113, "112" => 114, "113" => 115, "114" => 116, "115" => 117, "116" => 118, "117" => 119, "118" => 120, "119" => 121, "12" => 14, "120" => 122, "121" => 123, "122" => 124, "123" => 125, "13" => 15, "14" => 16, "15" => 17, "16" => 18, "17" => 19, "18" => 20, "19" => 21, "2" => 4, "20" => 22, "21" => 23, "22" => 24, "23" => 25, "24" => 26, "25" => 27, "26" => 28, "27" => 29, "28" => 30, "29" => 31, "3" => 5, "30" => 32, "31" => 33, "32" => 34, "33" => 35, "34" => 36, "35" => 37, "36" => 38, "37" => 39, "38" => 40, "39" => 41, "4" => 6, "40" => 42, "41" => 43, "42" => 44, "43" => 45, "44" => 46, "45" => 47, "46" => 48, "47" => 49, "48" => 50, "49" => 51, "5" => 7, "50" => 52, "51" => 53, "52" => 54, "53" => 55, "54" => 56, "55" => 57, "56" => 58, "57" => 59, "58" => 60, "59" => 61, "6" => 8, "60" => 62, "61" => 63, "62" => 64, "63" => 65, "64" => 66, "65" => 67, "66" => 68, "67" => 69, "68" => 70, "69" => 71, "7" => 9, "70" => 72, "71" => 73, "72" => 74, "73" => 75, "74" => 76, "75" => 77, "76" => 78, "77" => 79, "78" => 80, "79" => 81, "8" => 10, "80" => 82, "81" => 83, "82" => 84, "83" => 85, "84" => 86, "85" => 87, "86" => 88, "87" => 89, "88" => 90, "89" => 91, "9" => 11, "90" => 92, "91" => 93, "92" => 94, "93" => 95, "94" => 96, "95" => 97, "96" => 98, "97" => 99, "98" => 100, "99" => 101}, "2" => ${"1" => 5, "10" => 23, "11" => 25, "12" => 27, "13" => 29, "14" => 31, "15" => 33, "16" => 35, "17" => 37, "18" => 39, "19" => 41, "2" => 7, "20" => 43, "21" => 45, "22" => 47, "23" => 49, "24" => 51, "25" => 53, "26" => 55, "27" => 57, "28" => 59, "29" => 61, "3" => 9, "30" => 63, "31" => 65, "32" => 67, "33" => 69, "34" => 71, "35" => 73, "36" => 75, "37" => 77, "38" => 79, "39" => 81, "4" => 11, "40" => 83, "41" => 85, "42" => 87, "43" => 89, "44" => 91, "45" => 93, "46" => 95, "47" => 97, "48" => 99, "49" => 101, "5" => 13, "50" => 103, "51" => 105, "52" => 107, "53" => 109, "54" => 111, "55" => 113, "56" => 115, "57" => 117, "58" => 119, "59" => 121, "6" => 15, "60" => 123, "61" => 125, "7" => 17, "8" => 19, "9" => 21}, "3" => ${"4" => 125}}
1 => {1 => 3, 10 => 12, 100 => 102, 101 => 103, 102 => 104, 103 => 105, 104 => 106, 105 => 107, 106 => 108, 107 => 109, 108 => 110, 109 => 111, 11 => 13, 110 => 112, 111 => 113, 112 => 114, 113 => 115, 114 => 116, 115 => 117, 116 => 118, 117 => 119, 118 => 120, 119 => 121, 12 => 14, 120 => 122, 121 => 123, 122 => 124, 123 => 125, 13 => 15, 14 => 16, 15 => 17, 16 => 18, 17 => 19, 18 => 20, 19 => 21, 2 => 4, 20 => 22, 21 => 23, 22 => 24, 23 => 25, 24 => 26, 25 => 27, 26 => 28, 27 => 29, 28 => 30, 29 => 31, 3 => 5, 30 => 32, 31 => 33, 32 => 34, 33 => 35, 34 => 36, 35 => 37, 36 => 38, 37 => 39, 38 => 40, 39 => 41, 4 => 6, 40 => 42, 41 => 43, 42 => 44, 43 => 45, 44 => 46, 45 => 47, 46 => 48, 47 => 49, 48 => 50, 49 => 51, 5 => 7, 50 => 52, 51 => 53, 52 => 54, 53 => 55, 54 => 56, 55 => 57, 56 => 58, 57 => 59, 58 => 60, 59 => 61, 6 => 8, 60 => 62, 61 => 63, 62 => 64, 63 => 65, 64 => 66, 65 => 67, 66 => 68, 67 => 69, 68 => 70, 69 => 71, 7 => 9, 70 => 72, 71 => 73, 72 => 74, 73 => 75, 74 => 76, 75 => 77, 76 => 78, 77 => 79, 78 => 80, ...}
2 => {1 => 5, 10 => 23, 11 => 25, 12 => 27, 13 => 29, 14 => 31, 15 => 33, 16 => 35, 17 => 37, 18 => 39, 19 => 41, 2 => 7, 20 => 43, 21 => 45, 22 => 47, 23 => 49, 24 => 51, 25 => 53, 26 => 55, 27 => 57, 28 => 59, 29 => 61, 3 => 9, 30 => 63, 31 => 65, 32 => 67, 33 => 69, 34 => 71, 35 => 73, 36 => 75, 37 => 77, 38 => 79, 39 => 81, 4 => 11, 40 => 83, 41 => 85, 42 => 87, 43 => 89, 44 => 91, 45 => 93, 46 => 95, 47 => 97, 48 => 99, 49 => 101, 5 => 13, 50 => 103, 51 => 105, 52 => 107, 53 => 109, 54 => 111, 55 => 113, 56 => 115, 57 => 117, 58 => 119, 59 => 121, 6 => 15, 60 => 123, 61 => 125, 7 => 17, 8 => 19, 9 => 21}
3 => {4 => 125}
ack(3, 5)
253
0.08302289
253
0.003126
ack(3, 6)
509
0.25801006
509
0.0064397
ack(3, 7)
1021
1.0393494
1021
0.011712
$

0 コメント:

コメントを投稿