はじめに
競技プログラミングでは、標準入力から数値や文字列をインタラクティブに受け取って処理するコードをよく書きます。Go では、入力のサイズによって、fmt.Scan、bufio.Scanner、bufio.Reader.LeadLine を使い分けるのが定石です。
簡単に書きたいとき
fmt.Scan を使う
たくさん (> 10^5) 読み込みたいとき
bufio の Scanner を使う
長い行を (> 64x10^3) 読み込みたいとき
bufio の ReadLine を使う
- Go 言語で標準入力から読み込む競技プログラミングのアレ
ただ、具体的にどの程度性能に差がでるか、ベンチーマークの結果を示している記事が見当たらなかったので、書いてみました。
測定対象のコード
AIZU ONLINE JUDGE の問題 を使って、ベンチマーク測定の対象となるコードを書きました。
fmt.Scan は、fmt.Fscan のラッパー関数で、引数の io.Reader に標準入力を渡しているだけです。ですので、テストコードではテストケースごとに入力するファイルを作成して、io.Reader にそのファイルディスクリプタを渡してあげました。
コードは Gist にあげています。
ベンチマークの測定結果
Windows マシン上で測定したベンチマークの結果です。コンパイラによる最適化前の結果ですので、あくまで参考値ですが、たくさん読み込む必要がある場合、性能が1桁程度違ってくることが分かりました。
PS> go test -bench . --benchmem
goos: windows
goarch: amd64
pkg: github.com/toversus/go-aoj/alds1/1_d_maximum_profit
BenchmarkGetMaxProfitByFscan-8 2000 688114 ns/op 6338 B/op 2004 allocs/op
BenchmarkGetMaxProfitByScanner-8 20000 75352 ns/op 10416 B/op 2002 allocs/op
PASS
この問題で「Time Limit Exceeded」から抜け出せない原因が、fmt.Scan による入力処理部分のボトルネックだと気付くのに時間が掛かってしまいました。皆さんも気を付けましょう。
2018/5/22 追記
コードに手を入れていたら、測定結果が変わってきたので、記事を更新しました。
せっかくなので、Russ Cox 先生作の benchstat を使って、両者を比較してみました。
1行目が処理時間、2行目がメモリアロケーションで確保した容量、3行目がメモリアロケーションの回数の比較です。
PS > go get golang.org/x/perf/cmd/benchstat
PS > benchstat .\old.txt .\new.txt
name old time/op new time/op delta
GetMaxProfit-8 684µs ± 3% 74µs ± 7% -89.16% (p=0.000 n=10+10)
name old alloc/op new alloc/op delta
GetMaxProfit-8 6.34kB ± 0% 10.42kB ± 0% +64.34% (p=0.000 n=10+10)
name old allocs/op new allocs/op delta
GetMaxProfit-8 2.00k ± 0% 2.00k ± 0% -0.10% (p=0.000 n=10+10)