C++向け簡易コマンドラインパーザ cmdline

を作りました。

http://github.com/tanakh/cmdline

何か

コマンドライン引き数の解析を助けるライブラリです。同じ目的のライブラリに、Cの標準関数であるgetoptやgoogleのgflagsなどがありますが、cmdlineは適当に使えてそこそこ便利というのを目指しています。getoptは使いにくいし、usageも自分で書く必要がある。gflagsはライブラリをインストールしたり、リンクしたりちょっと大掛かり。cmdlineは、1ヘッダファイルで、コピーするだけで使えて、修正BSDライセンスで公開しているので、自由にプログラムに取り込んでいただけます。

コードサンプル

#include "cmdline.h"

int main(int argc, char *argv[])
{
  cmdline::parser p;
  p.add("hoge", 'h', "hoge flag with no value");
  p.add<int>("moge", 'm', "moge flag with int value", false, 123);
  p.add("help", 0, "print help");
  // add other flags...

  if (!p.parse(argc, argv)||p.exist("help")){
    std::cout<<p.error_full()<<p.usage();
    return 0;
  }

  // main code...

  if (p.exist("hoge"))
     std::cout<<"there is hoge flag"<<std::endl;

  std::cout<<"moge value: "<<p.get<int>("moge")<<std::endl;

  // ...
}

上プログラムのように、cmdline::parserのオブジェクトを生成してやり、parser::add()によりフラグを追加し、parser::parse()を呼び出します。実行例です。

> ./a.out --help
usage: ./a.out [options] ...
options:
  -h, --hoge    hoge flag with no value
  -m, --moge    moge flag with int value (int [=123])
      --help    print help

> ./a.out --moge=777 -h
there is hoge flag
moge value: 777

>  ./a.out --moge=huga
option value is invalid: --moge=huga
usage: ./a.out [options] ...
options:
  -h, --hoge    hoge flag with no value
  -m, --moge    moge flag with int value (int [=123])
      --help    print help

マニュアル

parser::add(const string &name, char short_name, const string &description)

値を持たないフラグを定義します。フルネーム、短縮名、フラグの説明、の順です。短縮名に0を指定すると、短縮名なしになります。

template void parser::add(const std::string &name, char short_name=0, const std::string &desc="", bool need=true, const T def=T())

値を持つフラグを定義します。必須なのは、フルネーム、短縮名、フラグの説明(と、テンプレートパラメータである型)です。オプショナルな引き数として、そのフラグが必須か(必須ならば、コマンドラインで与えられないときにparseがエラーになります)と、フラグ値が与えられなかったときのデフォルトの値があります。短縮名を0にすると短縮名なしになるのは上と同じです。

template void parser::add(const std::string &name, char short_name=0, const std::string &desc="", bool need=true, const T def=T(), F reader=F())

上と同じく、値を持つフラグを定義します。値に対するカスタムreaderをセットできます。上のメソッドでは、デフォルトのreaderとして、lexical_castが使われます。stringから型Tへの任意の関数もしくは関数オブジェクトが渡せます。この関数が例外を投げる場合、失敗とみなされ、parser::parse()は失敗になります。

bool parser::parse(int argc, char *argv[])

コマンドライン引き数を解析します。mainの引き数をそのまま渡します。失敗したらfalse、成功したらtrueが返ります。失敗した場合、parser::error()で具体的なエラーメッセージが取得できます。

bool parser::exist(const string &name)

コマンドライン引き数に与えられたフラグが存在していたかを返します。parser::parse()した後に使います。

template const T &parser::get(const std::string &name)

与えられたフラグの値を返します。parser::parse()した後に使います。フラグ名が不正(addされていない)、もしくは型がaddしたときとかみ合わない場合、cmdline::cmdline_error例外が投げられます。

const std::vector &parser::rest()

コマンドライン引き数のうち、コマンドラインオプションと認識されなかった引き数が格納される配列が返されます。オプションのほかにファイル名などを引き数として取りたい場合などに使えます。

std::string parser::error()

一つ目のエラーメッセージを返します。

std::string parser::error_full()

すべてのエラーメッセージを返します。

std::string parser::usage()

usageを返します。

void parser::footer(const std::string &f)

usageが返す文字列のusageの行の後ろに文字列を追加できます。

void parser::set_progam_name(const std::string &name)

usageのusageの行に表示されるプログラム名をセットできます。この関数でセットしない場合、プログラム名としてはargv[0]が使われます。

