こんにちは。KOUKIです。
とあるWeb系企業で、Goエンジニアとして色々なAPIを実装しています。
今回は、Golangによるデータ検索のアルゴリズムについて記事にしました。
モジュール
fakerを使って、テストデータを作成します。
|
1 |
go get -u github.com/bxcodec/faker/v3 |
検索エンジンの実装
EmailとNameを保持したUser構造体からEmailを検索して、Nameを返却するプログラムを実装しましょう。
逐次処理で実装
最初は逐次処理でユーザーを検索するアルゴリズムを実装します。
|
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 |
package main import ( "fmt" "os" "time" "github.com/bxcodec/faker/v3" ) type User struct { Email string Name string } var Database []User func init() { // ユーザー3000000人分 for i := 0; i < 3000000; i++ { user := User{ Email: faker.Email(), Name: faker.Name(), } Database = append(Database, user) } specificedUser := User{ Email: "selfnote@work", Name: "selfnote", } Database = append(Database, specificedUser) } type Worker struct { database []User } func NewWorker(database []User) *Worker { return &Worker{database: database} } func (w *Worker) Find(email string) *User { for i := range w.database { user := &w.database[i] if user.Email == email { return user } } return nil } func main() { email := os.Args[1] w := NewWorker(Database) start := time.Now() fmt.Printf("Looking for %s\n", email) user := w.Find(email) if user != nil { fmt.Printf("The email %s is owned by %s\n", email, user.Name) } else { fmt.Printf("The email %s was not found\n", email) } fmt.Printf("It took %d ms\n", time.Since(start).Milliseconds()) } |
Inif関数ではfakerを使ってテストデータを3000000件追加しており、WorkerのFineメソッドにEmailを渡すことでデータ検索をできるようにしています。
また、プログラム実行時に引数としてEmailを渡せるように、osパッケージのArgsメソッドを使用しています。
|
1 2 3 4 5 6 7 8 9 |
$ go run main.go selfnote@work Looking for selfnote@work The email selfnote@work is owned by selfnote It took 7 ms $ go run main.go invalidemail Looking for invalidemail The email invalidemail was not found It took 8 ms |
Channelバージョン
次に、Channelバージョンを実装します。
|
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 |
package main import ( "fmt" "os" "time" "github.com/bxcodec/faker/v3" ) type User struct { Email string Name string } var Database []User func init() { // ユーザー3000000人分 for i := 0; i < 3000000; i++ { user := User{ Email: faker.Email(), Name: faker.Name(), } Database = append(Database, user) } specificedUser := User{ Email: "selfnote@work", Name: "selfnote", } Database = append(Database, specificedUser) } type Worker struct { ch chan *User database []User } func NewWorker(ch chan *User, database []User) *Worker { return &Worker{ch: ch, database: database} } func (w *Worker) Find(email string) { for i := range w.database { user := &w.database[i] if user.Email == email { w.ch <- user } } } func main() { email := os.Args[1] ch := make(chan *User) start := time.Now() fmt.Printf("Looking for %s\n", email) go NewWorker(ch, Database).Find(email) select { case user := <-ch: fmt.Printf("The email %s is owned by %s\n", email, user.Name) case <-time.After(15 * time.Second): fmt.Printf("The email %s was not found\n", email) } fmt.Printf("It took %d ms\n", time.Since(start).Milliseconds()) } |
Channelの場合は、goroutineでFindメソッドを実行します。
Selectでは、caseを使ってチャネルからデータを取得しています。便利なのが、上記のコードの様にtimeoutを設定できることです。15秒以上経ってもデータが検索できない場合はtimeoutにしました。
|
1 2 3 4 5 6 7 8 9 |
$ go run main.go selfnote@work Looking for selfnote@work The email selfnote@work is owned by selfnote It took 8 ms $ go run main.go invalidemail Looking for invalidemail The email invalidemail was not found It took 15004 ms |
逐次処理と比較しても実行速度はあまり変わりませんね。
Goroutineを複数にしてみる
Goroutineを複数にして処理を実行してみましょう。
|
1 2 3 4 5 6 7 |
func main() { ... go NewWorker(ch, Database[:1500000]).Find(email) go NewWorker(ch, Database[1500000:]).Find(email) ... } |
|
1 2 3 4 |
$ go run main.go selfnote@work Looking for selfnote@work The email selfnote@work is owned by selfnote It took 5 ms |
おお、3ms早くなりましたね!
Nameを与える
GoroutineにNameを与えてみましょう。
|
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 |
package main import ( "fmt" "os" "time" "github.com/bxcodec/faker/v3" ) type User struct { Email string Name string } var Database []User func init() { // ユーザー3000000人分 for i := 0; i < 3000000; i++ { user := User{ Email: faker.Email(), Name: faker.Name(), } Database = append(Database, user) } specificedUser := User{ Email: "selfnote@work", Name: "selfnote", } Database = append(Database, specificedUser) } type Worker struct { ch chan *User database []User name string } func NewWorker(ch chan *User, database []User, name string) *Worker { return &Worker{ch: ch, database: database, name: name} } func (w *Worker) Find(email string) { for i := range w.database { user := &w.database[i] if user.Email == email { fmt.Println(">>", w.name) w.ch <- user } } } func main() { email := os.Args[1] ch := make(chan *User) start := time.Now() fmt.Printf("Looking for %s\n", email) go NewWorker(ch, Database[:1000000], "#1").Find(email) go NewWorker(ch, Database[1000000:2000000], "#2").Find(email) go NewWorker(ch, Database[2000000:], "#3").Find(email) select { case user := <-ch: fmt.Printf("The email %s is owned by %s\n", email, user.Name) case <-time.After(15 * time.Second): fmt.Printf("The email %s was not found\n", email) } fmt.Printf("It took %d ms\n", time.Since(start).Milliseconds()) } |
|
1 2 3 4 5 |
$ go run main.go selfnote@work Looking for selfnote@work >> #3 The email selfnote@work is owned by selfnote It took 4 ms |
#3のgoroutineでデータを取得したことがわかりますね。goroutineを一つ増やしたので、データ取得も1ms早くなりました。
おわりに
実際の現場でもデータ検索を実装する機会はたくさんあります。
その時、速度を意識してアルゴリズムを実装してみるのもいいかもしれません。
例えば、stringsパッケージのContainsメソッドを使って検索処理を実装してみましょう。
|
1 2 3 4 5 6 7 8 9 |
func (w *Worker) Find(email string) { for i := range w.database { user := &w.database[i] if strings.Contains(user.Email, email) { fmt.Println(">>", w.name) w.ch <- user } } } |
|
1 2 3 4 5 6 7 8 9 10 11 |
$ go run main.go selfnote@work Looking for selfnote@work >> #3 The email selfnote@work is owned by selfnote It took 23 ms $ go run main.go selfnote@work Looking for selfnote@work >> #3 The email selfnote@work is owned by selfnote It took 28 ms |
意外なことに7倍くらい処理が遅くなってしまいました!
処理を実装するときは、色々なパターンで実装し、testingパッケージのBenchmarkで速度計測した方が良さそうですね。
それでは、また!
にほんブログ村
コメントを残す
コメントを投稿するにはログインしてください。