読者です 読者をやめる 読者になる 読者になる

Higher order perl 1.1

perl hop

Higher order perlという本を買いました。他の本を読んでいる途中なので
ちら見した程度ですが、とりあえず 1.1を読みました。


10進数を2進数にするというものですが、その関数が再帰関数であるという
ことが特徴的なんですかね。


で、比較のコードを書きたくなったので少し書いてみた。

#!/usr/local/bin/perl
use strict;
use warnings;

use Benchmark qw(cmpthese);

cmpthese(1000000, {
    not_tail_recursive => sub {
        binary_recursive( int(rand(10000)) );
    },

    tail_recursive => sub {
        binary_tail_recursive( int(rand(10000)) );
    },

    sprintf => sub {
        sprintf("%b", int(rand(10000)));
    },
});

exit;

sub binary_recursive {
    my $n = shift;

    if ( $n <= 1) {
        return $n;
    } else {
        return binary_recursive($n >> 1) . ($n & 1);
    }
}


sub binary_tail_recursive {
    my $n = shift;

    return _binary_tail_recursive($n, '');
}

sub _binary_tail_recursive {
    my ($n, $acc) = @_;

    if ($n <= 1) {
        return reverse ($acc . $n);
    } else {
        return _binary_tail_recursive($n >> 1, $acc . ($n & 1));
    }
}

結果は以下のような具合.
当たり前だが、sprintfが一番早い。末尾再帰とそうでないものの差は
大して見られなかった。やっぱりtail recursiveだよねって言いたかったん
ですが、ここでは言えませんでした。

                        Rate not_tail_recursive  tail_recursive          sprintf
not_tail_recursive   97466/s                 --             -1%             -97%
tail_recursive       98619/s                 1%              --             -97%
sprintf            3225806/s              3210%           3171%               --

徐々に読み進められるように他の本を読み終えていかなければ。