はじめに

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 ではこのような形式で入力を受け付ける時、

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 を読みに行ってみます。

golang/go/src/fmt/scan.go#L59-L65

// 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 にその理由を返します。

golang/go/src/fmt/scan.go#L117-L126

// 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 構造体を見にいきます。

golang/go/src/bufio/scan.go#L14-L41

// 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 関数（無名関数）は以下のような定義になっています。

// 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 つが定義されています。

// バイト毎
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（代入可能性）に関しては、こちらの記事が分かりやすいかと思います。

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

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

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

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

// 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

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

// スキャナを作成
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/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

データ件数が 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 を使用する必要があるということになります。

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

// ② 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 言語における Scanning の特性と使い分け

目次

はじめに

`fmt.Scan`

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

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

`bufio.Scanner`

実際に使用する場合

速度比較

結論

参考・引用

目次

はじめに

fmt.Scan

fmt.Scan で TLE が発生する

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

bufio.Scanner

実際に使用する場合

速度比較

結論

参考・引用

`fmt.Scan`

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

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

`bufio.Scanner`