Big Sky

Golang で言語処理100本ノックの No.3 の問題を解いてベンチマークとってみた - Qiita
http://qiita.com/megu_ma/items/01029c3ca24fb9820373

正規表現や strings.Trim 等はとても便利なのですが、いかんせん単一の関数呼び出しに対して真面目にループを回す作りになっており、戻り値がコピーされる前提の作りになっています。例えば

func answer1() []int {

    // 単語に分解
    words := strings.Split(sentence, " ")

    var pi []int
    for _, word := range words {
        word = strings.Trim(word, ",")
        word = strings.Trim(word, ".")
        // pi = append(pi, utf8.RuneCountInString(word))
        pi = append(pi, len(word))

    }

    return pi

}


このコードの場合

1. strings.Split で文字列の先頭から終端まで検査しながらループ
2. words で単語数分ループ(W)
3. strings.Trim で単語の長さ分ループ(W × 2)

という無駄なループが回ります。正規表現に至っても同じ。

func answer2() []int {

    // 文を正規表現で単語に分解
    words := regexp.MustCompile(`\s|"|,|\.`).Split(sentence, -1)

    var pi []int
    for _, word := range words {
        // 文末がスプリットされた場合、words の配列の最後に空文字が入る
        if word != "" {
            // pi = append(pi, utf8.RuneCountInString(word))
            pi = append(pi, len(word))
        }
    }

    return pi

}


1. パターン文字列長分ループ
2. 検査対象文字列に対して Split でマッチングループ
3. words で単語数分ループ(W)

となります。これを1度のループ(lenはカウントしない物とします)で回す事が出来ます。

func answer3() []int {

    var pi []int
    var prev, i int
    b := []byte(sentence)
    l := len(b)
    for i < l {
        for ; i < l; i++ {
            if ('a' <= b[i] && b[i] <= 'z') || ('A' <= b[i] && b[i] <= 'Z') {
                break
            }
        }
        if i < l {
            prev = i
            for ; i < l; i++ {
                if !(('a' <= b[i] && b[i] <= 'z') || ('A' <= b[i] && b[i] <= 'Z')) {
                    break
                }
            }
            pi = append(pi, i-prev)
        }
        i++
    }

    return pi

}


ループ内にループがあり、一見は二重ループが回っている様に見えますが、実際には文字列長に対して先頭位置から終端位置、つまりこのテストケース Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics. で言えば 94 文字分しか処理が行われません。

1. 文字列長分ループ

だけとなります。一見読みづらいかもしれませんが

• コピーを減らす
• ループ回数を減らす

これを守ると速いプログラムが書ける様になります。

PASS
BenchmarkAnswer1          300000              5340 ns/op
BenchmarkAnswer2          100000             21620 ns/op
BenchmarkAnswer3         3000000               552 ns/op
ok      _/C_/dev/go-bench       6.508s


僕の環境だとおよそ10倍速い結果となりました。

追記

methane さんがもうちょっと綺麗なのを書いてくれました。

func answer4(s string) []int {
    res := make([]int, 0, len(s)/6)
    cnt := 0
    for _, c := range s {
        switch {
        case 'a' <= c && c <= 'z', 'A' <= c && c <= 'Z':
            cnt++
        default:
            if cnt != 0 {
                res = append(res, cnt)
                cnt = 0
            }
        }
    }
    if cnt != 0 {
        res = append(res, cnt)
        cnt = 0
    }
    return res
}