Drkcore

13082006 music

メタモのチケットがキマシタヨ

メタモのチケットきた。

BLACK STROBE MARK FARINA が気になる。

11082006 perl

続　perlでフィボナッチ

昨日に引き続き3章を読み進めていたら、フィボナッチ数をキャッシュで高速化する例が。

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 6402円 ( 2005-03-28 )

コードはこんな感じで、割と普通な。

my %cache;

sub fib{
    my $n = shift;
    unless (exists $cache{$n}){
    if($n < 2){
        $cache{$n} = 1;
    }else{   
        $cache{$n} = fib($n-1) + fib($n-2);
    }
    }
    return $cache{$n};
}

さて、昨日のタプルを使ったコードとどっちが速いのか比べてみた。

#!/usr/bin/perl

use strict;
use warnings;
use Benchmark qw(cmpthese);

sub fibStep {
    my $n = shift;
    return [$n->[1], $n->[0] + $n->[1]];
}

sub fibPair {
    my ($n, $fs, $fp) = @_;
    return [0,1] if ($n == 0);
    return $fs->($fp->($n-1,$fs,$fp))
}

sub fastFib {
    my $n = shift;
    my $fs = \&fibStep;
    my $fp = \&fibPair;
    my $fib_num = $fp->($n,$fs,$fp);
    return $fib_num->[0];
}

my %cache;

sub fib{
    my $n = shift;
    unless (exists $cache{$n}){
    if($n < 2){
        $cache{$n} = 1;
    }else{   
        $cache{$n} = fib($n-1) + fib($n-2);
    }
    }
    return $cache{$n};
}

my $number = 50;
my $count = 10000000;

my $fibcache = \&fib;
my $fibfast = \&fib;

cmpthese($count, {
        'Cache' => $fibcache->($number),
        'Fast' => $fibfast->($number)
    });

とりあえず1000万回まわしてみたけどそれでもwarningがでるので、この際無視。

./fib.pl 
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
            Rate  Fast Cache
Fast  38461538/s    --  -27%
Cache 52631579/s   37%    --

キャッシュしたほうが速いというのがイマイチ理解できん。何でじゃろか？

10082006 perl Haskell

haskellでフィボナッチそしてPerlで書いてみた

普通のhaskellプログラミングを読み終えて、なんか次に読むものないかなと探していたら、webarchiveに面白そうなページがあることを知ったので、ダウンロードして読んでます。

3回目の講義資料に、タプルを使って高速にフィボナッチ数を計算する話があったので、なんでそうなるのかを理解するために手で書き下してみた。

普通に書くとこんな感じ(fib)。

fact :: Int -> Int
fact n
  | n == 0  = 1
  | n > 0   = fact (n-1) * n

書き下すと、計算量があっという間に増えていくことがわかる。

fib 5
=> fib 3 + fib 4
=> (fib 1 + fib 2) + (fib 2 + fib 3)
=> (fib1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + fib 2))
=> (fib1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + (fib 0 + fib 1)))

タプルを使った例(fastfib)

フィボナッチ数列を効率良く計算する方法を考えよう．前に見たとおり，フィボナッチ数列の各項は，その前の二つの項の和である．逆に言えば，二つの連続した項の値が与えられれば，次の項を計算するのは簡単なのだ．

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibPair :: Int -> (Int, Int)
fibPair n
  | n == 0    = (0, 1)
  | otherwise = fibStep (fibPair (n-1))

fastFib :: Int -> Int
fastFib = fst . fibPair

コードを眺めただけではなんで速くなるのか実感がわかなかったので、書き下してみる。

fastFib 5
=> fst (fibPair 5)
=> fst (fibStep (fibPair 4))
=> fst (fibStep fibStep (fibPair 3))
=> fst (fibStep fibStep fibStep (fibPair 2))
=> fst (fibStep fibStep fibStep fibStep (fibPair 1))
=> fst (fibStep fibStep fibStep fibStep fibStep (fibPair 0))
=> fst (fibStep fibStep fibStep fibStep fibStep (0, 1))
=> fst (fibStep fibStep fibStep fibStep (1, 1))
=> fst (fibStep fibStep fibStep (1, 2))
=> fst (fibStep fibStep (2, 3))
=> fst (fibStep (3, 5))
=> fst (5, 7)
=> 5

