Go - ISUCON5予選でスコア34000を出す方法 - Qiita
Goで下記のようなsliceの先頭にひたすらオブジェクトを追加する処理を書く際は、不必要に長いsliceにならないよう注意しましょう。負荷が非常に高い処理になります。
hoge := []int{}http://qiita.com/y_matsuwitter/items/771020ebb68c07053548
for _, comment := range comments {
hoge = append([]int{comment.ID}, hoge...)
}
append は第一引数のスライスに第二引数以降の可変個アイテムを追加する関数です。なるべく呼ばれない実装が良いです。どうしても多いアイテムを扱う場合は出来れば以下の様に書くのが良いです。
参考: https://blog.golang.org/slices
hoge := make([]int, 0, len(comments))
for i := 0; i < len(comments); i++ {
hoge = append(hoge, comment.ID)
}
注意)これは逆順です
もしくは
hoge := make([]int, len(comments), len(comments))
for i := 0; i < len(comments); i++ {
hoge[i] = comment.ID
}
注意)これは逆順です
golang の append はキャパシティ内であれば hoge は増幅せずに戻り値として返されます。つまり先に make で確保しておけば append でのアローケートは1回となります。次に以下のコード見て下さい。リンク先のコードと以下のコードは少しの違いしかないですが、実は物凄い違いがあります。一見、単純な間違いに見えますが実は大きな落とし穴があります。
hoge := []int{}
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
上記リンクのコードと引数の順番が違うだけに見え、処理性能も変わらない様に見えます。しかし上記のリンクにあるコードの場合だと、ループ毎に新しいスライスが作られ、それに対して増えつつある hoge を追加し、さらに hoge を壊して代入する形になります。つまり O(N^2) 回処理されます。
先頭に追加するのであれば以下の様に書くべきです。
hoge := make([]int, len(comments), len(comments))
l := len(comments)
for i, j := l - 1, 0; i >= 0; i-- {
hoge[i] = comments[j].ID
j++
}
ベンチマークを取ってみると
package foo
import (
"testing"
)
type comment struct {
ID int
}
var (
comments []comment
)
func ready() {
comments = make([]comment, 60000, 60000)
for i := 0; i < len(comments); i++ {
comments[i].ID = i
}
}
func BenchmarkTest1(b *testing.B) {
ready()
b.ResetTimer()
hoge := []int{}
for _, comment := range comments {
hoge = append([]int{comment.ID}, hoge...)
}
}
func BenchmarkTest2(b *testing.B) {
ready()
b.ResetTimer()
hoge := make([]int, len(comments), len(comments))
l := len(comments)
for i, j := l-1, 0; i >= 0; i-- {
hoge[i] = comments[j].ID
j++
}
}
testing: warning: no tests to run
PASS
BenchmarkTest1-4 1 7712771200 ns/op
BenchmarkTest2-4 2000000000 0.00 ns/op
ok _/c_/dev/arrr 7.949s
60000個の処理を行うと、2000000000倍(2億倍)の差が付くようです。
