miauのブログ

はてなダイアリー「miauの避難所」をはてなブログに移行しました

Google Code Jam 2009 の思い出 (2)

Algorithm

ということで続きです。Perl や Windows での Tips や、その他情報源です。

Perl スクリプトのひな形

Round2 のタイミングでようやくひな形を準備するようになったんですけど、だいたいこんな感じで落ち着きました。

use strict;
use warnings;
use Data::Dumper;
use Data::Dump qw/dump/;

$| = 1;

my @data = <DATA>;
my $case_count = shift @data;

for (my $case = 1; $case <= $case_count; $case++) {
	print "Case #$case: \n";

	my ($h, $w) = split(' ', shift @data);
}
__DATA__

__DATA__ セグメントに example の問題文を貼って、SciTE で少しずつ実装→実行を繰り返す形。
で、example が通ったら のところを に置き換えて、

perl round1A.pl < large.in > large.out

みたいにして実行してました。

Perl の便利そうなライブラリ

ちゃんと使い込んでないものも含めてメモ。

print デバッグ支援
  • Data::Dumper、Data::Dump、Dumpvalue モジュールあたり。
    • それぞれ特徴があるので適当に使い分ける。
      • 本当はオプションでもっと細かく書式変更できるけど、ちゃんと把握してないので・・・
    • Perl - CakeWiki によると、XXX のほうがモダンらしい。確かに受け取った値をそのまま返したり、ファイル名＆行数を表示してくれるのは便利かも。
  DB<1> $a = {i => 1, s => 'abc', a => [[1, 2], [3, 4]]};

  DB<2> use Data::Dumper; print Dumper($a)
$VAR1 = {
          'a' => [
                   [
                     1,
                     2
                   ],
                   [
                     3,
                     4
                   ]
                 ],
          's' => 'abc',
          'i' => 1
        };

  DB<3> use Data::Dump q/dump/; print dump($a)
{ a => [[1, 2], [3, 4]], i => 1, "s" => "abc" }

  DB<4> use Dumpvalue; $d = Dumpvalue->new(); $d->dumpValue($a);
'a' => ARRAY(0x1d45f28)
   0  ARRAY(0x182ec48)
      0  1
      1  2
   1  ARRAY(0x1d45ef8)
      0  3
      1  4
'i' => 1
's' => 'abc'

  DB<5> use XXX; XXX $a;
---
a:
  -
    - 1
    - 2
  -
    - 3
    - 4
i: 1
s: abc
...
  at (eval 19)[C:/Perl/lib/perl5db.pl:638] line 2
配列、ハッシュ操作
  • List::Util
    • first、max、maxstr、min、minstr、reduce、shuffle、sum あたりが使える。
  • Perl6::Junction
    • all、any、none、one あたりが使える。
    • 「if (any(@grant) eq 'su') { ... }」みたいに書ける。
  • Tie::IxHash
    • ハッシュの要素を追加順で取り出せるようにする。
  • Tie::RefHash
    • ハッシュキーにリファレンスを使えるようにする。
  • Storable
    • dclone() でデータの deep copy ができる。
  • Set::CrossProduct
    • 直積を出す。
  • Math::Combinatorics
    • 順列、組合せ、重複組合せ等の処理。

ちなみに最後の 2 つは

から。ただ、こういうモジュールを使っても Small を力技で解ける程度だと思います。Large だと計算量が膨大になるので、アルゴリズムを見直す必要があるでしょう。

その他挙動の変更
  • bignum プラグマ
    • 標準より大きい値／有効数字を扱う。
  • integer プラグマ
    • 整数として計算が行われるので高速化できる。詳細は次回書くかも。
  • Memoize
    • memoize（関数の実行結果をキャッシュすること）ができる。
    • ただし内部で文字列処理が走るのでループ回数が多いような場合には向かない。

Perl のその他 tips

  • 入力値をうまいこと分割するには split ' ' （※間に半角スペースあり）を使うといい。
    • split / / （※間に半角スペースあり）とは意味が違って、改行なんかもうまく扱ってくれる。
    • 一方文字単位に分割するのは split // （※間に文字なし）と。
  • 行儀よく my を使わずに our とか使ったほうがいいことも。
    • 「処理を切り出したいけどスコープの変数を使いたい」みたいな場合、当初
local *inner = sub { return $x * 19 };

みたいにクロージャを使ってたけど、our で変数定義したほうが遙かに楽だったとかあった。

  • 全組み合わせのループっぽいノウハウはためておいたほうがいいかも
    • Ruby の yield っぽいのができればいいんだけど。Perl できたっけ？
  • ひさびさに Perl 使うとよく間違えるんだけど、ハッシュキーの有無をチェックするのは defined じゃなくて exists と。

Perl 不満点

  • 文字列処理でいちいち substr とか面倒。正規表現で書きやすい処理ならいいけど。
  • 配列操作も splice とか面倒。Python や Ruby みたいに配列のスライスに要素数違う配列を代入できたら楽なんだけど。
  • 多次元配列とか使うことが多くなるけど、こうなるとデリファレンスが面倒くさい。この点は PHP のほうがよほど楽。
  • Python みたいに foreach に else つなげたくなることもしばしば
  • yield 使いたい

とかいろいろ。やっぱり Perl5 は Python や Ruby に比べると欠点が目立つ。誰かと共有するコードは Perl5 で書いておいたほうがいいだろうけど、自分しか使わないコードについては Perl6 にさっさと移行したいな。

Windows での Tips

時間計測

Small で実行時間の目安をつけて Large で実行、というようなことをやるといいんですが、*nix の time コマンドみたいなことを Windows でやるには、Resource Kit Tools に含まれる timeit というものを使えばいいそうです。

timeitコマンドでアプリケーションの実行時間を測定する − ＠IT

>timeit perl -e "for ($i = 0; $i < 10_000_000; $i++) { $n++ } print $n;"
10000000
Version Number:   Windows NT 6.0 (Build 6002)
Exit Time:        2:31 am, Sunday, May 16 2010
Elapsed Time:     0:00:02.909
Process Time:     0:00:02.386
System Calls:     104790
Context Switches: 46356
Page Faults:      1638
Bytes Read:       15522
Bytes Written:    10820
Bytes Other:      97928

こんな感じで時間が計測できます。もし .pl を perl に関連付けている場合でも、ちゃんと実行ファイルを指定してやらないと計測できないので注意。

ウィンドウを最前面に固定

普段からログの監視なんかでも使いますが。計算に時間がかかる場合は HiWindowOP でウィンドウを最前面に固定して次の問題にとりかかったりしてました。このソフトは常駐しない（実行したタイミングでアクティブになっているウィンドウに対して操作を行う）だから、常駐ソフトが多くて嫌な感じのひとにオススメ。

参考になりそうなサイト

      • -

といったところで Tips は終わり。次回は一番書きたかったパフォーマンス周りの話・・・・にしたいと思うんですが、断片的なメモしかないのでお蔵入りする可能性も・・・。