外に出るねくら

~ 外に出たって結局やることは自宅と同じ ~

トップ > Goで実行時間を7msから4msまで減らした件

Goで実行時間を7msから4msまで減らした件

TL;DRってなんかかっこいいから使ってみたかった。
けどこんな記事を見かけて、僕は顰蹙買いたくなかったのでこれからも使わないことにする。
一度使い出したらクセになりそうだし。

さて、そんなことはさておき

Goで実行時間を7msから4msまで減らした件

ってどういうことか説明します。

最近AtCoderやってるんです。golangで。

毎年半分記念でGoogle Code Jamに出てるんですが、毎年qualifier stageで脱落してて半分記念のクセに超悔しいので、そろそろ本気モードで勉強しようと思いまして。

golangを使っている理由は単純に使ってみたかったから。ホントはpythonの方がいいんだろう。でもホントのホントはCとかC++の方がいいんだろう。
それでも使いたい欲求を抑えることはできなかった。
golang使いたいがために勉強しそうなんてのも期待した。(そして実際そうなってる)

で、ある問題を、初めにめちゃくちゃ愚直に解いて、そのあとリファクタリングをしてどこまで早くなるのかを試してみたくなった。
その問題がこちら。(問題文掲載していいのかわからなかったのでやめとく)
atcoder.jp

2つの数字(N, Y)を与えられて、 a+b+c = N かつ 10000 × a + 5000 × b + 1000 × c = Y になる a, b, c の組合せを探す感じ。
2秒以内に、256Mのメモリで。
ちなみに組合せがない場合は -1 -1 -1 って出力してね。

解法はめちゃくちゃ簡単。

総当り

残念ながら僕にはそれしか方法思いつかなかった。
でも当たり方にもいろいろあるんですよということで。

めちゃくちゃ愚直な解法

文字通り 総当り

package main

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

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() {
    sc.Split(bufio.ScanWords)
    n := nextInt() // N の読み込み
    y := nextInt() // Y の読み込み
    print(logic(n, y))
}

func logic(n, y int) string {
    maxA := y/10000 // Yを10000で割ってaの最大値を算出。aを見つけるためのループの終端
    maxB := y/5000 // Yを5000で割ってbの最大値を算出。bを見つけるためのループの終端
    maxC := y/1000 // Yを1000で割ってcの最大値を算出。cを見つけるためのループの終端
    for a := 0; a < maxA+1; a++ {
        for b := 0; b < maxB+1; b++ {
            for c := 0; c < maxC+1; c++ {
                // ルーーーーーープ
                if a+b+c == n && 10000*a+5000*b+1000*c == y{
                    // a+b+c = N かつ 10000 × a + 5000 × b + 1000 × c = Y だったらその組合せを返す
                    return strconv.Itoa(a)+" "+strconv.Itoa(b)+" "+strconv.Itoa(c)
                }
            }
        }
    }
    return "-1 -1 -1" // 組合せがなければこれを返す
}

func print(ans string) {
    fmt.Println(ans)
}

凄まじい・・・
もちろん2秒オーバーで実行時間制限超過。
ここからリファクタリングが始まる・・・

とりあえずテスト通す

修正内容一つ一つ書いてたら記事が長くなるので、テストが通るところまで一気にワープする。

package main

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

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() {
    sc.Split(bufio.ScanWords)
    n := nextInt()
    y := nextInt()
    print(logic(n, y))
}

