D言語でダイクストラ法を実装してみた。（プログラミングコンテスト仕様）
アルゴリズムの勉強にどうせなら新しい言語を使おうと思って D 言語を見つけたので、試しに手元のダイクストラ法の実装(c++)を移植してみた。
- DMD v2.060 だとコンパイルできないので AtCoder / AOJ 等で verify できんかった...orz(2015/5/31現在)。まあ多分ちゃんと動くはず。(本当はSingle Source Shortest Path | Aizu Online Judgeを通したかった。)
- c++11 は auto とか lambda とかあるんでヒャッホーと思っていた一方で multi dimentional vector の resize/fill 関数を template で実装 - shifth’s blog みたいに多重配列の初期化方法が面倒だったり、template の分岐が面倒だったっりと痒いところに手が届かなかった。(あと file util がないとか string に split/strip がないとか色々...)D 言語にはそういう痒いところに手が届くものが全部揃っている印象。
- D 言語のよいと思ったこと(ちょっと触ってみた感じの感想)
- 言語仕様が綺麗。今まで触った言語のうち一番コードが綺麗に書けると思った。
- UFCS のサポート。ruby のようなメソッドチェーンが書ける。(遅延評価っぽいので実行速度効率と両立できてそう。たぶん。)
- unittest を標準サポートしていてどこにでも書けること。今書いているコードを汚すことなく、新しい関数や言語仕様を簡単にテストできる。ruby でいうならあのメソッドってどう動作するっけ？というときに irb を起動して確かめるところを D 言語では unittestt に書いて簡単に確かめられた感じ。実装していると気づいたらテストが増えている感じ。
- import あること。関数内で import できるので無駄な依存関係を取り除ける(気がしている)。
- range のサポート。boost c++ oven range とかカッコイイな c++ の標準機能に入んないかなーとか思っていたが、D 言語にはすでに(それっぽいのが)入っていた。
- ライブラリが充実(文字列操作・file util などなど)
- template の分岐が c++ より書きやすい。
- とにかく標準で色々サポートしているのがよい。他の言語でも boost を入れたらよいとか rspec を入れたら良いとかあるんだけど、複数のマシンでソースを共有して趣味のコーディングをする人なので言語が標準色々サポートしているのはかなりうれしかったりする。
- D 言語にあったらいいなと思ったこと。(ちょっとしか触ってないけど)
- priority_queue/set をサポート。(BinaryHeap, RedBlackTree で同じことできるけど標準でサポートしてほしい。コードが読みやすくなるので。)
- std::tie 関数。自分で alias を用意するでなくて標準でいれて(サポートして)ほしい。もしくは a,b,c = tuple みたいな多重代入。
- tempfile() の返す file に name を入れてほしい。
- 最新仕様ではコンパイルできないのでしばらくはプログラミングコンテストでは使えないなかなー残念。趣味のコーディングでは使うと思う。
- D 言語を触るとかいって class すらかかいてねぇや...。
以下コード
// DMD32 D Compiler v2.067.1 import std.typecons; import std.typetuple; const inf = (1<<30); alias Edge = Tuple!(int,"to", int ,"cost"); alias tie = TypeTuple; int[] dijkstra(in Edge[][] tree, int start) { import std.container; import std.algorithm; alias PriorityQueue = BinaryHeap; int V = tree.length; auto dist = new int[V]; fill(dist, inf); // priority_queue auto queue = new PriorityQueue!(Array!Edge, "a.cost>=b.cost")(); dist[start] = 0; queue.insert(Edge(start,0)); while (!queue.empty()) { int v; int cost; tie!(v,cost) = queue.front(); queue.popFront(); // another shorter path was already found, skip if (dist[v] < cost) continue; foreach(const ref Edge e; tree[v]) { if (dist[v] + e.cost < dist[e.to]) { dist[e.to] = dist[v] + e.cost; // found new shorter path, // push to queue for re-calculate path queue.insert(Edge(e.to, dist[e.to])); } } } return dist; } // // 一行をよみこんで引数に格納する。 // token の数と引数が合わないとエラーにする。 // 引数に型に変換できなくてもエラー。 // void readlnToken(T...)(auto ref T args) { import std.stdio; import std.conv; import std.string; import std.array; auto line = split(readln()); foreach(ref arg; args) { arg = to!(typeof(arg))(line[0]); line = line[1..$]; } assert(line.empty()); // got all token?? } void solve() { import std.stdio; int V, E, r; readlnToken(V,E,r); auto tree = new Edge[][](V,0); foreach(i; 0..E) { int s, t, d; readlnToken(s,t,d); tree[s] ~= Edge(t,d); } auto dist = dijkstra(tree, r); foreach(d; dist) { if (d == inf) writeln("INF"); else writeln(d); } } void main() { } // // stdin/stdout を redirect してテストするための関数 // void redirectString(in string input, ref string output, void delegate() fun) { auto savedOut = stdout; auto savedIn = stdin; scope(exit) { stdout = savedOut; stdin = savedIn; } auto tmpOut = File.tmpfile(); auto tmpIn = File.tmpfile(); // prepare input tmpIn.write(input); tmpIn.rewind; stdout = tmpOut; stdin = tmpIn; fun(); // 一応念の為 stdout = savedOut; stdin = savedIn; // read output tmpOut.rewind; foreach(line; tmpOut.byLine()) output ~= (line~"\n"); } // sample 例でのテスト unittest { import std.string; string output; auto input=q{ 4 5 0 0 1 1 0 2 4 1 2 2 2 3 1 1 3 5 }.strip; auto answer=q{ 0 1 3 4 }.strip; redirectString(input, output, { solve(); }); assert(output.split==answer.split); }
D 言語の基礎文法は他のサイトに任せるとして、上のコードをちょっと解説すると、
alias Edge = Tuple!(int,"to", int ,"cost");
tuple のアクセサーに名前を付けられる。c++ では e.first とか get<0>(e) とかでしかアクセスできなかった。
alias PriorityQueue = BinaryHeap;
PriorityQueue がなかった(どっかにあるのかもしれないが)ので BinaryHeap で代用させる。
比較関数を "a.cost>=b.cost" と文字列で指定できるのもステキ。
tie!(v,cost) = queue.front();
c++ で便利な std::tie っぽいことは TypeTuple でできる。
auto dist = new int[V]; fill(dist, inf);
動的配列の初期値は 0 らしい。
0 以外で初期化をしたいときは fill(range, value) だけでいいのがうれしい。c++ のように
#define RANGE(vec) vec.begin(),vec.end()
なる(けしからん)マクロがいらないのがよい。
多重配列でも fill がそのまま使える。
ちなみに
int[2][6] vec; writeln(vec[5][1]);
と多重配列では配列のインデックス対応が逆になっているっぽいのが c++ と違う。
void readlnToken(T...)(auto ref T args)
c++ のように
cin >> x >> y >> z;
みたいに書けないので面倒だなーと思ってたが、可変数引数 template でおいしくいただけた。
int V, E, r;
readlnToken(V,E,r);
のように使うと指定した型に stdin の空白区切り入力を格納できる。
void redirectString(in string input, ref string output, void delegate() fun)
delegate としてクロージャを渡せる。ここでは stdin/stdout をすげ替えてソース内でテストを完結させられるようにしている。
プログラミングコンテストでは stdin/stdout で入出力のやりとりをするので、提出コードを変えずにサンプルテストができるとうれしい。
そこで stdin/stdout の挿げ替えをしてローカルテストをしている。(あんまりこういうの見かけないけど便利だと思うの僕だけ？)
呼び出し側でヒアドキュメント記法 q{} を使って作成したテストケースの input を stdin にすげ替えてテストしている。
scope(exit) { stdout = savedOut; stdin = savedIn; }
にて何かのエラーになってもかならず元の stdout/stdin に戻せるようにしている。
ちなみに c++ では cin/cout の挿げ替えを
void redirect(std::istream &input, std::ostream &out, const std::function<void(void)> &func) { std::streambuf *cinbuf = std::cin.rdbuf(); //save old buf std::cin.rdbuf(input.rdbuf()); //redirect cin std::streambuf *coutbuf = std::cout.rdbuf(); //save old buf std::cout.rdbuf(out.rdbuf()); //redirect cout func(); std::cin.rdbuf(cinbuf); //reset to standard input again std::cout.rdbuf(coutbuf); //reset to standard output again }
みたいに書ける。ただし scanf/printf 系の入出力は挿げ替えできない。(何か方法があるのかもしれないが調べてない。)
あと触っていて気づいたことで、配列の範囲外アクセス range violation は Exception じゃなくて Error として throw される。
try-catch するときは Exception じゃなくて Error で catch しないとだめ。
unittest { import std.array; int[] a = [2,3,4]; a = a[1..$]; writeln(a); a = a[1..$]; writeln(a); a = a[1..$]; writeln(a); assert(a.empty()); try { a = a[1..$]; assert(false); } catch(Exception ex) { assert(false); } catch(Error e) { writeln(e.msg); // range violation は Error を投げる } }
このコードも移植中に書いた unittest 。やはり unittest の標準サポートはいい。