カスタムreader

デフォルトでは、フラグの値を読むのに、lexical_cast(のような自前のもの)が使われます。このため、addなどとすると、コマンドライン引き数が10進整数として読まれ、不正な値ならばparseが失敗するなどの動作になります。この処理はオプションで変更することができ、lexical_castの代わりに任意の関数オブジェクトを渡すことができます。なので、16進で読ませることや、特定のレンジにある値、のような指定もできます。cmdlineでは、簡便のために、レンジ付き値、択一などのreaderがあらかじめ用意されています。デフォルトの動作は、cmdline::default_readerとして参照できます。

  p.add<int>("hoge", 'h', "int value (100 - 999)", cmdline::range(100, 999));
  p.add<string>("moge", 'm', "one of abd, def, ghi", cmdline::oneof<string>("abc", "def", "ghi"));

関数合成的な演算子を用意して、ごりごりと合成できるほうがいいかなとも思いましたが、独自の演算子を定義して、それを覚えてもらうのもよくないかなと思ってやめました。とにかく覚えること少なくて、ぬるく使えるように。

ICFP2009 ソースコード

ICFP飲み会でソースコードを公開するといいよ、みたいなことを
しきりに言われて、そうか、ソースコードを公開するべきなんだな、って
その時はとてもそういう気分になっていたのですが、すっかり忘れていました。
この度思い出したので、忘れないうちにアップロードしておくことにします。
ソースコードはHaskell/C++で書かれていて、基本的にはHaskellです。

http://fxp.infoseek.ne.jp/tmp/icfp2009.tar.gz

仮想マシンのコンパイラと、シミュレーションの重い部分がC++です。
ここ最近、私のコードにはコメントは書かれなくなったので、
コメントはありません。あしからず。
なので、本人も詳しいことは覚えておりません。
方針などの概要は前回のスライドを参照してください。

ICFP Programming Contest 2009

すっかり文章を書くのを忘れてたのをICFPが終わって思い出したので、社内向けに作ったスライドを張ってお茶を濁す。書き換えたい部分もあるが面倒なのでオリジナルまま。

Icfp2009

View more presentations from tanakh.

動画。手振れがひどい。なかなか辛い回り方をしているなあ。

[Scala]競技プログラミング in Scala

Scalaで競技プログラミングを行う際に気をつけることの列挙。

なぜScalaなのか？

• 速い
• 静的型付
• 字面がC++よりましなのでC++よりは速く書けるであろうという期待
• 同じ理由でJavaよりは速く書けるであろうという期待
• OCamlよりも基本的なライブラリが充実しているので速く書けるであろうという期待
• Haskelは配列を弄繰り回すような場合にコードが冗長になる傾向があるのでそういう場合に比較して速く書けるであろうという期待

プログラム全体の構造

Scalaプログラムの実行方法には二通りある。

• scalaコマンドによる直接実行
• scalac(fsc)コマンドで.classファイルを生成 → scalaコマンドで.classファイルを指定して実行

注意すべきは、どちらの方法をとるかで書くべきプログラムが変わることである。scalaコマンドで直接実行する場合、トップレベルに書かれた式が実行される。scalacコマンドでコンパイルする場合、トップレベルには定義しかかけない。つまり、クラスを作らなければならない。コードは次のようになる。

object A extends Application{
  ... hoge hoge
}

直接実行する場合、クラスを定義しただけでは実行されないので、これとは逆にクラスを定義してはいけない。

書くべきコードはコンパイルする場合のほうが多い。また、実行させるのに必要なコマンドも長くなる(さらに悪いことに、コンパイルした場合、ラムダ式に応じて匿名の.classファイルが大量に生成される傾向にある)。あえてコンパイルする理由があるとすれば実行速度だろう。しかし、私の見たところによると、コンパイルして実行速度が速くなるということはなかった。直接実行する場合も内部的にはきっちりコンパイルして実行しているようだ(たぶんそうなので、直接実行する場合にもscalacする場合と同じぐらい起動に時間がかかる)。このことを鑑みるに、競技プログラミングであえてscalacを行う理由はない。プログラムはトップレベルに書き、scalaコマンドで実行するのが良い。

入出力

典型的な競技プログラミングの課題は標準入力からテストセットを入力し、結果を標準出力に書き出す必要がある。Scalaで入力をするにはいくつかの方法がある。

