Goでの計算量を減らす書き方
まず
こちらの記事は私が足りていないと思う所を重点的に勉強する。
onion7日間チャレンジのDay5になります。
詳しくはここの冒頭で書いてあるので気になる人は見てみてください。
Day5
Day5では計算量の減らし方を解説することにしました。
今回は7つの計算量の減らし方を紹介します。
インターンの面接で質問されて答えられなかったからやります...
mapを使ったfor文
これはfor文の中にfor文があるときなどに利用できるものです。
ループ回数が増えれば増えるほど多くなり計算量はO(n*m)になります。
しかし、最初にmapに入れておくことでforの処理を早くすることができます。
mapはO(1)で処理することができるので、計算量はO(n+m)になります。
mapに入れる操作はfor一回の操作より大きいため
データ量が少ない場合、mapを使った操作の方が大きくなることがあります。
コード
//forを二回使ったやり方O(n*m)
func NMAP(a1, target []int){
for _,a2 := range a1 {
for _,t := range target{
if a2 == t {
fmt.Print("")
}
}
}
}
//mapを使ったやり方O(n+m)
func MAP(a1, target []int){
a2 := make(map[int]struct{})
for _, n := range a1 {
a2[n] = struct{}{}
}
for _, t := range target {
if _, ok := a2[t]; ok {
fmt.Print("")
}
}
}
スライスに追加する際にメモリを先に確保
配列サイズが事前に分かっている場合、メモリを先に確保しておくと処理が早くなります。
その都度で容量を確保すると大きな配列を作って全要素を確保しなおすため、遅くなります。
コード
//先に容量を確保しない場合
func NCAP(){
var slice []int
for i:=0;i<1000000;i++{
slice = append(slice,i)
}
}
//先に容量を確保する場合
func CAP(){
slice := make([]int,0,1000000)
for i:=0;i<1000000;i++{
slice = append(slice,i)
}
}
文字列を結合するとき
+で文字列を結合する時、新しいメモリ領域を確保するため、遅くなります。
strings.Builderを使うと早くなるみたいです。
コード
// strings.Builderを使わない例
func NSB(){
var str1 string
words := []string{"hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go"}
for _, w := range words {
str1 += w + " "
}
}
// strings.Builderを使う例
func SB(){
words := []string{"hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go","hello", "world", "go"}
var builder strings.Builder
// あらかじめ必要なサイズを指定するとさらに効率的
builder.Grow(100)
for _, w := range words {
builder.WriteString(w)
builder.WriteString(" ")
}
}
参照渡し(pointer)を使用する
値渡しをする場合、コピーが作られます。
コピー対象が大きくなれば大きくなるほど遅くなります。
中身を変更してもいい場合はアドレスだけ渡すようにしましょう。
コード
func NPOINTER(b BigStruct){
b.data1[0] = 42 // コピー側の操作
}
func POINTER(b *BigStruct){
b.data1[0] = 42 // 実体の操作
}
//フィールドが多い構造体
//フィールドが少ないと実行速度はあまり変わらない
type BigStruct struct {
data1 [10000]int
data2 [10000]int
data3 [10000]int
data4 [10000]int
data5 [10000]int
data6 [10000]int
data7 [10000]int
data8 [10000]int
data9 [10000]int
data10 [10000]int
data11 [10000]int
data12 [10000]int
data13 [10000]int
data14 [10000]int
}
forループでコピーをしない
先ほどと同じでforループでrangeを使用するばあいもコピーします。
コピー対象が大きくなれば大きくなるほど遅くなります。
この時はインデックスだけ使って処理すると早くなります。
コード
func NINDEX(s []BigStruct){
for _,v := range s{
_ = v
}
}
func INDEX(s []BigStruct){
for i := range s{
_ = s[i].data1[0]
}
}
//フィールドが多い構造体
//フィールドが少ないと実行速度はあまり変わらない
type BigStruct struct {
data1 [10000]int
data2 [10000]int
data3 [10000]int
data4 [10000]int
data5 [10000]int
data6 [10000]int
data7 [10000]int
data8 [10000]int
data9 [10000]int
data10 [10000]int
data11 [10000]int
data12 [10000]int
data13 [10000]int
data14 [10000]int
}
bufioを使ってファイル処理
bufio パッケージは、データをまとめて（バッファリングして）読み書きすることで、システムコールの回数を劇的に減らし、I/Oパフォーマンスを向上させます。(Gemini参照)
コード
func NBUFIO() {
// 直接書き込むより...
f, _ := os.Create("file.txt")
f.WriteString("line 1\n")
f.WriteString("line 2\n")
}
func BUFIO() {
// bufioを使ってバッファリングする方が効率的
f, _ := os.Create("file.txt")
defer f.Close()
writer := bufio.NewWriter(f)
writer.WriteString("line 1\n")
writer.WriteString("line 2\n")
// バッファに残っている内容をディスクに書き込む
writer.Flush()
}
goroutineを使って処理
これは並行処理によって処理を早くする方法です。
詳しくはここで話しています↓
最後に処理速度を計算して出力
実際にやってみました。
皆さんも実際に実行してみて体感してください。
githubは以下になります。
今回のリポジトリ
並行処理のリポジトリ
結果
//今回の結果
go run main.go
map不使用 にかかった時間: 25.906661ms
map使用 にかかった時間: 92.868µs
capacityなし にかかった時間: 11.337323ms
capacityあり にかかった時間: 1.852728ms
string_builderを不使用 にかかった時間: 35.705µs
string_builderを使用 にかかった時間: 921ns
pointerを不使用 にかかった時間: 1.048013ms
pointerを使用 にかかった時間: 113ns
コピーでrangeを操作 にかかった時間: 912.922µs
INDindexでrangeを操作EX にかかった時間: 113ns
普通にfile読み込み にかかった時間: 209.191µs
bufioでfile読み込み にかかった時間: 106.427µs
//並行処理の結果
go run main.go
input create of image directory: ./output
input path of image directory: ./images
input size: 100 200
goroutine不使用 にかかった時間: 15.59309894s
input create of image directory: ./output
input path of image directory: ./images
input size: 100 200
goroutine使用 にかかった時間: 13.998766602s
感想
こんなんやらなくても作れればいいじゃんって思ってました。
ですが、大きいときは数10ms違っていて、それが実際のプロダクトでは何個もあるというのに気づいてから恐ろしくなりました。
もし一つで10ms変わるのが1000個あるプロジェクトがあったら1秒遅くなります。
たかが1秒と感じるかもしれませんが、Akamaiが発表した調査によると
・ページの表示速度が100ミリ秒低下すると、コンバージョン率が最大7.1%低下する。
・ページの表示速度が1秒低下すると、コンバージョン率が最大21.8%低下する。
・ページの表示速度が2秒低下すると、コンバージョン率が最大36.5%低下する。
と書いてあります。
やはり、計算量を意識して書くに越したことはないですね！
Discussion