Perl 6 - Starting with the basics - Arrays and Lists(sorted words(alphabetical order), bisection search(binary search))

Think Perl 6

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• Perl 6 (プログラミング言語)
• Rakudo(コンパイラ、実装)

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 9(Arrays and Lists)の Exercise 9-10.を取り組んでみる。

Exercise 9-10.

コード(Emacs)

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

say '10.';
my @words = 'words.txt'.IO.lines;

sub bisect(@array, $item) {
    return False unless @array;
    
    my $idx = Int(@array.elems / 2);
    my $middle = @array[$idx];
    
    return True if $item eq $middle;
    return bisect(@array[0..$idx - 1], $item) if $item lt $middle;
    return bisect(@array[$idx+1..*-1], $item);
}
sub bisect1(@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);
}


sub find(@array, $item) {
    for @array {
        return True if $_ eq $item;
    }
    return False;
}

for <think perl 6 aa zymurgy a zzzzzzzzzz> {
    say $_;
    my $t = now;
    my $bln = bisect(@words, $_);
    $t = now - $t;
    say 'bisect:  ', $bln, " {$t}s";
    $t = now;
    $bln = find(@words, $_);
    $t = now - $t;
    say 'find:    ', $bln, " {$t}s";
    $t = now;
    $bln = bisect1(@words, $_);
    $t = now - $t;
    say 'bisect1: ', $bln, " {$t}s";
}

入出力結果(Terminal, REPL)

$ ./sample10.pl
10.
think
bisect:  True 0.1543282s
find:    True 0.0698243s
bisect1: True 0.0010259s
perl
bisect:  False 0.1425609s
find:    False 0.07582829s
bisect1: False 0.0007793s
6
bisect:  False 0.1442627s
find:    False 0.0930395s
bisect1: False 0.00075812s
aa
bisect:  True 0.1760245s
find:    True 0.00033429s
bisect1: True 0.00065462s
zymurgy
bisect:  True 0.14378873s
find:    True 0.0758514s
bisect1: True 0.00061357s
a
bisect:  False 0.14224503s
find:    False 0.072161s
bisect1: False 0.0007307s
zzzzzzzzzz
bisect:  False 0.14194162s
find:    False 0.0747634s
bisect1: False 0.0005318s
$