見習い魔法使いの日常

果たして魔法が使える日は訪れるのか!?

Goで bufio.Scanner.Scan からfalseが返ってくる問題

はじめに

最近Goで競技プログラミングに挑戦し、ものの見事に叩きのめされました...。気持ちを一新してアルゴリズムの勉強をはじめたのですが、Goでbufio.Scanner.Scanからfalseが返ってきてるらしく、サイズの大きい一行を読み込むことができないという問題に直面したため、調査をしました。

false が返ってくるパターン

var sc = bufio.NewScanner(os.Stdin)

func readLine() {
	sc.Scan()
	return sc.Text()
}

基本的には、上のコードをベースに読み込み部分を書いていました。
このコードで今まで入力を取得し、いくつか問題を説いてきたのですが、ある問題で突然止まってしまい...。エラーメッセージもないため、原因不明でお手上げ状態。

原因の調査

ググって見ると簡単にヒットしました。

mickey24.hatenablog.com


1行の長さがScannerのBuffer量をオーバするとスキャンをやめてしまうみたい。

バッファサイズはデフォルトでbufio.MaxScanTokenSize(65536)バイトとあるので実際にどうなのか試してみる.

package main

import (
	"bufio"
	"fmt"
)

func main() {
	fmt.Println(bufio.MaxScanTokenSize)
}
65536

そのとおりですね。
go doc で調べた結果。

$ go doc bufio.MaxScanTokenSize
const (
	// MaxScanTokenSize is the maximum size used to buffer a token
	// unless the user provides an explicit buffer with Scan.Buffer.
	// The actual maximum token size may be smaller as the buffer
	// may need to include, for instance, a newline.
	MaxScanTokenSize = 64 * 1024
)

そして、ちゃんとエラーメッセージはあったみたいです。

if err := sc.Err(); err != nil {
	fmt.Println("Scanner error: %q\n",err)
}

参考にしたブログの中で、

実際Scan()後にErr()を確認しないコードを何度か見たことがある

と述べられており、まさに私でした。

Goは error 型が返ってくると思っていたので、この確認の仕方は知りませんでした。
素晴らしい記事をありがとうございます。
エラーメッセージがわかりさえすれば、失敗している原因がわかります。

Scanner error: "bufio.Scanner: token too long"

ニャルほど。
最初は sc.Scan をみても false だけで、何で失敗しているのか検討もつかなかったけれど、エラーメッセージを見るとトークンが長すぎたのが原因であったということがわかりました。


でも、この問題をC言語で解いたときは、特につまらなかったはず...。
と、いうことでC言語で書いた入力部分のソースを見直してみた。

scanf("%d", &n);
for ( i = 0; i < n; i++) scanf("%d", &A[i]);

1数字ずつ読み込んでいたわけか...理解。
ひとまずは、なんとか読み込みさせるためにC言語のソースっぽく実装してみる。

	var A []int
	var n int
	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		A = append(A, a)
	}

取り替えず、読み込めました。(パチパチ)
これでエラーの原因と、回避策がわかりました。

結局どうすればいいのか

ググっているなかで以下のサイトを見つけました。

qiita.com

競技プログラミングに関してで、私が躓いたことが全部掲載されている。

以下引用

  • 簡単に書きたいとき
    • fmt.Scanを使う
  • たくさん(10 ^ 5)読み込みたいとき
    • bufioのScannerを使う
  • 長い行( > 64 * 10 ^ 3)読み込みたいとき
    • bufioのReadLineを使う

ちなみに、

sc.Split(bufio.ScanWords)

で、スペース区切りにできるみたい。デフォルトは bufio.ScanLines で一行取得。

僕は bufio.Scanner を使った時は、1行を取得した後、以下のようにスペース区切りで分割していたので手間が減りそうです。

for _, v := range strings.Split(sc.Text(), " ") {
    num, _ := strconv.Atoi(v)
    list = append(list, num)
}


コードを書き換えてみました。

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func main() {
	var n int
	var A []int
	fmt.Scan(&n)
	sc.Split(bufio.ScanWords)

	for i := 0; i < n; i++ {
		A = append(A, nextInt())
	}

	fmt.Println(A)
}

できた!

競技プログラミングでは、入力の個数が事前に与えられるのでそれは fmt.Scan で取得します。今回は自作関数の nextInt() で取得しても大丈夫そうです。

さて、残る問題は fmt.Scan と bufio.Scanner のどっちが早いかです。

比べてみた

測定用に、以下のコードを作成した。

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

// fmt.Scanを用いて入力を読み込む
func try_scan() []int {
	var n int
	var A []int
	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		A = append(A, a)
	}
	return A
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

// bufio.Scannerでbufio.ScanWordsを指定して入力を読み込み
func try_scanwords() []int {
	var n int
	var A []int
	fmt.Scan(&n)
	sc.Split(bufio.ScanWords)

	for i := 0; i < n; i++ {
		A = append(A, nextInt())
	}
	return A
}

// 僕がこれまでやっていた手法
func splitElements() []int {
	var n int
	var A []int
	fmt.Scan(&n)
	sc.Split(bufio.ScanLines)
	sc.Scan()
	//if err := sc.Err(); err != nil {
	//	fmt.Printf("Scanner error: %q\n", err)
	//}
	for _, v := range strings.Split(sc.Text(), " ") {
		num, _ := strconv.Atoi(v)
		A = append(A, num)
	}
	return A
}

func main() {
	// try_scan()
	// try_scanwords()
	// splitElements()
	// fmt.Println(a)
}

測定には、AOJのPartition | Aizu Online Judgeの入力ファイルを用い、手元にダウンロードした後、以下のようにして測定した。

$ cat in | /usr/bin/time go run main.go

測定には以下のコードを使用し、main 関数の関数呼び出しのコメントアウトを変えて、手法の切り替えを行った。

timeコマンドを用いて測定したところ、私の環境では問題の入力に対しては bufio.Scanner は fmt.Scanよりも明らかに高速に動きました。

個人的に面白かったのは、私が今まで使っていた入力取得用関数 splitElements の挙動で、エラー処理をしていないと、そのままプログラムは進みスライスAを返してくる。ただし、Aは空のスライスで、その配列の要素にアクセスしようとして...バーンという感じになってしまうことがわかったことです。

まとめ

これまでは bufio.Scanner で1行取得後スペース区切りに分割という方法で、不自由なく問題を解いて来ましたが、1行が大きくなりすぎる場合には注意が必要だということがわかりました。

これを回避する方法としては、fmt.Scan を使って取得する方法もありますが、競技プログラミングはスペース区切りで値が与えられることが多いため、bufio.ScanWords を設定して取得すると、より高速に取得できます。