前職のずいぶん前の話だけど、Goで展開しながらappendするコードを提案されたことがある。 結合後に逆順にする方が早いと言ったけど伝わらなかった。なので測ってメモしておく。

Goのsliceで先頭方向で要素を繰り返し付加するのであれば、最後に逆順にするとだいたい早い。 (要素のアロケーションとか他の時間に埋もれる可能性は多々ある)

go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import (
        "fmt"
        "testing"
)

func BenchmarkReverseAppend(b *testing.B) {
        src := make([]string, 10)
        for i := 0; i < 10; i++ {
                src = append(src, fmt.Sprintf("sec-%d", i))
        }
        for i := 0; i < b.N; i++ {
                path := []string{}
                for _, s := range src {
                        path = append([]string{s}, path...)
                }
        }
}

func BenchmarkReverseAppended(b *testing.B) {
        src := []string{}
        for i := 0; i < 10; i++ {
                src = append(src, fmt.Sprintf("sec-%d", i))
        }
        for i := 0; i < b.N; i++ {
                l := len(src)
                path := make([]string, l)
                for _, s := range src {
                        path = append(path, s)
                }
                for i := 0; i < l/2; i++ {
                        path[i], path[l-1-i] = path[l-1-i], path[i]
                }
        }
}
go test -bench .
goos: linux
goarch: amd64
BenchmarkReverseAppend-4          200000              6429 ns/op
BenchmarkReverseAppended-4       3000000               524 ns/op
PASS
ok      _/home/mkanai/works/sample      3.451s