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

Perlメモをメモ

テックウェブという会社の取締役さんのPerlに関するメモ書き。
Perlメモ

僕の癖が強いものもありますがご容赦を。

たしかにww トリッキーで楽しいコードがいっぱいです。


いくつか紹介

リストシャッフル

sub Shuffle{
    BEGIN{srand}
    my @OUT;
    push @OUT,splice @_,rand @_,1 while @_;
    return \@OUT;}

自分もそうですがCから来た人は配列要素の追加削除を繰り返すプログラムは敬遠してしまいがち。思わず自分のいつも使う「乱数くっつけてソート」アルゴリズムと簡易速度比較。

[mikeda@cent ~]$ time perl -e '@out = map $$_[1], sort {$$a[0]<=>$$b[0]} map [rand,$_],0..100_000'

real 0m1.611s
user 0m1.566s
sys 0m0.044s
[mikeda@cent ~]$ time perl -e '@_=1..100_000;push @out,splice @_,rand @_,1 while @_'

real 0m1.816s
user 0m1.800s
sys 0m0.015s

速度はそんな変わらず、メモリ効率は(たぶん)だいぶ負けてることが判明。

ハッシュのキーと値を交換する(値が重複してはならない)

%hashB = reverse %hashA;

やったことなかった。反射的に考えたコードはこう。上のより効率悪いのは明らか。

@hashB{values %hashA} = keys %hashA;

配列の一つごとの数値フィールドを指定しそれを比較してソートした配列を返す

sub Fsort{
    my $spritkey=shift;
    my $field=shift;
    my @in=@_;
    my @out;
    @out=map{$_->[0]}sort{$a->[1]<=>$b->[1]}
    map{[$_,(split /$spritkey/)[$field]]}@in;
    return \@out;} 

これはまぁ定番と言えるのかな。ナニ法って言うんだったか。
例えばこういう名前と年齢と好物の並んだCSVファイルに対して、

ミケ,2,煮干し
タマ,4,肉
トラ,3,カリカ

年齢でソートするときなんかに使う。

open CAT,"<cat.csv";
chomp(@cats = <CAT>);
@sorted_cats = @{&Fsort(',', 1, @cats)};
print map "$_\n", @sorted_cats;

単純にこうやったのではソートの際、要素比較のたびに高コストのsplitが呼ばれる。

sort {split /$splitkey/, $a <=> split /$splitkey/, $b} @in

sortの比較関数は極力軽くすること。
ついでに言えば要素比較のたびに呼ばれることを意識すること。
いちばん上の方で書いたこの配列シャッフルアルゴリズム

@shuffled = map $$_[1], sort {$$a[0]<=>$$b[0]} map [rand,$_],0..10;

乱数くっつけてソートといってもこんな比較関数を書くとソートアルゴリズムは混乱してしまうだろう。ある値に紐づけられたソート用の値が毎回変わってしまうのだから。

@shuffled = sort {rand() <=> rand()} 0..10;

数字に3桁ごとのカンマを入れちゃう

sub keta{
    my $yen=shift;
    1 while $yen =~ s/(.*\d)(\d\d\d)/$1,$2/g;
    return \$yen;
    }

1 whileってなんだかんだいって使ったことないなぁ。
(これってgオプションはいらないような)

ファイルからランダムに一行出す

open(FILE,"hoge.txt");
srand;
rand($.) < 1 && ($line = $_) while <FILE>; 

C言語なんかでサイズのわからないリストからランダムに要素を取り出すアルゴリズムですね。
お題を読んでパッと思いついたのはこう。

@a=<FILE>;
$line = @a[rand @a];

99.9%はこれでいいだろう。ただ読み込むファイルが非常に大きい時はどうするか。
全部で何行かがわからなければ発生させる乱数の範囲がわからない。じゃあこうか。

$cnt++ while <FILE>;
seek FILE,0,0;
$r = 1 + int rand $cnt;
$line = <FILE> while $r--;

いやいやその非常に大きなファイルを2回読み込むなんて・・・
というところでこの紹介されてるアルゴリズム。読み込みは1行ずつ、1回。
ある行まで読み込んだときにその行数分の1の確率で$lineにその行の値をセットする。
ちゃんと均等な確率で出現するのか1から6までで計算してみる。
1番簡単なのは6だ。最後の1回、1/6を引くかどうか。5は5行目で5(1/5)引いて6行目で6以外(5/6)を引いたとき。そして・・・

6 => 1/6
5 => 1/5 * 5/6 = 1/6
4 => 1/4 * 4/5 * 5/6 = 1/6
3 => 1/3 * 3/4 * 4/5 * 5/6 = 1/6
2 => 1/2 * 2/3 * 3/4 * 4/5 * 5/6 = 1/6
1 => 1/1 * 1/2 * 2/3 * 3/4 * 4/5 * 5/6 = 1/6
(序算にカッコつけるの省略)

かっこよすぎ!