追記 (2022-06-12)

この記事はstrconv.Itoaを大量に使わないというタイトルで、strconv.Itoaを使うことが重い原因のように書いていましたが申し訳ありません、それは間違いだったので結論を直しています。

概要

Goで競プロをやるときにハマった事のメモです。

ABC233のEでTLEを出した時の対処となります。

結論

文字列の連結（r+="hoge"のような）をN>= 10⁵くらいより上のケースで使うとTLEになる場合があるので避ける。文字を結合したければ[]byteで扱うか、strings.Joinを利用すれば良い。strconv.Atoiとstrconv.Itoaは使っても問題になることは少ないはず。

詳細

https://atcoder.jp/contests/abc233/submissions/28133985

以下TLEになったソースです。

func main() {
 
    defer flush()
 
    o := ""
 
    x := ns()
    ns := make([]int, len(x))
    sum := 0
    for i, v := range x {
        ns[i] = atoi(string(v))
        sum += ns[i]
    }
    rs := make([]int, len(ns)+1)
    t := 0
    for i := 0; i < len(ns); i++ {
        rs[i] = (sum + t) % 10
        t = (sum + t) / 10
        sum -= ns[len(ns)-i-1]
    }
    if t != 0 {
        o += itoa(t)
    }
    for i := len(ns) - 1; i >= 0; i-- {
        o += itoa(rs[i])
    }
 
    out(o)
}

自作関数を所々使ってますが、入出力はバッファリングしているのと、あとstrconv.Atoi、strconv.Itoaはそれぞれエラー処理が煩雑なのと書く量を減らすためatoi,itoaにラップしてます。

メインのロジックは間違っていないと思っており(実際に間違っていませんでした)、atoiとitoaのどちらかがまずいのだろうと目星をつけました。

atoiの方は

        ns[i] = atoi(string(v))

を

        ns[i] = int(v) - 48

に変えましたが効果はありませんでした。それはそのはずで、実際にstrconv.Atoiの中でも

        n := 0
        for _, ch := range []byte(s) {
            ch -= '0'
            if ch > 9 {
                return 0, &NumError{fnAtoi, s0, ErrSyntax}
            }
            n = n*10 + int(ch)
        }

上記のような処理を内部でやっているので実質やっていることは同じです。

問題はitoaの方で500000個の要素に対し全てにitoaをやるのはかかる時間が大きすぎるようです。ここは最終的に答えが出力されれば良いので、

    if t != 0 {
        o += itoa(t)
    }
    for i := len(ns) - 1; i >= 0; i-- {
        o += itoa(rs[i])
    }
 
    out(o)

ここをoutに対してoutwolnという関数(without ln、いい名称ではないがlnをつけるケースがほとんどなので…)を作り

func out(v ...interface{}) {
    _, e := fmt.Fprintln(wtr, v...)
    if e != nil {
        panic(e)
    }
}
func outwoln(v ...interface{}) {
    _, e := fmt.Fprint(wtr, v...)
    if e != nil {
        panic(e)
    }
}

以下のようにすればACでした！

    if t != 0 {
        outwoln(t)
    }
    for i := len(ns) - 1; i >= 0; i-- {
        outwoln(rs[i])
    }
    out("")

改めてstrconv.Itoaの中身を見てみましたが処理が数値が10未満、100未満、それ以上と別れていて100未満の場合は以下のように文字列から取っているようです。面白いですね。早そうですが毎回スライスを扱うので大量に行うと重いようです。

func small(i int) string {
    if i < 10 {
        return digits[i : i+1]
    }
    return smallsString[i*2 : i*2+2]
}

const smallsString = "00010203040506070809" +
    "10111213141516171819" +
    "20212223242526272829" +
    "30313233343536373839" +
    "40414243444546474849" +
    "50515253545556575859" +
    "60616263646566676869" +
    "70717273747576777879" +
    "80818283848586878889" +
    "90919293949596979899"

const digits = "0123456789abcdefghijklmnopqrstuvwxyz"

（追記 2020-06-16）と記事を書いた当初はstrconv.Itoaを悪者にしていましたが、初めのソースを以下のように直すと普通に通りました。

    r := make([]string, len(ns))
    for i := len(ns) - 1; i >= 0; i-- {
        r[len(ns)-i-1] = itoa(rs[i])
    }
    o += strings.Join(r, "")

原因は文字列結合だったようです。

改めてなぜ文字列結合が遅いかを調べたところ、以下にわかりやすい解説がありました。毎回文字列を作り直しているんですね…。O(N²)になるのかと思います。

Goでは文字列連結はコストの高い操作

高速にするには[]byteで扱うのが正解、次点でstrings.Join()となります。

Goの文字列結合のパフォーマンス

なので最終的にこうして

    r := make([]byte, len(ns))
    for i := len(ns) - 1; i >= 0; i-- {
        r[len(ns)-i-1] = byte('0' + rs[i])
    }
    o += string(r)

今までで一番早くなりました！文字列結合にしていると2s以上かかっていたものが37msですみました。

Go Notes

文字列の連結をしない

追記 (2022-06-12)

概要

結論

詳細