http://mattn.kaoriya.net/software/lang/go/20150928144704.htm
こちらの記事を参考にベンチマークをいくつか追加して計測してみました。
makeせずにスライスの先頭に追加を繰り返すとO(N^2)かかる
banck1_test.go
package foo
import(
"testing"
)
type comment struct {
ID int
}
var (
comments []comment
)
func ready() {
comments = make([]comment, 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 := []int{}
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
}
func BenchmarkTest3(b *testing.B) {
ready()
b.ResetTimer()
hoge := make([]int, len(comments))
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
}
func BenchmarkTest4(b *testing.B) {
ready()
b.ResetTimer()
hoge := make([]int, len(comments))
l := len(comments)
for i, j := l-1, 0; i >= 0;i-- {
hoge[i] = comments[j].ID
j++
}
}
結果1
testing: warning: no tests to run
PASS
BenchmarkTest1-4 1 4000805357 ns/op 14635456312 B/op 122698 allocs/op
BenchmarkTest2-4 2000000000 0.00 ns/op 0 B/op 0 allocs/op
BenchmarkTest3-4 2000000000 0.00 ns/op 0 B/op 0 allocs/op
BenchmarkTest4-4 2000000000 0.00 ns/op 0 B/op 0 allocs/op
参考にさせていただいた記事の通り、60000個の処理を行うと、2000000000倍(2億倍)の差が付きました。
理由は
ループ毎に新しいスライスが作られ、それに対して増えつつある hoge を追加し、さらに hoge を壊して代入する形になります。つまり O(N^2) 回処理されます。
ということです。
O(N^2)以外の3つの比較
Nを60000000にして、BenchmarkTest1をコメントアウトして実行してみました。
bench2_test.go
package foo
import(
"testing"
)
type comment struct {
ID int
}
var (
comments []comment
)
func ready() {
comments = make([]comment, 60000000)
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 := []int{}
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
}
func BenchmarkTest3(b *testing.B) {
ready()
b.ResetTimer()
hoge := make([]int, len(comments))
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
}
func BenchmarkTest4(b *testing.B) {
ready()
b.ResetTimer()
hoge := make([]int, len(comments))
l := len(comments)
for i, j := l-1, 0; i >= 0;i-- {
hoge[i] = comments[j].ID
j++
}
}
結果2
BenchmarkTest2-4 1 1301906279 ns/op 2526498184 B/op 69 allocs/op
BenchmarkTest3-4 1 2040929539 ns/op 3939434752 B/op 9 allocs/op
BenchmarkTest4-4 2000000000 0.08 ns/op 0 B/op 0 allocs/op
makeしてもしなくても、末尾でも、appendを60000000回繰り返すと2億倍の差がでました。
b.Nを使って全部比較
bench3_test.go
package foo
import(
"testing"
)
type comment struct {
ID int
}
var (
comments []comment
)
func ready(n int) {
comments = make([]comment, n)
for i := 0; i < len(comments); i++ {
comments[i].ID = i
}
}
func BenchmarkTest1(b *testing.B) {
ready(b.N)
b.ResetTimer()
hoge := []int{}
for _, comment := range comments {
hoge = append([]int{comment.ID}, hoge...)
}
}
func BenchmarkTest2(b *testing.B) {
ready(b.N)
b.ResetTimer()
hoge := []int{}
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
}
func BenchmarkTest3(b *testing.B) {
ready(b.N)
b.ResetTimer()
hoge := make([]int, len(comments))
for _, comment := range comments {
hoge = append(hoge, comment.ID)
}
}
func BenchmarkTest4(b *testing.B) {
ready(b.N)
b.ResetTimer()
hoge := make([]int, len(comments))
l := len(comments)
for i, j := l-1, 0; i >= 0;i-- {
hoge[i] = comments[j].ID
j++
}
}
func BenchmarkTest5(b *testing.B) {
ready(b.N)
b.ResetTimer()
hoge := make([]int, len(comments))
l := len(comments)
for i, j := l-1, 0; i >= 0;i-- {
hoge[i] = comments[i].ID
j++
}
}
結果3
BenchmarkTest1-4 200000 303425 ns/op 804081 B/op 2 allocs/op
BenchmarkTest2-4 50000000 24.1 ns/op 40 B/op 0 allocs/op
BenchmarkTest3-4 100000000 44.7 ns/op 65 B/op 0 allocs/op
BenchmarkTest4-4 300000000 4.81 ns/op 8 B/op 0 allocs/op
BenchmarkTest5-4 500000000 4.67 ns/op 8 B/op 0 allocs/op
appendでスライスの先頭に繰り返し追加するのはやめたほうがいい。
末尾に追加するならあんまり変わらないけど、makeでallocateしておいてforループで追加していくのが良さそう。