2010年9月27日
モダンなPerlを「読む」上で覚えておくとよい構文 第2回「リストを理解すれば配列とハッシュをより活用できる」
第1回から大分時間が空きましたが、なんと続きます。「次回は無名関数について書く」とか書いていましたが、先にリストについて言及することにします。
混同されがちですがこのエントリーでは「リスト」と「配列」を厳密に違うものとして扱います。結論を先に簡単に言ってしまうと、リストを配列に代入すれば配列になるし、リストをハッシュに代入すればハッシュになるということです。
Perlの式は値を返す
サブルーチンに限らずPerlのあらゆる式は評価された値を返します。返された値は代入先があれば代入され、代入先がなければ捨てられます。
値を返さないケース
ブロックは値を返しません(doを使えばブロックに値を返させることが出来ます)。例外的にuse文やpackage文は値を返しません。この二つはコンパイル時にコードを実行する前に最初に評価されるので値の返しようがありません。
さて、本題です。Perlの式の値の返し方には2種類あります。スカラーとリストです。スカラーを返すかリストを返すかはコンテキストに応じて変化することもあります。
リストコンテキストで返されるものがリスト(当たり前！)です。また、以下のようにすればリストを直に記述できます。
(1, 2, 3, 'hoge');
qw/1 2 3 hoge/;
「なんだ、配列じゃないか。」
いいえ、違います。そう思う人は以下のコードを実行してみて下さい。驚きの結果が得られることでしょう。
use Data::Dumper;
my $hoge = \(1, 2, 3, 'hoge'); #配列をリファレンス化している...？
print Dumper $hoge;
リストを配列リファレンスに代入したい場合は、リストをブラケットで囲めば配列リファレンスを返します。
my $hoge = [1, 2, 3, 'hoge'];
リストはハッシュキーにもなれる(けど使う機会はまずない)
以下のようなことも可能です。
my %hash;
$hash{qw/1 2 3/} = 'hoge';
print $hash{qw/1 2 3/}; # hoge
これはどういう事かというと、以下のコードを実行すれば分かります。
my %hash;
$hash{qw/1 2 3/} = 'hoge';
my ($key) = keys %hash; #キーを取り出す。
$key =~ s/(.)/'\x'.unpack('H2', $1)/eg; #バイトごとに16進にエンコーディング
print $key; # \x31\x1c\x32\x1c\x33
値が'\x1c'という文字で区切られていることが分かります。これは印字されない制御文字(FS)です。つまり印字されない文字を区切り文字に使った文字列(バイト列)がキーになっているという単純な仕掛けです。
なのでバイナリデータをハッシュキーにしたりすると上手くいかない可能性があります。
また、この区切り文字には特殊変数$;を使ってアクセスすることができます。
ややマニアックだけどかなりどうでも良いネタでした。
冒頭に書いたとおり、リストを配列に渡せば配列になり、ハッシュに渡せばハッシュになります。
前の記事でも書きましたが、ハッシュへの代入で使われる、"=>"(ファットコンマ)ってのは単なるカンマの代用であり、コードの可読性を上げるために使われています。ハッシュに渡されるのは単なるリストです。
my @arr = (1, 2, 3, 'hoge');
print $arr[1]; # 2
my %hash = (1, 2, 3, 'hoge'); # (1 => 2, 3 => 'hoge') と同じ
print $hash{3}; # hoge
配列はリストコンテキストで評価された場合リストを返します。ハッシュも同様にリストを返します。なので以下のようなことも可能です。
my @arr = (1, 2, 3, 'hoge');
my %hash = @arr;
print $hash{3}; # hoge
@arr = %hash; # こんなことも可能。ハッシュの順番が保証されないので、普通はやらない
これを利用して、名前付き引数的な関数を実現可能です。
#カッコの中はリスト。ファットコンマは単に可読性のため。
func(
hoge => 'fuga',
piyo => 11,
);
sub func {
#配列をハッシュに代入していて一見意味不明だが、配列がリストを
#返し、それがハッシュにわたっていると考える。
%hash = @_;
if ($hash{hoge} ){ ... }
}
また、以下のようにmapを組み合わせて、配列の各要素をキーとして、ハッシュを作成することが可能です。
my @arr = qw/hoge fuga piyo/;
%hash = map { $_ => 1 } @arr; #各要素を1で初期化
if($hash{hoge}){# @arr内に'hoge'が存在するかをチェックできる
...
}
mapやgrepは難解に思えますが、リスト操作には欠かせません。トリッキーに思えることも多いかと思いますが、そのうち慣れてくるでしょう。ただ、やりすぎはいけません。
リファレンス
[]や{}を使って、配列/ハッシュリファレンスを作成することが出来ますが、内部に単なるリストではなく、リストを返す式を書くこともできます。以下のような感じです。
$arr_ref = [1,2,3]; # 普通の書き方
$arr_ref = [qw/hoge fuga piyo/]; # こんな書き方も
$arr_ref = [@arr]; # \@arr と実質同じだけど、こう書かれることも多い
$arr_ref = [split //, $str]; #文字列を一文字づつ切り出した結果を配列リファレンスに
最後の式は少しびっくりするかもしれません。人によって多寡はありますが、これくらいだったら良く使われているように思います。mapやgrepがこの中で使われることもあります。例に因って自分で書くときはやりすぎは厳禁です。
また、オブジェクトのコンストラクタに引数を渡すときに、名前付き引数的な渡し方とハッシュリファレンスを渡すやりかたが両方可能になっている場合も結構あったりします。以下のような感じです。
my $obj1 = Hoge->new( #名前付き引数的な渡し方
hoge => 'fuga',
);
my $obj2 = Hoge->new({ #ハッシュリファレンスを渡す渡し方
hoge => 'piyo',
});
package Hoge;
sub new{
my $cls = shift;
#渡されたのが、リスト(名前付き引数)か、ハッシュリファレンスか判別
my $self =
ref $_[0] eq 'HASH' ? shift : {@_};
bless $self, cls;
}
{@_}という書き方が最初慣れないかも知れませんが「配列がリストとして展開されて、それがハッシュリファレンスになる」と考えれば理解可能でしょう。
まとめ
「何でここでは配列なのに、こっちではハッシュなんだ？」とか思ってしまうこともあるかもしれません。
全てリストを介してつながっている
と考えれば話は簡単です。この辺りのリストの扱いを理解してくると「PerlがLISPの影響を受けている」と言われる所以も分かってくるでしょう。
03:54
2010年9月20日
Perlでフィボナッチ数列の高速化とか無名関数の再帰とか
簡単にfibを高速化する方法を読み、おおっと思って、Perlでやってみた。
#!/usr/bin/perl
use strict;
use warnings;
use feature qw/state/;
use Benchmark qw/timethese cmpthese/;
sub _fib_ret2 {
my $n = shift;
if ( $n == 1 ){
(1,1);
}
else {
my ( $aa, $bb ) = _fib_ret2($n-1);
($aa+$bb, $aa);
}
}
sub fib_ret2 {
(_fib_ret2(shift))[0];
}
sub fib_memo {
state @cache;
my $n = shift;
$cache[$n] ||= $n <= 1 ? 1 : fib_memo($n-2) + fib_memo($n-1);
}
sub fib_normal {
my $n = shift;
return 1 if $n <= 1;
return fib_normal($n-2) + fib_normal($n-1);
}
sub fib_no_recv { #まあ、これが一番速いのは分かってるんですよ。
my $n = shift;
return 1 if $n <= 1;
my ( $fib, $prev ) = (1,1);
( $fib, $prev ) = ( $fib+$prev, $fib ) for 2..$n;
$fib;
}
my $fib_arg = 30;
cmpthese timethese 0, {
fib_ret2 => sub { fib_ret2($fib_arg) },
fib_memo => sub { fib_memo($fib_arg) },
fib_normal => sub { fib_normal($fib_arg) },
fib_no_recv => sub { fib_no_recv($fib_arg) },
};
fib_memo: 3 wallclock secs ( 3.19 usr + 0.00 sys = 3.19 CPU) @ 1742548.96/s (n=5551761)
fib_no_recv: 3 wallclock secs ( 3.17 usr + 0.00 sys = 3.17 CPU) @ 66800.76/s (n=211892)
fib_normal: 3 wallclock secs ( 3.61 usr + 0.00 sys = 3.61 CPU) @ 0.55/s (n=2)
fib_ret2: 3 wallclock secs ( 3.20 usr + 0.00 sys = 3.20 CPU) @ 28944.44/s (n=92738)
Rate fib_normal fib_ret2 fib_no_recv fib_memo
fib_normal 0.554/s -- -100% -100% -100%
fib_ret2 28944/s 5224372% -- -57% -98%
fib_no_recv 66801/s 12057437% 131% -- -96%
fib_memo 1742549/s 314529988% 5920% 2509% --
確かに速い。しかし、メモ化するよりかは遅い？いや、再帰なしのパターンよりか速いのはおかしくね？
違ぁう！そりゃそうだ。メモ化したやつは2回目の試行以降は、単なる配列のインデックスアクセスになっているので速いに決まっているのだ。つまり、実装としては正しいが、ベンチマークとしてはフェアじゃない。
てことで、ベンチマークの試行毎にメモの内容が初期化されて欲しい。しかし、stateが初期化された無名関数を返すにしても、無名関数を再帰する方法はPerlにはデフォルトで無いので、ダサいけど外部にメモを持たせるしかないかなぁと。
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw/timethese cmpthese/;
sub _fib_ret2 {
my $n = shift;
if ( $n == 1 ){
(1,1);
}
else {
my ( $aa, $bb ) = _fib_ret2($n-1);
($aa+$bb, $aa);
}
}
sub fib_ret2 {
(_fib_ret2(shift))[0];
}
my @memo;
sub fib_memo2 {
my $n = shift;
$memo[$n] ||= $n <= 1 ? 1 : fib_memo2($n-2) + fib_memo2($n-1);
}
sub fib_no_recv {
my $n = shift;
return 1 if $n <= 1;
my ( $fib, $prev ) = (1,1);
( $fib, $prev ) = ( $fib+$prev, $fib ) for 2..$n;
$fib;
}
my $arg = 50;
cmpthese timethese 0, {
fib_ret2 => sub { fib_ret2($arg) },
fib_memo => sub { @memo=();fib_memo2($arg) },
fib_no_recv => sub { fib_no_recv($arg) },
};
fib_memo: 3 wallclock secs ( 3.22 usr + 0.02 sys = 3.23 CPU) @ 12827.77/s (n=41485)
fib_no_recv: 3 wallclock secs ( 3.14 usr + 0.02 sys = 3.16 CPU) @ 34344.42/s (n=108391)
fib_ret2: 4 wallclock secs ( 3.30 usr + 0.00 sys = 3.30 CPU) @ 17243.33/s (n=56834)
Rate fib_memo fib_ret2 fib_no_recv
fib_memo 12828/s -- -26% -63%
fib_ret2 17243/s 34% -- -50%
fib_no_recv 34344/s 168% 99% --
確かに一回だけの計算だったら、二つ返すほうがメモ化よりも速いことが分かる。
理由を考えてみると、値を二つ返すパターンだと、単に実行コンテキストをスタックに詰んでいって戻ってくるのが一本道だと言うことが分かる。
メモ化のパターンだと関数内で関数が2回呼ばれるので、その分関数の呼び出し回数が指数的に増えていってしまうので、そこがネックになるのでしょう。
なるほど。考えた人すごい。
おまけ
無名関数の再帰が出来なくてスマートに記述できなかったのが悔しかったので、Sub::Recursiveを使って書き直してみた。Sub::Recursiveを使ったのは、「Perlで無名関数再帰のベンチ」で一番速いって書いてあったし、そこにあったベンチマークスクリプトを走らせても圧倒的にSub::Recursiveが速かったので。
#!/usr/bin/perl
use strict;
use warnings;
use feature qw/state/;
use Benchmark qw/timethese cmpthese/;
use Sub::Recursive qw/$REC recursive/;
sub _fib_ret2 {
my $n = shift;
if ( $n == 1 ){
(1,1);
}
else {
my ( $aa, $bb ) = _fib_ret2($n-1);
($aa+$bb, $aa);
}
}
sub fib_ret2 {
(_fib_ret2(shift))[0];
}
sub fib_ret2_lambda{
((recursive {
my $n = shift;
if ( $n == 1 ){
(1,1);
}
else {
my ( $aa, $bb ) = $REC->($n-1);
($aa+$bb, $aa);
}
})->(shift))[0];
}
my @memo;
sub fib_memo2 {
my $n = shift;
$memo[$n] ||= $n <= 1 ? 1 : fib_memo2($n-2) + fib_memo2($n-1);
}
sub fib_memo_lambda {
recursive {
state @cache;
my $n = shift;
$cache[$n] ||= $n <= 1 ? 1 : $REC->($n-2) + $REC->($n-1);
};
}
my $fib_arg = 50;
cmpthese timethese 0, {
fib_ret2 => sub { fib_ret2($fib_arg) },
fib_ret2_lambda => sub { fib_ret2_lambda($fib_arg) },
fib_memo => sub { @memo=();fib_memo2($fib_arg) },
fib_memo_lambda => sub { fib_memo_lambda()->($fib_arg) },
};
fib_memo: 4 wallclock secs ( 3.17 usr + 0.00 sys = 3.17 CPU) @ 13341.11/s (n=42318)
fib_memo_lambda: 3 wallclock secs ( 3.20 usr + 0.00 sys = 3.20 CPU) @ 6907.90/s (n=22126)
fib_ret2: 3 wallclock secs ( 3.22 usr + 0.00 sys = 3.22 CPU) @ 16680.96/s (n=53696)
fib_ret2_lambda: 3 wallclock secs ( 3.25 usr + 0.00 sys = 3.25 CPU) @ 15201.23/s (n=49404)
Rate fib_memo_lambda fib_memo fib_ret2_lambda fib_ret2
fib_memo_lambda 6908/s -- -48% -55% -59%
fib_memo 13341/s 93% -- -12% -20%
fib_ret2_lambda 15201/s 120% 14% -- -9%
fib_ret2 16681/s 141% 25% 10% --
まあ、やっぱ余計なことしないほうが速いに決まってますよね。
23:07
デイリーポータルViewerをバージョンアップ(べつやくれい・林雄司両氏結婚記念ではない)
まずはべつやくれいさん、林雄司さんご入籍おめでとうございます。面白人間同士ご結婚ということでどんなお子さんが産まれるか今から楽しみですね！
で、その昔、デイリーポータルZを作者別に見たいと思って、デイリーポータルViewerというものをその昔作りっぱなしで放置しておりました。余りにもひどい酷い作りだったので直したいと常々思っていたのですが、この度改良を加えました。見た目は全然変わっていませんが、実質書き直しになりました。
やったことは以下。
- ワンファイル内でprint文直書き(!!!)だったのでロジックとviewを分離。CGIフレームワークHyCycjkを適用。
- データファイルをテキストファイルからSQLiteに。排他制御周りを見直し。
- RSSのパースを正規表現(!!!)からXML::FeedPPに変更
- クローリング頻度を見直し
本当はURLも変えたかったのですが、長年このURLで運用してしまったので、そこは変えないことにしました。daily2.cgiというファイルはもうありませんが、mod_rewriteで無理やり同じURLにしています。
HyCycjkはYacafiをベースにしてMentaにインスパイアされた拙作のCGI Application Frameworkです。Yacafiよりかは高機能、Mentaよりかは低機能だけどワンファイル配置するだけで動く。といった辺りを狙っています。多分mod_perlでも動きます。残念ながらPSGI対応はしていません。
しかし、元のプログラムは色々酷くて、よく動いていたなぁと逆の意味で関心してしまうというか。2年半前の自分はここまで酷かったのかとか。
そもそも、立ち上げのときも、バックナンバーのページからリンク先を辿ってデータを取得するようなクローラを書いたのですけど、勿論1アクセス毎にウェイトをかけるなんてこともしてなかったので、逮捕されなくてよかったなぁ(笑)、とか思ったり。
22:10