fmtとbufioのScanメソッドの違いってなんだろう?[Go]

データ構造やアルゴリズムや競プロで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.

https://pkg.go.dev/fmt

:::note
### I/Oとは
Input/Outputを`I/O`と略して使われます。
他にも標準入出力のこともI/Oと呼ばれたりします。
:::

:::note
### package
Go言語では、ソースコードをpackageという単位で管理しています。

一ファイルの最上部にpackageを記述することで、そのコードを一つのpackageとして管理することができます。
```go
package main
```

そのパッケージを複数集めたのがモジュールです。
下のようなコマンドを打つことがあると思いますが、これはmoduleを作成してパッケージを作成したmoduleに入れています。
```zsh:zsh
go mod init <module_name>
```
:::

fmtとしてよく使うのは、標準出力を行える`Print`、`Printf`、`Println`、文字列の整形で使える`Sprinrf`だと思います。

- Print
```go
fmt.Print(str)
```

- Printf
```go
fmt.Printf(str)
```

- Println
```go
fmt.Println(str)
```

- Sprintf
```go
fmt.Srintf(format,v)
```

# bufioパッケージとは
bufioパッケージは、buffered I/Oを行うことができるパッケージです。

>Package bufio implements buffered I/O. 

https://pkg.go.dev/bufio

:::note
### bufferedとは
バッファリングとは、メモリ空間にキャッシュとして情報を貯めておき、プログラムで情報を使い回すことです。
HDDやSSDに直接書き込むのではなく、計算用紙のように、長期的には使わないが短期的に使う情報で使用します。
DBから取り出してある情報はもう一度DBから取り出さず、バッファリングを利用してキャッシングすることで処理速度を早く処理することができます。

bufferedはバッファリングされたということを指しています。
:::

入出力においてバッファリングを使うことができ、キャッシングしながら入出力を扱うことができます。

# fmtとbufioのScan()での違いを調べてみる

今回の本題です。

fmtとbufioのざっくりとしたパッケージの概要をご紹介しました。

2つのパッケージは、フォーマットされたI/OとバッファリングされたI/Oという違いがあります。

最初の方にも書いたように二つのパッケージにはScanメソッドという標準入力を読み取るためのメソッドが実装されていますが、実行速度に違いがあります。

まず、その実行速度がどのくらい差があったのか、ご紹介します。

## 実際にfmtとbufioはどの程度の処理速度の違いがあるのか

今回調べるきっかけになった問題でどの程度差が出たのかというと

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D

これのテストケース37番で以下のような差が出ていました。

|fmt|bufio
|---|---
|01.26 s|00.02 s

1sという大きな差が出てしまっており、実行制限が1sであったためここでTLEが出てしまっていました。

この結果だけでも実行の仕方から大きな速度差が生まれているなと感じました。

それぞれのパッケージのScanメソッドの違いを調査しながら、この速度差の原因を調べてみます。

# どうしてこのような違いが出るのか

### fmt.Scan()の仕様

https://pkg.go.dev/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にシステムコールされてしまうので、競プロのような大量のデータを高速に扱う場合には向いていません。

```go 
var str string
fmt.Scan(&str)
```

### bufio.Scanの仕様

https://pkg.go.dev/bufio#Scanner.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構造体のメソッドとして実装されています。
```go
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メソッドを使うことで変数に格納したりすることができます。
```go
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
str := scanner.Text()
```

# まとめ

結果、2つのパッケージによるScanメソッドの使い分けは以下のようになりました。

|メソッド|特徴|使い分け
|---|---|---
|fmt.Scan()|スペースごとに読み取る|簡単に標準入力による読み込みを行いたい時
|bufio.Scan()|トークン(デフォルトは行)ごとに読み取る|大量の行や文字を高速に読み込みたい時

競プロ等の高速性が求められるときにはbufioパッケージが好ましいですが、実務等でファイル読み込み等で仕様するときfmtパッケージでも数秒で終わると思うので、速度を求めないときはfmtパッケージでも良さそうですね。