2015/09/28

Go - ISUCON5予選でスコア34000を出す方法 - Qiita

Goで下記のようなsliceの先頭にひたすらオブジェクトを追加する処理を書く際は、不必要に長いsliceにならないよう注意しましょう。負荷が非常に高い処理になります。

hoge := []int{}
for _, comment := range comments {
    hoge = append([]int{comment.ID}, hoge...)
}
http://qiita.com/y_matsuwitter/items/771020ebb68c07053548

append は第一引数のスライスに第二引数以降の可変個アイテムを追加する関数です。なるべく呼ばれない実装が良いです。どうしても多いアイテムを扱う場合は出来れば以下の様に書くのが良いです。

参考: https://blog.golang.org/slices

hoge := make([]int0len(comments))
for i := 0; i < len(comments); i++ {
    hoge = append(hoge, comment.ID)
}

注意)これは逆順です

もしくは

hoge := make([]intlen(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([]intlen(comments), len(comments))
l := len(comments)
for i, j := l - 10; 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, 6000060000)
    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([]intlen(comments), len(comments))
    l := len(comments)
    for i, j := l-10; 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億倍)の差が付くようです。

Posted at 14:59 | WriteBacks () | Edit
Edit this entry...

wikieditish message: Ready to edit this entry.






















A quick preview will be rendered here when you click "Preview" button.