データ構造やアルゴリズムや競プロでGoを使うとなった時に標準入出力が必要になると思います。
標準入力ではfmtパッケージのScan()を使って、標準入力をすることができます。
しかし、その方法だと処理が遅くTLEが出てしまいます。
その解決方法としてbufioパッケージのScan()を使うのですが、どのような違いがあるのかわからないので調べてみようと思います。
fmtパッケージとは
fmtパッケージは、C言語のprintfやscanfなどフォーマットされた入出力(I/O)を行えるパッケージです。
Package fmt implements formatted I/O with functions analogous to C's printf and scanf. The format 'verbs' are derived from C's but are simpler.
fmtとしてよく使うのは、標準出力を行えるPrint、Printf、Println、文字列の整形で使えるSprinrfだと思います。
fmt.Print(str)
- Printf
fmt.Printf(str)
- Println
fmt.Println(str)
- Sprintf
fmt.Srintf(format,v)
bufioパッケージとは
bufioパッケージは、buffered I/Oを行うことができるパッケージです。
Package bufio implements buffered I/O.
入出力においてバッファリングを使うことができ、キャッシングしながら入出力を扱うことができます。
fmtとbufioのScan()での違いを調べてみる
今回の本題です。
fmtとbufioのざっくりとしたパッケージの概要をご紹介しました。
2つのパッケージは、フォーマットされたI/OとバッファリングされたI/Oという違いがあります。
最初の方にも書いたように二つのパッケージにはScanメソッドという標準入力を読み取るためのメソッドが実装されていますが、実行速度に違いがあります。
まず、その実行速度がどのくらい差があったのか、ご紹介します。
実際にfmtとbufioはどの程度の処理速度の違いがあるのか
今回調べるきっかけになった問題でどの程度差が出たのかというと
これのテストケース37番で以下のような差が出ていました。
| fmt | bufio |
|---|---|
| 01.26 s | 00.02 s |
1sという大きな差が出てしまっており、実行制限が1sであったためここでTLEが出てしまっていました。
この結果だけでも実行の仕方から大きな速度差が生まれているなと感じました。
それぞれのパッケージのScanメソッドの違いを調査しながら、この速度差の原因を調べてみます。
どうしてこのような違いが出るのか
fmt.Scan()の仕様
Scan scans text read from standard input, storing successive space-separated values into successive arguments. Newlines count as space. It returns the number of items successfully scanned. If that is less than the number of arguments, err will report why
fmt.Scanでは、標準入力で受け取った内容をスペース区切りでスキャンします。改行もスペースとして扱われ、スキャンが成功したものは引数に入れられていきます。
ただ読み取る時に毎回OSにシステムコールされてしまうので、競プロのような大量のデータを高速に扱う場合には向いていません。
var str string
fmt.Scan(&str)
bufio.Scanの仕様
Scan advances the Scanner to the next token, which will then be available through the Scanner.Bytes or Scanner.Text method. It returns false when there are no more tokens, either by reaching the end of the input or an error. After Scan returns false, the Scanner.Err method will return any error that occurred during scanning, except that if it was io.EOF, Scanner.Err will return nil. Scan panics if the split function returns too many empty tokens without advancing the input. This is a common error mode for scanners.
bufio.Scanではトークンと呼ばれるもので区切っていき、それをバッファリングしていきます。
トークンとは何かを掴むためにScanメソッドを見てみます。
Scanメソッドは、下のScanner構造体のメソッドとして実装されています。
type Scanner struct {
r io.Reader // The reader provided by the client.
split SplitFunc // The function to split the tokens.
maxTokenSize int // Maximum size of a token; modified by tests.
token []byte // Last token returned by split.
buf []byte // Buffer used as argument to split.
start int // First non-processed byte in buf.
end int // End of data in buf.
err error // Sticky error.
empties int // Count of successive empty tokens.
scanCalled bool // Scan has been called; buffer is in use.
done bool // Scan has finished.
}
https://go.googlesource.com/go/+/go1.16.3/src/bufio/scan.go#30
ここにmaxTokenSizeというフィールドにあるように、Scanner構造体は最大のトークンサイズを指定できます。
トークンって何?という感じだったのですが、どうやらトークンは区切るデータの最小単位に当たるものっぽいです。
Scanner構造体にはしっかりbufというフィールドがあり、bufioの説明であったようにバッファリングしながらI/Oを行います。
Scanでは、トークンごとにバッファリングした内容をscanしていき、スペースごとに区切ることで粒度が小さくなっていたのを大きくできるように調整できるようになったので、実行速度が比較的かかるI/Oのシステムコール数を少なくすることができます。
読み込んだ値は、Scanner構造体に実装されているTextメソッドを使うことで変数に格納したりすることができます。
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
str := scanner.Text()
まとめ
結果、2つのパッケージによるScanメソッドの使い分けは以下のようになりました。
| メソッド | 特徴 | 使い分け |
|---|---|---|
| fmt.Scan() | スペースごとに読み取る | 簡単に標準入力による読み込みを行いたい時 |
| bufio.Scan() | トークン(デフォルトは行)ごとに読み取る | 大量の行や文字を高速に読み込みたい時 |
競プロ等の高速性が求められるときにはbufioパッケージが好ましいですが、実務等でファイル読み込み等で仕様するときfmtパッケージでも数秒で終わると思うので、速度を求めないときはfmtパッケージでも良さそうですね。