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
}
このコードの場合
strings.Splitで文字列の先頭から終端まで検査しながらループwordsで単語数分ループ(W)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
}
- パターン文字列長分ループ
- 検査対象文字列に対して
Splitでマッチングループ 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 文字分しか処理が行われません。
- 文字列長分ループ
だけとなります。一見読みづらいかもしれませんが
- コピーを減らす
- ループ回数を減らす
これを守ると速いプログラムが書ける様になります。
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
}
