2013-01-20日誌

アルゴリズムをはじめよう P1-P115

アルゴリズムを、はじめよう

こういう本は、読んだだけだと無駄でしかないので、写経してみました。今回それぞれ、素直なパターンと再帰するパターンで書いてみた。rubyとpythonでも実装しようかと思ったけど、あまり代わり映えがしないので、やめました。
関数型言語で書くとちょっと違うのかな?

線形探索

use strict;
use warnings;
use 5.14.2;

# 素直なパターン
sub search {
    my ($list, $target) = @_;

    for (my $i = 0; $i < scalar(@$list); $i++) {
        return $i if $list->[$i] == $target;
    }
    return -1;
}

# 再帰するやつ
sub search2 {
    my ($list, $target, $index) = @_;
    $index ||= 0;
    return -1 if scalar(@$list) == $index;
    return $list->[$index] == $target ?
        $index : search2($list, $target, $index + 1);
}

use Test::More;

is( search([ 1,2,3,4,5,6,7,8,9 ], 5) => 4);
is( search([ 2,4,5,7,8,1,3,9,6 ], 2) => 0);
is( search([ 2,4,5,7,8,1,3,9,6 ], 6) => 8);
is( search([ 2,4,5,7,8,1,3,9,6 ], 0) => -1);

is( search2([ 1,2,3,4,5,6,7,8,9 ], 5) => 4);
is( search2([ 2,4,5,7,8,1,3,9,6 ], 2) => 0);
is( search2([ 2,4,5,7,8,1,3,9,6 ], 6) => 8);
is( search2([ 2,4,5,7,8,1,3,9,6 ], 0) => -1);

done_testing;

二分探索

再帰パターンの引数が多いのが少し気になる。

use strict;
use warnings;
use 5.14.2;
use POSIX qw( floor );

# 素直なパターン
sub search {
    my ($list, $target) = @_;

    my $length = scalar(@$list);
    my $head = 0;
    my $tail = $length -1;
    while ( $head <= $tail ) {
        my $middle = floor( ($tail + $head) /2 );
        return $middle if $list->[$middle] == $target;

        ($head, $tail) = $list->[$middle] > $target ?
            ($head, $middle -1) : ($middle +1, $tail);
    }

    return -1;
}

sub search2 {
    my ($list, $target, $length, $head, $tail) = @_;

    $length //= scalar(@$list);
    $head   //= 0;
    $tail   //= $length -1;

    return -1 if $head > $tail;

    my $middle = floor( ($tail + $head) /2 );
    return $middle if $list->[$middle] == $target;

    ($head, $tail) = $list->[$middle] > $target ?
        ($head, $middle -1) : ($middle +1, $tail);
    search2($list, $target, $length, $head, $tail);
}

use Test::More;

is( search([ 1..10 ],  0) => -1);
is( search([ 1..10 ],  5) =>  4);
is( search([ 1..10 ],  1) =>  0);
is( search([ 1..10 ], 10) =>  9);

is( search([ 1..100000 ], 10) => 9);

is( search([ 1..1000, 9000..10000 ], 1001) => -1);
is( search([ 1..1000, 9000..10000 ], 8999) => -1);

is( search2([ 1..10 ],  0) => -1);
is( search2([ 1..10 ],  5) =>  4);
is( search2([ 1..10 ],  1) =>  0);
is( search2([ 1..10 ], 10) =>  9);

is( search2([ 1..100000 ], 10) => 9);

is( search2([ 1..1000, 9000..10000 ], 1001) => -1);
is( search2([ 1..1000, 9000..10000 ], 8999) => -1);

done_testing;