D言語。
ローレベルな事も抽象的な事もできて、読みやすくて、使いやすい標準関数が揃っていて、速度もそこそこ速い。
競プロで better C++ くらいの使い方するのにとても良いと思っています。
なのですが、Dで標準入力から取得する時、皆さんどうしてます？
方法としては3種類くらいあるかなぁと思っています。
- readlnを酷使する
- readfを酷使する
- stdin.byLineを酷使する
core.stdc.stdioを活用する
他にもやり方はあるかもしれないのですが、さっと思いつくのはこんなところですかね。
自分が楽なものを使えば良いと思うのですが、しかし競プロで利用するならば速度（とメモリ消費）を考えないといけません。
……これらの方法で、どれが一番速いのでしょうか？
サンプル問題
適当にこんな問題を考えました。
N行M列の数列があります。
全ての数字の合計の、下3桁を求めなさい。
条件:
1 <= N, M <= 10^3
0 <= 全ての数字 < 10^3
入力:
N M
X1,1 X1,2 ... X1,M
:
XN,1 XN,2 ... XN,M
これを、3種類の標準入力で解いてみましょう。
テストケースを作る
それ用のスクリプトを雑に書きました。
N = 10 ** 3
M = 10 ** 3
puts "#{N} #{M}"
nums = [*0...1000]
N.times do
puts M.times.map { nums.sample }.join(" ")
end
Rubyで書きました。
解答のコードを書く
こっちは勿論 D で書きましょう。
readlnを使う
import std.stdio, std.conv, std.array;
void main()
{
auto N = readln.split[0].to!int;
int c;
int[] ns;
foreach (_; 0..N)
foreach (n; readln.split) c = (c + n.to!int) % 1000;
writeln(c);
}
readln 関数を N+1 回呼んで、全部の行を取得しています。
先頭以外の行は split 関数で分割し（この関数は引数無しで呼ぶと空白で分割してくれます）、 foreach で回して to 関数で int 型に変換しつつ下3桁を足していきます。
readlnを使う（バッファを活用する）
readln 関数は、バッファを取る事ができます。読み込んだ行を返り値として返すと、その度に文字列のメモリのアロケーションが発生するのに対し、バッファを使うとそのコストを抑える事ができます（と、関数の説明に書いてあります）。
というわけでバッファを使う版も書いてみましょう。
import std.stdio, std.conv, std.array;
void main()
{
auto N = readln.split[0].to!int;
int c;
int[] ns;
char[] buf;
foreach (_; 0..N) {
readln(buf);
foreach (n; buf.split) c = (c + n.to!int) % 1000;
}
writeln(c);
}
readfを使う
writef の逆バージョンですね。フォーマットで指定した形式で文字列を読み込む事ができます。何となく便利そうですよね。
import std.stdio, std.conv, std.array;
void main()
{
int N, M;
readf("%d %d", &N, &M);
int c, X;
foreach (_1; 0..N) foreach (_2; 0..M) {
readf(" %d", &X);
c = (c + X) % 1000;
}
writeln(c);
}
最新のphobosだとポインタで渡す必要が無かったり、フォーマット文字列をコンパイル時に渡せたりする版のreadf（やwritef）が入っているのですが、AtCoderで使えるDだとまだその機能が入っていませんでしたね。残念。
byLine関数を使う
ファイルを1行単位の range として扱う関数です。
import std.stdio, std.conv, std.array;
void main()
{
int c = -1;
foreach (line; stdin.byLine) {
if (c == -1)
c = 0;
else
foreach (n; line.split) c = (c + n.to!int) % 1000;
}
writeln(c);
}
やってる事は readln 版とそんなに変わりませんね。
比較する
簡単なスクリプトを書いて速度を比較します。
Dには std.datetime.stopwatch.benchmark という関数があるので使ってみました。
test${N}.txt という名前で10個くらいテストファイルを作って、確認してみます。
import std.stdio, std.conv, std.process, std.datetime.stopwatch;
void test(string filename)()
{
static foreach (i; 1..11)
executeShell("./" ~ filename ~ " < test" ~ i.to!string ~ ".txt");
}
void main()
{
auto r = benchmark!(test!"readln_test", test!"readln_buf_test", test!"readf_test", test!"byline_test")(1);
writefln("readln_test:\t%s", r[0]);
writefln("readln_buf_test:\t%s", r[1]);
writefln("readf_test:\t%s", r[2]);
writefln("byline_test:\t%s", r[3]);
}
結果がこうなりました。
readln_test: 1 sec, 323 ms, and 520 μs
readln_buf_test: 1 sec, 197 ms, 249 μs, and 9 hnsecs
readf_test: 4 secs, 501 ms, 440 μs, and 2 hnsecs
byline_test: 1 sec, 246 ms, 363 μs, and 3 hnsecs
見てみる
readf 関数を使った場合が明白に遅いですね。その他は、まぁどんぐりの背比べでしょうか。
バッファを使った readln が一番速いように見えますが、何度か試行すると byLine 版と逆転したりするので、同じくらいという事でしょうか。ただ、バッファを使わない場合よりは間違いなく速いです。
実は byLine 関数は中でバッファを使った readln を使っているので、速度にほとんど差が無いのは当然なんですね。
一方 readf は少しややこしい事をしています。
その辺りが速度の違いに現れてるんじゃないですかね。
結論
どれを使えば良いんでしょうね？
個人的には readln で1行取得して、 chomp なり split なりしてから to でよしなに変換してやるのが楽でわかりやすいので多用しています。
readln.split.to!(int[]); // intの配列に変換
readln.chomp.to!long; // 何か大きな数を取得
調査結果からバッファを使った方が多少速い事が分かりますが、標準入力からの取得なんてそこまで何度もループする処理ではないので、僅かな時間すら惜しいような問題でも無い限りそんなに気にする事じゃないかなぁと思っています。
最初の1行読み取る、みたいな処理ならば、 readf 使ったって良いと思います。