こんにちは。KOUKIです。
とあるWeb系企業で、Goエンジニアをやっています。
今回は、Goのループ処理でMapを使うと処理速度が劇的に上がることについて記事にしました。
何をするか
以下の2つの配列があるとします。
|
1 2 |
array1 := [5]{"a", "b", "c", "x", "z") array2 := [5]{"c", "d", "e", "f", "g"} |
この2つの配列の中で、共通の文字が存在すればtrueを、存在しなければfalseを返す関数を実装したいと思います。
具体的にいうと、下記のようにループ処理を実装することになると思います。
|
1 2 3 4 5 6 7 8 9 10 11 |
func containsCommonItem(array1, array2 [num]string) bool { for i := 0; i < len(array1); i++ { for j := 0; j < len(array2); j++ { if array1[i] == array2[j] { return true } } } return false } |
array1, array2を2重ループにして、チェックを行っています。
前述通り、重複した文字があればtrueを、なければfalseを返しています。
これでも問題ないのですが、Mapを使うと劇的に速くなります。
事前準備
適当な文字を返す関数を実装しておきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package main import ( "fmt" "math/rand" ) func randSeq(n int) string { b := make([]rune, n) for i := range b { b[i] = letters[rand.Intn(len(letters))] } return string(b) } func main() { fmt.Println(randSeq(1)) fmt.Println(randSeq(2)) fmt.Println(randSeq(3)) fmt.Println(randSeq(4)) fmt.Println(randSeq(5)) fmt.Println(randSeq(6)) } |
randSeq関数のパラメータは、何文字返すかを指定します。
|
1 2 3 4 5 6 7 |
$ go run test1/main.go g jW Pji TzCU iTXpx jVFoRo |
この関数は、ランダムな文字列の配列を作るのに便利です。
この関数は、1000000要素の配列に「6文字のランダム文字列」を埋め込む処理に利用します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package main import ( "fmt" "math/rand" "time" ) const ( num = 1000000 ) var ( letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") array1 [num]string array2 [num]string ) func randSeq(n int) string { b := make([]rune, n) for i := range b { b[i] = letters[rand.Intn(len(letters))] } return string(b) } func init() { rand.Seed(time.Now().UnixNano()) for i := 0; i < num; i++ { array1[i] = randSeq(5) array2[i] = randSeq(5) } } func main(){} |
Mapの実装
それでは、Mapでループ処理を実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
func containsCommonItem2(array1, array2 [num]string) bool { myMap := make(map[string]bool, len(array1)) for i := 0; i < len(array1); i++ { if !myMap[array1[i]] { item := array1[i] myMap[item] = true } } for j := 0; j < len(array2); j++ { if myMap[array2[j]] { return true } } return false } |
容量を指定したmyMap変数を宣言し、array1の要素をループで格納しています。
その後、array2をループで回してmyMapに合致する要素がないか検索しています。
これだけ？と思われるかもしれませんが、これがめちゃくちゃ早いです。
ちなみにこんな書き方も可能です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
func containsCommonItem3(array1, array2 [num]string) bool { myMap := make(map[string]bool, len(array1)) for i := 0; i < len(array1); i++ { if !myMap[array1[i]] { item := array1[i] myMap[item] = true } } for _, arr := range array2 { _, ok := myMap[arr] if ok { return true } } return false } |
計測
計測用のコードを追加して、プログラムを起動してみましょう。
念の為、ここまで実装したコードを載せておきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
package main import ( "fmt" "math/rand" "time" ) const ( num = 1000000 ) var ( letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") array1 [num]string array2 [num]string ) func randSeq(n int) string { b := make([]rune, n) for i := range b { b[i] = letters[rand.Intn(len(letters))] } return string(b) } func init() { rand.Seed(time.Now().UnixNano()) for i := 0; i < num; i++ { array1[i] = randSeq(5) array2[i] = randSeq(5) } } func containsCommonItem(array1, array2 [num]string) bool { now := time.Now() for i := 0; i < len(array1); i++ { for j := 0; j < len(array2); j++ { if array1[i] == array2[j] { fmt.Println("containsCommonItem1 took time: ", time.Now().Sub(now).Milliseconds(), "ms", ) return true } } } fmt.Println("containsCommonItem1 took time: ", time.Now().Sub(now).Milliseconds(), "ms", ) return false } func containsCommonItem2(array1, array2 [num]string) bool { now := time.Now() myMap := make(map[string]bool, len(array1)) for i := 0; i < len(array1); i++ { if !myMap[array1[i]] { item := array1[i] myMap[item] = true } } for j := 0; j < len(array2); j++ { if myMap[array2[j]] { fmt.Println("containsCommonItem2 took time: ", time.Now().Sub(now).Milliseconds(), "ms", ) return true } } fmt.Println("containsCommonItem2 took time: ", time.Now().Sub(now).Milliseconds(), "ms", ) return false } func containsCommonItem3(array1, array2 [num]string) bool { now := time.Now() myMap := make(map[string]bool, len(array1)) for i := 0; i < len(array1); i++ { if !myMap[array1[i]] { item := array1[i] myMap[item] = true } } for _, arr := range array2 { _, ok := myMap[arr] if ok { fmt.Println("containsCommonItem3 took time: ", time.Now().Sub(now).Milliseconds(), "ms", ) return true } } fmt.Println("containsCommonItem3 took time: ", time.Now().Sub(now).Milliseconds(), "ms", ) return false } func main() { containsCommonItem(array1, array2) containsCommonItem2(array1, array2) containsCommonItem3(array1, array2) } |
1回目
|
1 2 3 4 |
$ go run test1/main.go containsCommonItem1 took time: 1119 ms containsCommonItem2 took time: 180 ms containsCommonItem3 took time: 155 ms |
2回目
|
1 2 3 4 |
$ go run test1/main.go containsCommonItem1 took time: 5825 ms containsCommonItem2 took time: 299 ms containsCommonItem3 took time: 338 ms |
3回目
|
1 2 3 4 |
$ go run test1/main.go containsCommonItem1 took time: 419 ms containsCommonItem2 took time: 234 ms containsCommonItem3 took time: 205 ms |
4回目
|
1 2 3 4 |
$ go run test1/main.go containsCommonItem1 took time: 5431 ms containsCommonItem2 took time: 198 ms containsCommonItem3 took time: 159 ms |
5回目
|
1 2 3 4 |
$ go run test1/main.go containsCommonItem1 took time: 661 ms containsCommonItem2 took time: 218 ms containsCommonItem3 took time: 158 ms |
おわりに
いかがでしょうか？
最大で17倍の速度差が出ています。ループを回すときはMapを検討すると幸せになりますね。
もっと効率の良いループ処理があれば、追記します^^
それでは、また!
にほんブログ村
コメントを残す
コメントを投稿するにはログインしてください。