func logic(n, y int) string {
    maxA := y/10000
    if y%10000 == 0 && maxA == n {
        // Y が10000で割りきれて、かつ商がnならそれ答えじゃん
        return strconv.Itoa(maxA)+" 0 0"
    }
    maxB := y/5000
    if y%5000 == 0 && maxB == n {
        // Y が5000で割りきれて、かつ商がnならそれ答えじゃん
        return "0 "+strconv.Itoa(maxB)+" 0"
    }
    maxC := y/1000
    if y%1000 == 0 && maxC == n {
        // Y が1000で割りきれて、かつ商がnならそれ答えじゃん
        return "0 0 "+strconv.Itoa(maxC)
    }
    for a := 0; a < maxA+1; a++ {
        if a > n {
            break // aがNより大きくなったらそれ以降確認する意味無いよね
        }
        for b := 0; b < maxB+1; b++ {
            if a+b > n {
                break // a+bがNより大きくなったらそれ以降確認する意味無いよね
            }
            // c = N - a - bじゃん
            if 10000*a+5000*b+1000*(n-a-b) > y {
                break // 10000*a+5000*b+1000*c がYより大きくなったらそれ以降確認する意味無いよね
            }
            if 10000*a+5000*b+1000*(n-a-b) == y{
                return strconv.Itoa(a)+" "+strconv.Itoa(b)+" "+strconv.Itoa(n-a-b)
            }
        }
    }
    return "-1 -1 -1"
}

func print(ans string) {
    fmt.Println(ans)
}

これでテストが通る。
実行時間7ms。

実行時間6msへ

package main

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

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() {
    sc.Split(bufio.ScanWords)
    n := nextInt()
    y := nextInt()
    logic(n, y)
}

// string返すのをやめた
func logic(n, y int) {
    maxA := y/10000
    if y%10000 == 0 && maxA == n {
        fmt.Printf("%d 0 0", maxA)
        return
    }
    if maxA > n { // for文の中で判定してたものを外出し
        maxA = n
    }
    maxB := y/5000
    if y%5000 == 0 && maxB == n {
        fmt.Printf("0 %d 0", maxB)
        return
    }
    maxC := y/1000
    if y%1000 == 0 && maxC == n {
        fmt.Printf("0 0 %d", maxC)
        return
    }
    for a := 0; a < maxA+1; a++ {
        for b := 0; b < n-a; b++ { // bもn-aにすることで n以上かどうかを気にしなくてよくなる
            c := n - a - b // c を最初に計算しておく
            if 10000*a+5000*b+1000*c > y {
                break
            }
            if 10000*a+5000*b+1000*c == y{
                fmt.Printf("%d %d %d", a, b, c)
                return
            }
        }
    }
    fmt.Print("-1 -1 -1")
}

for文の中でいちいち判定してたのは外出し。
条件に一致すればfor文の終端をnにすればいいだけ。
n以上かどうかを判定するif文をほとんど抹殺できたのがよかった。

実行時間4ms

package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text()) // よくよく考えたらエラーの処理とか絶対いらない
    return i
}

func main() {
    sc.Split(bufio.ScanWords)
    n := nextInt()
    y := nextInt()
    logic(n, y)
}

func logic(n, y int) {
    maxA := y/10000
    if y%10000 == 0 && maxA == n {
        fmt.Printf("%d 0 0", maxA)
        return
    }
    if maxA > n {
        maxA = n
    }
    maxB := y/5000
    if y%5000 == 0 && maxB == n {
        fmt.Printf("0 %d 0", maxB)
        return
    }
    maxC := y/1000
    if y%1000 == 0 && maxC == n {
        fmt.Printf("0 0 %d", maxC)
        return
    }
    for a := 0; a < maxA+1; a++ {
        for b := 0; b < n-a; b++ {
            c := n - a - b
            // 10000*a+5000*b+1000*c > y の判定を抹殺
            // この判定させるくらいなら追加でfor文回ることを許容する方がいいのでは
            // という考えが頭をよぎった
            if 10000*a+5000*b+1000*c == y {
                fmt.Printf("%d %d %d", a, b, c)
                return
            }
        }
    }
    fmt.Print("-1 -1 -1")
}

これで4ms!!
10000*a+5000*b+1000*c > y を消したのは正直賭け。
考えた限りありえなかったけど、本当にそうなのかは全く自信ない。

ここまでやって得た教訓

  1. ifは減らしまくる
  2. 新しく変数を宣言するのをできるだけ避ける(最低限の変数でどうにかできないかを考える)
  3. 調査対象を絞りに絞る

長々と書きましたが以上