Go実装の最適化ゲームをしてみた
概要
同僚が「このコード書ける Java
のライブラリない?」 と言ってきたので、
Go
で実装し返しました。(遊び)
書いたコードがひどそうだったので、最適化をするゲームをしてみました。
結論、あまりいい感じではないですね。
お題
配列が与えられた際に、 指定した最小/最大サイズの文字列を前から順に結合して取得したい とのことでした。(何言ってるかわからない)
例
例を挙げるとわかりやすいかと思います。
input: [a, b, c, d, e] => output: [ab, abc, abcd, abcde, bc, bcd, bcde, cd, cde, de]
実装
パート1
まず、最初に思いついて書いたコードが下記になります。
なんかこう色々まずそうです。
Go Playground
func initialShingle(min, max int, arr []string) []string { res := []string{} if min > max { return res } for i := 0; i < len(arr); i++ { cmin := min for j := i; j+cmin < len(arr)+1; j++ { if len(arr[i:j+cmin]) > max { break } var s string for _, v := range arr[i : j+cmin] { s += v } res = append(res, s) } } return res }
閑話休題
とりあえず、動作確認のためテストコードを書きます。
min/maxの値の境界値等を Table Drive Test
で記載しました。
https://github.com/midorigreen/shingle/blob/master/main_test.go#L35
var cases = []struct { in in out []string }{ { in: in{min: 2, max: 1, arr: []string{"a", "b", "c", "d", "e"}}, out: []string{}, }, { in: in{min: 2, max: 2, arr: []string{"a", "b", "c", "d", "e"}}, out: []string{"ab", "bc", "cd", "de"}, }, { in: in{min: 2, max: 3, arr: []string{"a", "b", "c", "d", "e"}}, out: []string{"ab", "abc", "bc", "bcd", "cd", "cde", "de"}, }, { in: in{min: 2, max: 5, arr: []string{"a", "b", "c", "d", "e"}}, out: []string{"ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde", "de"}, }, { in: in{min: 2, max: 100, arr: []string{"a", "b", "c", "d", "e"}}, out: []string{"ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde", "de"}, }, } func TestInitialShingle(t *testing.T) { for _, c := range cases { res := initialShingle(c.in.min, c.in.max, c.in.arr) equal(t, res, c.out) } }
ベンチマークも書いたので、この結果が元になります。
% go test -benchmem -run=^$ github.com/midorigreen/shingle -bench ^BenchmarkInitialShingle$ goos: darwin goarch: amd64 pkg: github.com/midorigreen/shingle BenchmarkInitialShingle-4 3 388369200 ns/op 354791952 B/op 4621681 allocs/op PASS ok github.com/midorigreen/shingle 1.513s
パート2
alloc回数を減らすために、返却値の初期化を1回にします。
Go Playground
func shingle2(min, max int, arr []string) []string { // 省略 // for alloc array maxLen := len(arr) resLen := 0 for maxLen > 0 { resLen += maxLen maxLen-- } res := make([]string, resLen) // 省略 }
ベンチマーク結果
% go test -bench . -benchmem goos: darwin goarch: amd64 pkg: github.com/midorigreen/shingle BenchmarkInitialShingle-4 3 364788315 ns/op 354790757 B/op 4621679 allocs/op BenchmarkShingle2-4 3 484458838 ns/op 355455082 B/op 4621651 allocs/op PASS ok github.com/midorigreen/shingle 4.093s
悪くなってますね..
パート3
slice->stringの処理で文字列結合をしている部分を修正しました。
strings.Join([]string, string)
を使ってます。
Go Playground
func shingle3(min, max int, arr []string) []string { // 省略 res = append(res, strings.Join(arr[i:j+cmin], "")) // 省略 }
% go test -bench . -benchmem goos: darwin goarch: amd64 pkg: github.com/midorigreen/shingle BenchmarkInitialShingle-4 5 330830989 ns/op 354791379 B/op 4621680 allocs/op BenchmarkShingle2-4 5 332415947 ns/op 355455014 B/op 4621651 allocs/op BenchmarkShingle3-4 20 59744819 ns/op 27479328 B/op 186132 allocs/op PASS ok github.com/midorigreen/shingle 7.958s
速度もalloc回数も改善されました。
(補足) strings.Join()関数
実際の実装を見ると、以下の形になってます。
len(array)<=3
までは+で結合している- それ以降は、まずスライス長を確保している
- 結合するのではなくstringをbyte配列にcopyしている
- copyはstring->[]byteへコピーできる模様 doc
(As a special case, it also will copy bytes from a string to a slice of bytes.)
// Join concatenates the elements of a to create a single string. The separator string // sep is placed between elements in the resulting string. func Join(a []string, sep string) string { switch len(a) { case 0: return "" case 1: return a[0] case 2: // Special case for common small values. // Remove if golang.org/issue/6714 is fixed return a[0] + sep + a[1] case 3: // Special case for common small values. // Remove if golang.org/issue/6714 is fixed return a[0] + sep + a[1] + sep + a[2] } n := len(sep) * (len(a) - 1) for i := 0; i < len(a); i++ { n += len(a[i]) } b := make([]byte, n) bp := copy(b, a[0]) for _, s := range a[1:] { bp += copy(b[bp:], sep) bp += copy(b[bp:], s) } return string(b) }
感想
あまりいい感じの改善にはならなかったですね。
結局、string結合がボトルネックになっていたのでそこを改善すれば、
速度的にはマシになりました。
strings.Join()の挙動とcopyの挙動を知れたのが収穫です。
(よく考えると、どこがネックになっているかの計測を第一にしないといけなかったですね)