をを、タプルにすることで、計算量が減ってます、自分で展開していくとなるほどとよくわかる。

さて、最近Higher-order Perlを読んでいる僕としては、これをperlで書いてみたくなるわけである。

#!/usr/bin/perl

use strict;
use warnings;

sub fibStep {
    my $n = shift;
    return [$n->[1], $n->[0] + $n->[1]];
}

sub fibPair {
    my ($n, $fs, $fp) = @_;
    return [0,1] if ($n == 0);
    return $fs->($fp->($n-1,$fs,$fp))
}

sub fastFib {
    my $n = shift;
    my $fs = \&fibStep;
    my $fp = \&fibPair;
    my $fib_num = $fp->($n,$fs,$fp);
    return $fib_num->[0];
}

my $number = shift;
print fastFib($number)

サブルーチンのリファレンスを引数にとらないといけないのがhaskellと異なるとこかな。あとは書いてて思ったのは関数の型を書くとプログラムの流れが理解しやすいナァと。

実行すると一瞬で計算が終わる（速い!）

実際に処理の流れを追うために-dオプションを付けて実行してsを連打すると、main::fibPairがどんどん実行されて$nが0になったところで今度はmain::fibStepが次々実行されていく様がわかる。

Higher-order Perlの5章にもフィボナッチ数列のことが書いてあるのだが、まだそこまで読み進めていない。(今3章突入したところ)

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 5692円 ( 2005-03-28 )

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / ?円 ( 2006-06-01 )

haskellを勉強しながら、Higher-order Perlを読むと、色々新たな発見があって楽しい。

10082006 perl

Sudoku

実家に帰ったら、婆さんが数独にはまってた。ボケ防止にいいらしい。ちょうどいいので、flashの数独をgoogleで適当に探してきてお気に入りに登録しておいてやったら喜ばれたヨ。まぁ、使うかどうかわからんけど。

ちょうど、Highr Order Perl読み始めたところだし、家に戻ってきて、数独ソルバでも書いてみるかと思ってたら、タイミングよくUno, dos, tres, quatro!にエントリが。

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 6402円 ( 2005-03-28 )

バックトラック法ってのを使えばいいのねと自分で書いてみたのはマス目を一つ一つ移動してくコードだったんだけど、再帰深すぎるヨっていうエラーを吐いて終了。なんかダメダメだなぁ。他の人のを読んでみるとまだ埋まってないマス目を再帰で埋めていくべきだったことに気付いた。ちょっとこれに引っ張られたかなと反省。

まだ埋まってないマス目の配列と、過程として数字を置いたマス目の配列の二つを用意して、バックトラック法で解くというわけですな。

とか、わかった上で、三行数独ソルバを読むと、説明もついてるしよくわかった、素敵。

家のマシンで三行数独ソルバを実行してみるとこんな感じ。

 $ time perl sudoku.pl < sample
 825169734
 463857921
 917234658
 684712593
 759386142
 231495867
 548621379
 376948215
 192573486 #本当はココまで一行で出力

 real    0m1.439s
 user    0m1.436s
 sys     0m0.004s

プログラム・プロムナードにhaskellの数独ソルバが載ってたのでそれも実行してみた。ちゃんと理解しないといけないと思いつつ、今回はコピペ。ghciで計算させた。

 *Main> sudoku sample
 [8 2 5 1 6 9 7 3 4
 4 6 3 8 5 7 9 2 1
 9 1 7 2 3 4 6 5 8

 6 8 4 7 1 2 5 9 3
 7 5 9 3 8 6 1 4 2
 2 3 1 4 9 5 8 6 7
 5 4 8 6 2 1 3 7 9
 3 7 6 9 4 8 2 1 5
 1 9 2 5 7 3 4 8 6
 ]
 (0.28 secs, 26584692 bytes)