• java.io.以下のBufferedReaderなどを使う
• scala.io.Sourceを使う
• java.util.Scannerを使う

一つ目の方法は旧来のJavaで一般的な方法だが、冗長に過ぎる。scala.io.Sourceはインターフェースが使いにくい。Java1.5以上であればScannerを使うのがよろしい。

出力はSystem.outを使う方法と、scalaの標準ライブラリを使う方法がある。前者は、単にSystem.out.とタイプするのが面倒なこと(これはimportすればよいのだが)に加え、JavaのクラスであるObjectを引数をとる関数にはscalaの暗黙の型変換がうまく働かないという問題がある。

System.out.printf("%d\n", 123) // NG
System.out.printf("%d\n", int2Integer(123)) // OK

この理由から、scala組み込みのを使うべきである。

printf("%d\n", 123) // OK

なお、scalaのprint/printlnには任意個の引き数が渡せて、その場合にはタプルの出力と同じになるので、デバッグに便利である。

データ構造

• 配列

newでの生成は初期値が指定できない上に要素の型を指定しなくてはならず大変使いにくい。コンパニオンオブジェクトのfromFunctionが便利。

val aa = Array(1, 2, 3) // リテラル
val bb = Array.fromFunction(i=>...)(n) // 添え字で初期化できる
val cc = Array.fromFunction(_=> -1)(n) // 初期値が決まっているなら
val dd = Array.make(n, -1) // これでもいい
val ee = Array.fromFunction((i, j)=>...)(n, m) // 多次元配列も
val ff = Array.make(n, Array.make(m, -1)) // これはだめ

• リスト

普通のリスト。

• Map

• • scala.collection.Map
  • scala.collection.SortedMap

の二つのtraitがある。前者は順序を保障しない。後者は保障する。実装しているクラスは次のとおり

• • scala.collection.immutable.HashMap extends Map
  • scala.collection.immutable.ListMap extends Map
  • scala.collection.immutable.TreeMap extends SortedMap
  • scala.collection.immutable.TreeHashMap extends Map
  • scala.collection.immutable.UnbalancedTreeMap extends Map
  • scala.collection.immutable.IntMap extends Map
  • scala.collection.immutable.LongMap extends Map

• • scala.collection.mutable.HashMap extends Map
  • scala.collection.mutable.LinkedHashMap extends Map
  • scala.collection.mutable.OpenHashMap extends Map

などがある。たくさんあるが、

• • immutable.ListMapと、immutable.UnbalancedTreeMapは存在価値が不明
  • immutable.TreeHashMapはHashMapでいい
  • mutable.LinkedHashMapとOpenHashMapはmutable.HashMapでいい

おおよそ次のような基準で選ぶと良い。

• • 順序付ならimmutable.TreeMap一択
  • キーが整数かつ非負で順序つきならimmutable.IntMap or LongMap
    • これらはunsignedに順序が付くようなので、非負の数しか入れないならSortedMapとして使える
    • HashMapよりは遅いがTreeMapよりはだいぶ速い
  • パフォーマンスが気になるならmutable.HashMap
  • それ以外ならimmutable.HashMap
    • (実際のところimmutable.HashMapは十分速い)

なお、scala.collection.immutable.Mapとmutable.Mapコンパニオンオブジェクトはそれぞれimmutable.HashMapとmutable.HashMapを生成する。

• Set

• • scala.collection.Set
  • scala.collection.SortedSet

mapと同様に順序付きとそうでないものの二つのtraitがある。

• • scala.collection.immutable.HashSet extends Set
  • scala.collection.immutable.ListSet extends Set
  • scala.collection.immutable.TreeSet extends SortedSet

• • scala.collection.mutable.HashSet extends Set
  • scala.collection.mutable.LinkedHashSet extends Set

なぜかmapよりもバリエーションが少ない。IntMap相当のものがないことを除けば、選定基準はMapと同じでいいだろう。

• MultiMap

基本的にMap[A, Set[B] ]で扱う。便利のためにそのようなTraitがscala.collection.mutable.MultiMapに用意されている(なぜかmutableだけ)。

val x = new HashMap[Int, Set[Int] ] with MultiMap[Int, Int] // こうすると
x.add(1, 2)
x.add(1, 3)
x.entryExists(1, (_ = 2))
x.remove(1, 2) // こういうメソッドが使える

当然ながらimmutableにはくっつけられない。

キーも値も重複するものを許すものは用意されていない。

