【競プロ】Scanning で TLE が発生してコケる

# はじめに

Go 言語で競技プログラミングに臨んだことがある人なら, 一度は`fmt.Scan`関数の落とし穴にハマったことがあるのではないでしょうか. Go 言語では標準入力を受け付ける際に, `fmt.Scan`関数, もしくは`bufio.Scanner`メソッドや`bufio.ReadLine`メソッドをよく用いります.
しかし, Go 言語を使って競技プログラミングをやる場合, `bufio.Scanner`を使用しなければ困る場面があります.
今回の記事では, `fmt`パッケージの`Scan`関数と`bufio`パッケージの`Scanner`メソッドに注目しながら, `fmt.Scan`で TLE が発生する原因と解決策について紹介します.

[結論だけ知りたい人はこちらをクリック](#結論)

# fmt.Scan

まずは, `fmt.Scan`関数の詳細を見てみます.

## fmt.Scan で TLE が発生する

競プロにおいて, 大量のデータ入力が必要になる場合があります.
例えば, 競プロでよく見かける以下の入力形式において

```
N
A1 A2 A3 ... AN
```

ここで, レギュレーションとして _N_ の最大値を $3*10^6$ とします.
一般的に Go 言語ではこのような形式で入力を受け付ける時,

```go
func main() {
	N := // Nの入力を受け付ける・・・①
	if N > int(3*(math.Pow(10, 6))) {
		log.Fatalf("Regulation error: N => %d\n", N)
		return
	}

	A_list := make([]int, N)
	for i := 0; i < N; i++ {
		A_list[i] = // Aの入力を受け付ける・・・②
	}
}
```

のような書き方をするのではないでしょうか.
この時, _N_ の最大値は $3*10^6$ なので, for 文の中では 300 万件ものデータを受け付けなければなりません.
そのため, このような状況において ② の箇所で`fmt.Scan`を使うと多くの場合, TLE（Time Limit Exceeded）による不正解判定が出てしまいます.

## なぜ fmt.Scan だとダメなのか

なぜ, `fmt.Scan`だと TLE するのかを理解するために, `fmt`パッケージの`scan.go`を読みに行ってみます.

https://github.com/golang/go/blob/7cf32686667fe2de869ddab3ede647e34be9209e/src/fmt/scan.go#L59-L65

```go
// 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.
//
func Scan(a ...any) (n int, err error) {
	return Fscan(os.Stdin, a...)
}
```

> Scan は, 標準入力から読み込んだテキストをスキャンし, スペースで区切られた値として, 順に引数に格納します. 改行文字はスペースとしてカウントされます. この関数はスキャンに成功した項目数を返します. この数が, 引数の数より少ないときは, err にその理由を返します.

https://github.com/golang/go/blob/7cf32686667fe2de869ddab3ede647e34be9209e/src/fmt/scan.go#L117-L126

```go
// Fscan scans text read from r, 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.
//
func Fscan(r io.Reader, a ...any) (n int, err error) {
	s, old := newScanState(r, true, false)
	n, err = s.doScan(a)
	s.free(old)
	return
}
```

> Fscan は, r (io.Reader) から読み取られたテキストをスキャンし, スペースで区切られた連続する値を連続する引数に格納します. 改行はスペースとしてカウントされます. 正常にスキャンされたアイテムの数を返します. それが引数の数より少ない場合, err はその理由を報告します.

`fmt.Scan`は内部的に`fmt.Fscan`関数を呼び出します. つまり, `fmt.Scan`は`fmt.Fscan`のラッパー関数であり, 引数の`io.Reader`に標準入力を渡しているだけです. I/O 処理はプログラムを実行する上では比較的重い動作であり, unbufferd I/O の場合, 内部バッファを使用しずに直接ディスクに対してファイル書き込みを行うため, 都度システムコールが発生します. そのため, $3 * 10^6$ 程度の数値を入力すると TLE します.
つまり, 通常は比較的簡単に書くことができる`fmt.Scan`で問題なくても, 競プロのように膨大な量のデータを高速で受け付ける必要がある場合は, `fmt.Scan`だと遅すぎる訳です.

# bufio.Scanner

では, `bufio.Scanner`の場合はどうなっているのか.
まず, `Scanner`の正体を知るために, `bufio`パッケージの`Scanner`構造体を見にいきます.

https://github.com/golang/go/blob/ffe48e00adf3078944015186819a1ed5c6aa8bec/src/bufio/scan.go#L14-L41

```go
// Scanner provides a convenient interface for reading data such as
// a file of newline-delimited lines of text. Successive calls to
// the Scan method will step through the 'tokens' of a file, skipping
// the bytes between the tokens. The specification of a token is
// defined by a split function of type SplitFunc; the default split
// function breaks the input into lines with line termination stripped. Split
// functions are defined in this package for scanning a file into
// lines, bytes, UTF-8-encoded runes, and space-delimited words. The
// client may instead provide a custom split function.
//
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.
	// 以下, 省略
}
```

> Scanner は, 改行で区切られたテキスト行のファイルなどのデータを読み取るための便利なインターフェイスを提供します. Scan メソッドを連続して呼び出すと, ファイルの「トークン」がステップスルーされ, トークン間のバイトがスキップされます. トークンの指定は, SplitFunc 型の split 関数によって定義されます. デフォルトの分割関数は, 入力を行の終端を取り除いた行に分割します. このパッケージでは, ファイルを行, バイト, UTF-8 でエンコードされたルーン文字, およびスペースで区切られた単語にスキャンするための分割関数が定義されています. クライアントは, 代わりにカスタム分割機能を提供する場合があります.

`Scanner`メソッドは, **トークン** によって, 単語ごと（スペース区切り）, 行ごと（改行文字区切り）に効率的に読み取ることができます. また, トークンの指定は`SplitFunc`型の`split`関数によって定義することができるようです.
`split`関数（無名関数）は以下のような定義になっています.

```go
// SplitFunc is the signature of the split function used to tokenize the input.
type SplitFunc func(data []byte, atEOF bool) (advance int, token []byte, err error)
```

> SplitFunc は, 入力をトークン化するために使用される分割関数のシグネチャです.

`SplitFunc`型に代入することができる関数として, 以下の 4 つが定義されています.

```go
// バイト ごと
func ScanBytes(data []byte, atEOF bool) (advance int, token []byte, err error)

// 行 ごと
func ScanLines(data []byte, atEOF bool) (advance int, token []byte, err error)

// ルーン（int32のエイリアス）ごと
func ScanRunes(data []byte, atEOF bool) (advance int, token []byte, err error)

// 単語 ごと
func ScanWords(data []byte, atEOF bool) (advance int, token []byte, err error)
```

これらの関数は, `split`関数と`underlying type`が同一であるため, Go 言語の特性の一つである **Assignability** によって代入することが可能になっています.

Assignability に関しては, [こちら](https://qiita.com/behiron/items/89bf7292aec48b097fe4)の記事が分かりやすいかと思います.

加えて, `Scannerメソッド`は`fmt.Scan`と異なり, 内部にバッファを持っています. これを利用することで, `split`フィールドに定義されたトークンに従ってバッファに格納されたバイト列ごとに I/O 処理（bufferd I/O）を行うため, `fmt.Scan`よりも高速に動作することが可能になります.

スキャナーの作成は, `NewScanner`関数によって行います.

```go
// NewScanner returns a new Scanner to read from r.
// The split function defaults to ScanLines.
func NewScanner(r io.Reader) *Scanner
```

デフォルトで作成されたスキャナーは, 「行」をトークンとして, 入力を受け付けるよう設定されています.
これを上述した`split`関数に置き換えたい場合, `Split`メソッドを使用します.

```go
// Split sets the split function for the Scanner.
// The default split function is ScanLines.
func (s *Scanner) Split(split SplitFunc)
```

## 実際に使用する場合

これを以下のような形式で受け付ける場合,

```
N
A1 A2 A3 ... AN
```

単語（空白スペース）ごとに受け付けることで, 高効率かつ高速に処理が可能になります.

```go
// スキャナを作成
var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords) // 単語（空白スペース）で分割
    for i := 0; i < N; i++ {
		A_list[i] = scanInt() // bufio.Scannerを呼び出す
	}
}

// scanInt scans int type.
func scanInt() (i int) {
	var err error
	sc.Scan()
	i, err = strconv.Atoi(sc.Text()) // int型にparse
	if err != nil {
		log.Fatal("Failed to input", err)
	}
	return
}
```

# 速度比較

実際に以下のコードを使って, データの入力値を増やした時の, `fmt.Scan`と`bufio.Scanner`の読み込み速度を比較してみます. （本番環境を想定して, メモリを 512MB に制限して計測を行なっています. ）

- https://github.com/GotoRen/samples/tree/master/scanning-speed

| データ数            |   fmt.Scan | bufio.Scanner |
| :------------------ | ---------: | ------------: |
| 10                  |  0.000123s |     0.000023s |
| 100                 |  0.000310s |     0.000025s |
| 1000                |  0.004084s |     0.000224s |
| 10000 (=$10^4$)     |  0.033157s |     0.000550s |
| 100000 (=$10^5$)    |  0.509994s |     0.006163s |
| 1000000 (=$10^6$)   |  3.771113s |     0.064092s |
| 2000000 (=$2*10^6$) |  7.210549s |     0.142498s |
| 3000000 (=$3*10^6$) | 10.357201s |     0.190407s |
| 4000000 (=$4*10^6$) | 13.958481s |     0.253358s |

![speed-compare.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/705806/0ced9aeb-6180-867f-e94d-9ae60a4448e2.png)

データ件数が 1 万（$10^4$）件ぐらいまでは, 双方でほぼ同じ読み込み速度であるため, 簡単に書ける`fmt.Scan`の方が良さそうです.
しかし, 10 万（$10^５$）件を超えたあたりから`fmt.Scan`が明らかに遅くなってきます. 今回, レギュレーションとして設定されている『メモリ上限：512MB / 実行タイムアウト：2000ms』において, 100 万（$10^6$）件を読み込む時点で 3 秒以上も掛かるようでは, 300 万（$3 * 10^6$）件を読み込んで処理する際に TLE が発生するのも納得です.
一方, `bufio.Scan`はデータ件数が増えた場合にも, 読み込み速度が劣化しにくく安定して使えるため, 膨大な量のデータを読み込むことが可能になります.

# 結論

これらのことから, ① では, `fmt.Scan`によって入力を受け付ければ良く, ② では, `bufio.Scanner`を使用する必要があるということになります.

```go
// ① Nの入力を受け付ける場合
func main() {
	var N int
	fmt.Scan(&N) // calling fmt.Scan
}
```

```go
// ② 3*10^6回受け付ける場合
var sc = bufio.NewScanner(os.Stdin)

func main() {
    sc.Split(bufio.ScanWords) // split by word
	for i := 0; i < N; i++ {
		A_list[i] = scanInt() // calling bufio.Scanner
	}
}

// scanInt scans int type.
func scanInt() (i int) {
	var err error
	sc.Scan()
	i, err = strconv.Atoi(sc.Text()) // parse to int
	if err != nil {
		log.Fatal("Failed to input", err)
	}
	return
}
```

まとめると,

---

- **速度を気にしなくても良い場合**
  - `fmt.Scan`
- **膨大なデータ（$> 10^{5}$）を高速に読み込む必要がある場合**
  - `bufio.Scanner`
- **また, 今回は触れなかったが, 行数が多い場合（$> 64*10^{3}$）**
  - `bufio.ReadLine`

---

という感じでしょうか.

うーん. 単純な入力受付一つとっても, プログラミングって奥が深い...
競プロハマりそう. 研究もせねば...

### 参考・引用

- [go/src/fmt/scan.go](https://github.com/golang/go/blob/master/src/fmt/scan.go)
- [pkg.go.dev/fmt/#Scan](https://pkg.go.dev/fmt#Scan)
- [go/src/bufio/scan.go](https://github.com/golang/go/blob/master/src/bufio/scan.go)
- [pkg.go.dev/bufio/#Scanner](https://pkg.go.dev/bufio#Scanner)
- [toVersus/get_max_profit.go](https://gist.github.com/toVersus/095cd1010f8cabc44298badbdb0e11bb)
- [C 言語におけるファイル入出力の高速化](https://www.cc.u-tokyo.ac.jp/public/VOL8/No5/data_no1_0609.pdf)
- [Golang のバッファってよくできてるよな](https://note.crohaco.net/2019/golang-buffer/)
- [Go 言語のベンチマークでパフォーマンス測定](https://scrapbox.io/tsuchinaga/%E3%80%90Golang%E3%80%91fmt.Scan%E3%81%A8bufio.Scanner%E3%81%AE%E9%80%9F%E5%BA%A6%E6%AF%94%E8%BC%83)
- [Go 言語で標準入力から読み込む競プロのアレ](https://qiita.com/tnoda_/items/b503a72eac82862d30c6)
- [Go の代入可能性についてちゃんと理解してみる](https://qiita.com/behiron/items/89bf7292aec48b097fe4)

### 読者の皆さんへ

本記事を読んで下さり, ありがとうございます.
誤字脱字や誤った内容を見つけた場合, 本記事にてフィードバックを下さると幸いです.
また, 意見や提案等がありましたら, 併せて本記事のコメント欄に記述して頂けると助かります. より良い記事を書くため, 改良の参考にさせて頂きます.

@ren510dev