sachaos.md
----------

# AtCoder ABC168 D 問題の反省と Go のプロファイリング

このエントリーをはてなブックマークに追加

AtCoder の ABC168 の D 問題 で計算量的には問題なかったが、 そもそも入力を読み込むのにめっちゃ時間かかっていて TLE を出してしまったので、戒めとしてメモ。

## 結論

Go の fmt.Scanf では毎回システムコールが走って大量の入力だと遅い。 大量の入力を受けるときは bufio.Scanner を利用する。

以前もこのことで TLE を出し、苦汁を舐めだのだけど最近は Python で AtCoder に参加していたので忘れてしまっていた。

Go 言語で標準入力から読み込む競技プログラミングのアレ --- 改訂第二版

## TLE になっていたテストケース

入力がめっちゃ多い。

https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAD1PCSXpPVjPMW3pOfolvYqa/ABC168/D/in?dl=0&preview=sub1_36.txt&subfolder_nav_tracking=1

## TLE が出たコード

```go
package main
 
import "fmt"
 
func main() {
	// Code for D - .. (Double Dots)
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	a := make([]int, m)
	b := make([]int, m)
 
	path := map[int][]int{}
	for i := 1; i <= n; i++ {
		path[i] = make([]int, 0)
	}
 
	for i := 0; i < m; i++ {
		fmt.Scanf("%d %d", &a[i], &b[i])
		path[a[i]] = append(path[a[i]], b[i])
		path[b[i]] = append(path[b[i]], a[i])
	}
 
	mem := make([]int, n+1)
	q := []int{1}
 
	for len(q) > 0 {
		base := q[0]
		q = q[1:]
		rooms := path[base]
 
		for _, r := range rooms {
			if mem[r] > 0 {
				continue
			}
 
			q = append(q, r)
			mem[r] = base
		}
	}
 
	fmt.Println("Yes")
	for _, v := range mem[2:] {
		fmt.Println(v)
	}
}
```

### プロファイリングしてみる

  1. go get github.com/pkg/profile
  2. defer profile.Start().Stop() を埋め込み
  3. テストケースを入力にして実行
  4. プロファイルの結果を見る

#### テストケースを入力にして実行

```shell
$ cat ~/sub1_36.txt | go run abc168/abc168_d/main.go | tail
2020/05/18 00:54:06 profile: cpu profiling enabled, /var/folders/y3/t2g2qt4s6sxbptdqcf9t_s9r0000gn/T/profile482429519/cpu.pprof
2020/05/18 00:54:09 profile: cpu profiling disabled, /var/folders/y3/t2g2qt4s6sxbptdqcf9t_s9r0000gn/T/profile482429519/cpu.pprof
89992
89992
89992
89992
89992
89992
89992
89992
89992
89992
```

#### プロファイルの結果を見る

/var/folders/y3/t2g2qt4s6sxbptdqcf9t_s9r0000gn/T/profile482429519/cpu.pprof に結果が書き込まれているのでこれをビジュアライズする

```shell
$ go tool pprof -http=:8080 /var/folders/y3/t2g2qt4s6sxbptdqcf9t_s9r0000gn/T/profile482429519/cpu.pprof
Serving web UI on http://localhost:8080
```

グラフを見てみると fmt.Scanf で 2 秒かかっているのがわかった。 これでは入力を読み込むだけで、時間が過ぎてしまう。

pprof1

### TLE を克服したコード

Go 言語で標準入力から読み込む競技プログラミングのアレ --- 改訂第二版 で紹介されている bufio.Scanner を利用したものを使っている。

```go
package main

import (
	"bufio"
	"fmt"
	"github.com/pkg/profile"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	defer profile.Start().Stop()
	// Code for D - .. (Double Dots)
	n := nextInt()
	m := nextInt()

	path := map[int][]int{}
	for i := 1; i <= n; i++ {
		path[i] = make([]int, 0)
	}

	for i := 0; i < m; i++ {
		x := nextInt()
		y := nextInt()
		path[x] = append(path[x], y)
		path[y] = append(path[y], x)
	}

	mem := make([]int, n+1)
	q := []int{1}

	for len(q) > 0 {
		base := q[0]
		q = q[1:]
		rooms := path[base]

		for _, r := range rooms {
			if mem[r] == 0 {
				q = append(q, r)
				mem[r] = base
			}
		}
	}

	fmt.Println("Yes")
	for _, v := range mem[2:] {
		fmt.Println(v)
	}
}
```

#### プロファイルの結果を見る

入力の処理 nextInt は 30ms で終わっていて、めちゃくちゃ速くなっている。

pprof2

## 所感

  • 純粋な計算量以外のところで詰まるのは辛い。
  • もう競技プログラミングにおいて fmt.Scanf は使わない。
  • もうちょっと、実装レベルにまで踏み込んで調べたい気もする。

## 参考にしたもの

このエントリーをはてなブックマークに追加