• MultiSet

特に用意されているものはない。Map[A, Int] などで出現回数を数えるぐらいだろうか。

• PriorityQueue

scala.collection.mutableにある。比較関数は変えられない。

小技

• パラメータを複数個読み込む必要がある場合。

val sc = new java.util.Scanner(System.in)
val a, b, c = sc.nextInt() // a, b, c の順に整数が三つ読み込まれる

• 整数の配列を読み込む場合

val arr = Array.fromFunction(_=>sc.readInt())(n) // arr(0) .. arr(n-1) に順に整数が読み込まれる
val mat = Array.fromFunction((_,_)=>sc.readInt())(n, m) // arr(0)(0) .. arr(0)(m-1) .. arr(n-1)(m-1) に順に整数が読み込まれる

• 文字列を空白区切りで分割

val words = sc.nextLine() split " +"

• ジェネレータは一回しか評価されない

for (caseno <- 1 to sc.nextInt()){
  ...
  printf("Case #%d: ...", caseno, ...)
}

• パーザコンビネータが標準でついてるので、使えるようにしておくべし

気をつけること

• 型推論

型推論が弱いので、要所要所で型を書いてやる必要がある。書く必要がある場所の判定にはScalaの型推論アルゴリズムを熟知している必要があるので、Programming in Scalaには、コンパイラに怒られたらその都度注釈を入れよ、の様に書いてあった。しかし、いちいちそれでは時間をロスするので、注釈が必ず必要な簡単な場所は覚えておく。

• • 関数の引き数
  • 明示的にreturnしている関数の返り値の型
  • 再帰呼び出ししている関数の返り値の型

• for式の型

for式でyieldすると、最初のジェネレータと同じ型のコレクションが返る。ListならList、ArrayならArrayであるが、SetだとSetになって、要素がつぶれてしまうことがあるので注意。

競技プログラミング in Scala

素人なのであてにはならないと思いますが。

UTPC2009

今年も参加しました。
http://www.utpc.jp/2009/

結果は7問で6位という残念なものでしたが、
面白い問題がいろいろあって楽しかったです。
一つの問題にはまって他の問題が全然考えられなかったのが悔やまれます。

当日の様子を書いておきます。

A

問題がなかなか開かず焦る。
とりあえず普通に簡単な問題だったので通す。

B

DP書いて通す。
12問中の2問目にしてはめんどい。

C

2人の人が9枚ずつ与えられたカードを一枚ずつ出して云々という問題。
はまった。
1ターンずつ適当にカードを出し合ってビットDPすれば
(2^9)^2*9^2ぐらいで終わるんで、それで組んだら手元で0.5秒ぐらいかかるプログラムができた。
サブミットするとTLE。どうしたもんかなあと。

E

そうこうしているうちに早くもEが解かれてしまったので、Eに変更。
ぱっと見分からなかったけど、こんなに早く解かれるなら簡単に違いないという推理から、
これはどうやっても同じなのではないかと予想。
足し算したときの数の総和は変わらないか10減るか。
なので、最後に残る一桁の数は常に同じ。
10減る回数も決まっているので、結局どうやっても足し算できる回数は同じ。
適当に書いて適当に通す。

D

Dが解かれたので、Dに進む。
完全に後手後手になってきてて、もう今日は駄目かなあと思い始める。
呼んでみると実装するだけで仕様も単純だったので
さっくり通す。

G

今度はGが解かれたのでGに進む。
よく分からなかったけど、TLEにならない程度回してWAもらったら後で考える、
ぐらいで実装を始める。
普通にAccept。
あとで考えてみたが、ループするケースは二者間往復しかなさそうなので、
これは正しかった。

C

ほかに解かれてる問題がなかったので、Cに戻ってくる。
もう一回一から考え直したら、これは片方出す順固定して
もう片方の出す順番を全部試すだけじゃないかとやっとのことで気づく。
こんなことに気付かなかったなんて、悔しくて仕方がなかった。
でも、一回解法を思いついてしまうと、それに思考が縛られてしまうのは
仕方がないのかもしれないと思った。
そうして、ようやくAccept。

F

とりあえず残り全部読むかと思って、読む。
Fがよさそうな感じがしたので、実装開始。
サイズが50000なのが心配だったが、O(nm)のアルゴリズムで、
bitsetでやれば間に合うんじゃないかと思った。
完成したプログラムはワーストケースで手元で0.7秒ぐらいだった。
Cのこともあったので、どうかなと思って出したが、
結果はTLEであった。

