2015/09/28

Recent entries from same category

  1. golang では変数の宣言位置が大事
  2. golang と Generics と私
  3. レーベンシュタイン距離を使ったあいまい grep コマンド「lsdgrep」作ってみた
  4. golang オフィシャル謹製のパッケージ依存解決ツール「dep」
  5. Re: Go でシングルバイナリな Web アプリを開発しているときに webpack --watch をうまいところやる

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([]intlen(comments))
for i := 0; i < len(comments); i++ {
    hoge = append(hoge, comment.ID)
}

注意)これは逆順です

もしくは

hoge := make([]intlen(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))
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, 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([]intlen(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億倍)の差が付くようです。


blog comments powered by Disqus