前書き

始めまして、メガネです。
AtCoderをGolangでやった時にScannerを使った時と使わなかった時の差がどれくらいでるか検証してみました。
なおこの記事は本人の思い付きで書いているので、いろいろツッコミどころがあると思いますが、生暖かい目で見てもらえるとうれしいです。あと、本文中には提出したコードを載せないようにしました。

検証内容

GolangでScannerを使った場合と使わなかった場合の二つの実行時間の差を検証する。ただし、計算量がO(N)の問題を使用し、Nの値は制約の中で一番大きい数とする。なお、入力以外の部分のコードは同じものとする。

使用言語

Go (1.6)

検証に使用した問題

Scanner部分のコード

Scanner.go

package main
import(
  "fmt"
  "bufio"
  "os"
  "strconv"
)
var sc=bufio.NewScanner(os.Stdin)
func nextInt() int{
  sc.Scan()
  i, e :=strconv.Atoi(sc.Text())
  if e!=nil{
    panic(e)
  }
  return i
}
func main(){
  var i int
  sc.Split(bufio.ScanWords)
  n:=nextInt()
  a:=make([]int, n)
  for i=0;i<n;i++{
    a[i]=nextInt()
  }
}

検証結果

AtCoder Beginner Contest 81 B - Shift onlyでの結果

$N=200$である。

Scannerを使用した場合

結果　1 ms

Scannerを使用しなかった場合

結果　3 ms

AtCoder Beginner Contest 142 B - Roller Coasterでの結果

$N=10^5$である。

Scannerを使用した場合

結果　16 ms

Scannerを使用しなかった場合

結果　314 ms

考察

$N=100$の時ではScannerを使うとおよそ3倍ほど早くなったが、$N=10^5$の時では20倍ほど早くなった。(正確には19.625倍) これをGeoGebraというサイトで雑にプロットしてみた。
A=(1,3), B=(16,314)でとってみたら、ぱっと見$y=x^5$くらいの傾きになった。Nの値が大きければ大きいほど、Scannerは使うべきである。これだけでTLEを回避できそうなくらいである。やはりGo is God.

終わりに

思い付きで1時間弱で書いたのでわりとガバガバなところもありますし、検証に使った問題がたったの二問だけですので、このデータは十分正確ではないです。夏休みに気が乗ったら検証方法をよりよくして改訂版を書くかもしれないので、またその時にいい感じにします。何かあればTwitterのhima_megane_ までお願いします。

GolangでScannerを使った時と使わなかった時

前書き