I

二時間ぐらいFの高速化をやってて、さすがにまずいんじゃないかと思ったので、
スコアを見てみるとIがそこそこ解かれてるっぽかったので、解くことにした。
猫が自力で行けるときは0。
そうでないときは人が最小限の扉を開けてやらなければならない。
人が最初にいる場所と、猫が動ける範囲と、ゴールに猫が自力でたどり着ける範囲の三つを
結ぶ最小ルートがどうなるのかなあと考えていたら、最適な時はY字になるはずと気付いて、
それが分かれば後はすぐであった。
と思ったが、自力で行けるケースを書くのを忘れていて1回WAを食らった。
直してサブミットしようとしたらコードを二重に張ってCEをもらった。
三度目の正直でAC。

F

残り時間1時間ぐらいで、Fをやるかほかにあと1問別のやつを解くかで、
結局Fに戻ってきた。
Hはサイズが大きすぎて厳しそうだったのでパス。
Jは幾何よく分からないのでパス。
Kは式をちょっと書いてみたら泥沼になったのでパス。
Lはなんかうまい方法があると思って少し考えたけど全然わからなかったのでパス。

一時オブジェクトを作らないようにしたり、
bitsetをやめてsetにして枝刈りを入れてみたり、
setをunordered_setに変えてみたりいろいろやったがダメ。
unordered_setに変えたときは結構テストケースが進んでいるような手ごたえがあったが
結局は通らず。
状態数が爆発するケースがあることが分かったので、それを突っ込んでみたら
setでは全然終わらず。
諦めてbitsetを高速化するが、手元で0.4秒ぐらいまでになったものの
相変わらずTLE。
もうだめだ、というところで終了。

終了後

twitterでF後ろからやったら一瞬と聞いて相当ショックを受ける。
なんで気付かなかったんだ。
ちょっとこれはしばらく立ち直れないかもしれない。
よくよくも考えると、こんなにたくさんの人が
こんなに激しいチューニングをして通しているわけがないじゃないか…。

勝負としてはC手間取った時点でスコアでは勝てなくなってたので、
もうこれは駄目だった。仕方がない。

参加しての感想としては、
参加者の層が、ちょっと前では考えられないほど
厚くなってきてるなあと思った。
7問以上正解者が16人もいるのがそれを示している。
現役が強いなあという印象も受けた。
今年の世界大会は期待していいかな。

最後に主催者の皆様、このような楽しげなイベントをありがとうございました。
また来年があればよろしくお願いします。

ACM-ICPC Japan Domestic Warm Up I

http://rose.u-aizu.ac.jp/onlinejudge/jdwu1.html
http://rose.u-aizu.ac.jp/onlinejudge/ContestRankList.jsp?contestID=JDWU2009I

ICPC参加資格も何もないですけど、
リハビリのために参加しました。
最近老化がひどいので…。

A

二つの列を一緒に読み込んで、0加えて、ソートして、前からスキャン、
が一番速そうだったので、そう実装。

B

3次元配列をつくって、適当に塗っていく実装。

C

シンプルなparser。
10分でかけるparserとかいう記事を公開しながら
20分かかったのは、多分老化のせい。

D

20個しか科目がないので、2^20とおりビットパターン生成して
条件満たしてるかチェックで書いたのだけど、
1秒の制限時間を5秒ぐらいかかっている。
ちょいちょい変えながら再送するが、
ちっとも速くならない。
TLE厳しすぎる…。
問題チェンジ

F

Eが図形でFが探索なのを見て、
どっちかというとFかなと思う。

起点からのばして探索する方針で適当に書いて
サブミットしたが、全然間に合わない。
これもTLEを量産した揚句、いったん中断。

D

Dに戻る。
枝刈りが入らないのがいけないんじゃないかなあ、というので、
DFSで書き直し。
普通にとおる。うーむ…。

F

こっちも枝刈りを入れることにする。
正のマスについて、
負のマスにつなぐことができないのがあれば、だめ。
負のマスについて、隣接する正のマスの合計が超えてなければだめ。
この二つを入れたら、0.01秒とかで通った。
探索は博打みたいなところがあるなあ…。

E

のこり25分ぐらいだったけど、一応書いた。
座標と向きをノードとしてダイクストラみたいなので、
一応書き終わってサブミットしたが、
バグバグだった模様。