AtCoder ABC168 D 問題の反省と Go のプロファイリング
AtCoder の ABC168 の D 問題 で計算量的には問題なかったが、 そもそも入力を読み込むのにめっちゃ時間かかっていて TLE を出してしまったので、戒めとしてメモ。
## 結論
Go の fmt.Scanf では毎回システムコールが走って大量の入力だと遅い。
大量の入力を受けるときは bufio.Scanner を利用する。
以前もこのことで TLE を出し、苦汁を舐めだのだけど最近は Python で AtCoder に参加していたので忘れてしまっていた。
Go 言語で標準入力から読み込む競技プログラミングのアレ --- 改訂第二版
## TLE になっていたテストケース
入力がめっちゃ多い。
## TLE が出たコード
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)
}
}### プロファイリングしてみる
go get github.com/pkg/profiledefer profile.Start().Stop()を埋め込み- テストケースを入力にして実行
- プロファイルの結果を見る
#### テストケースを入力にして実行
$ 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 に結果が書き込まれているのでこれをビジュアライズする
$ go tool pprof -http=:8080 /var/folders/y3/t2g2qt4s6sxbptdqcf9t_s9r0000gn/T/profile482429519/cpu.pprof
Serving web UI on http://localhost:8080グラフを見てみると fmt.Scanf で 2 秒かかっているのがわかった。
これでは入力を読み込むだけで、時間が過ぎてしまう。
### TLE を克服したコード
Go 言語で標準入力から読み込む競技プログラミングのアレ --- 改訂第二版 で紹介されている bufio.Scanner を利用したものを使っている。
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 で終わっていて、めちゃくちゃ速くなっている。
## 所感
- 純粋な計算量以外のところで詰まるのは辛い。
- もう競技プログラミングにおいて
fmt.Scanfは使わない。 - もうちょっと、実装レベルにまで踏み込んで調べたい気もする。