こんにちは。KOUKIです。
Go言語で集合演算処理のプログラムを作ってみましょう!
ワークスペースの作成
ワークスペースを作成しましょう。
1 2 3 4 5 |
mkdir culc cd culc touch culc.go touch culc_test.go go mod init culc |
積集合
説明
一つのList(円)を集合と定義します。
積集合は、2つのListが重なり合った集合のことを指します。
実装
積集合の関数を作成します。
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 culc // 積集合 func CulcIntersection(l1, l2 []int) []int { s := make(map[int]struct{}, len(l1)) // list1をmap形式に変換 for _, data := range l1 { // struct{}{}何もない空のデータ s[data] = struct{}{} } r := make([]int, 0, len(l1)) for _, data := range l2 { // mapにデータがない場合は、スキップ // okにはデータの存在有無true/falseで入る if _, ok := s[data]; !ok { continue } // 積集合のデータを格納 r = append(r, data) } return r } |
上記のコードでは、引数にint型のListを渡しています。このListが集合です。
このプログラムが正しく動けば、l1とl2が重なっている値を抜き出せるはずです。
テスト
テストコードを書いて、確認してみましょう。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
package culc import ( "fmt" "testing" "github.com/magiconair/properties/assert" ) func TestCulcIntersection(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{3, 4, 5} result := CulcIntersection(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } |
List1を「1, 2, 3, 4, 5」、List2を「3, 4, 5, 6, 7」の集合にしたので、結果は「3, 4, 5」になるはずです。
1 2 3 4 5 6 |
$ go test -v ./... === RUN TestCulcIntersection Result: [3 4 5] --- PASS: TestCulcIntersection (0.00s) PASS ok culc 0.599s |
和集合
説明
和集合は、2つのListの集合に対して少なくともどちらか一方の集合に属する要素全体の集合のことを指します。要するに全部ということですが、重複値は許しません。
実装
List1とList2をmapに変換して、rangeで取り出します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// 和集合 func CulcUnion(l1, l2 []int) []int { s := make(map[int]struct{}, len(l1)) for _, data := range l1 { s[data] = struct{}{} } for _, data := range l2 { s[data] = struct{}{} } r := make([]int, 0, len(s)) for key, _ := range s { r = append(r, key) } return r } |
テスト
テストコードを実装します。
1 2 3 4 5 6 7 8 |
func TestCulcUnion(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{1, 2, 3, 4, 5, 6, 7} result := CulcUnion(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } |
List1を「1, 2, 3, 4, 5」、List2を「3, 4, 5, 6, 7」の集合にしたので、結果は「1, 2, 3, 4, 5, 6, 7」になるはずです。
実行してみましょう。
1 2 3 4 5 6 7 |
$ go test -v ./... ... === RUN TestCulcUnion Result: [1 2 3 4 5 6 7] --- PASS: TestCulcUnion (0.00s) PASS ok culc (cached) |
スライスは順番を保持しないのでテストが失敗する場合もありますが、出力にある「Result: [1 2 3 4 5 6 7]」を確認してください。
差集合
説明
差集合は、List1 に含まれているがList2 には含まれていない要素の集合のことです。
実装
和集合と似た感じで実装してみます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// 差集合 func CulcDifference(l1, l2 []int) []int { s := make(map[int]struct{}, len(l1)) for _, data := range l2 { s[data] = struct{}{} } r := make([]int, 0, len(l2)) for _, data := range l1 { if _, ok := s[data]; ok { continue } r = append(r, data) } return r } |
l1パラメータに、差分を出したい方のListを指定します。
テスト
テストコードを実装しましょう。
1 2 3 4 5 6 7 8 |
func TestCulcDifference(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{1, 2} result := CulcDifference(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } |
List1を「1, 2, 3, 4, 5」、List2を「3, 4, 5, 6, 7」の集合にしたので、結果は「1, 2」になるはずです。
1 2 3 4 5 6 |
$ go test -v ./... ... Result: [1 2] --- PASS: TestCulcDifference (0.00s) PASS ok culc 0.118s |
対称差集合
説明
対称差集合とは 2 つのListのどちらか片方だけに含まれる要素の集合のことです。
実装
これも和集合と似た感じで実装してみます。
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 |
// 対称差集合 func CulcSymmetricDifference(l1, l2 []int) []int { s1 := make(map[int]struct{}, len(l1)) s2 := make(map[int]struct{}, len(l2)) for _, data := range l1 { s1[data] = struct{}{} } for _, data := range l2 { s2[data] = struct{}{} } r := make([]int, 0, len(l1)) for _, data := range l1 { if _, ok := s2[data]; ok { continue } r = append(r, data) } for _, data := range l2 { if _, ok := s1[data]; ok { continue } r = append(r, data) } return r } |
うーん。なんかもっと効率の良い書き方があるかもしれないですね。
テスト
テストコードを実装しましょう。
1 2 3 4 5 6 7 8 |
func TestCulcSymmetricDifference(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{1, 2, 6, 7} result := CulcSymmetricDifference(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } |
List1を「1, 2, 3, 4, 5」、List2を「3, 4, 5, 6, 7」の集合にしたので、結果は「1, 2, 6, 7」になるはずです。
1 2 3 4 5 6 |
$ go test -v ./... ... Result: [1 2 6 7] --- PASS: TestCulcSymmetricDifference (0.00s) PASS ok culc (cached) |
補足: プログラムを早くする工夫
sliceやmapを定義するとき、makeでCapacityを指定しています。
1 2 3 |
// len(l1)がCapacity make(map[int]struct{}, len(l1)) make([]int, 0, len(l1)) |
こうすると、プログラムが結構早くなるのでおすすめです。
おわりに
もしかしたら、集合演算用のライブラリがあるのかも知れませんが、今回は手組みで実装してみました。
ライブラリはとても便利なのですが、使いすぎると自分でロジックを構築する力が衰えてきますよね^^;
たまには、こーいうのも良いです^^
それでは、また!
Go記事まとめ
ソースコード
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 |
package culc // 積集合 func CulcIntersection(l1, l2 []int) []int { s := make(map[int]struct{}, len(l1)) // list1をmap形式に変換 for _, data := range l1 { // struct{}{}何もない空のデータ s[data] = struct{}{} } r := make([]int, 0, len(l1)) for _, data := range l2 { // mapにデータがない場合は、スキップ // okにはデータの存在有無true/falseで入る if _, ok := s[data]; !ok { continue } // 積集合のデータを格納 r = append(r, data) } return r } // 和集合 func CulcUnion(l1, l2 []int) []int { s := make(map[int]struct{}, len(l1)) for _, data := range l1 { s[data] = struct{}{} } for _, data := range l2 { s[data] = struct{}{} } r := make([]int, 0, len(s)) for key, _ := range s { r = append(r, key) } return r } // 差集合 func CulcDifference(l1, l2 []int) []int { s := make(map[int]struct{}, len(l1)) for _, data := range l2 { s[data] = struct{}{} } r := make([]int, 0, len(l2)) for _, data := range l1 { if _, ok := s[data]; ok { continue } r = append(r, data) } return r } // 対称差集合 func CulcSymmetricDifference(l1, l2 []int) []int { s1 := make(map[int]struct{}, len(l1)) s2 := make(map[int]struct{}, len(l2)) for _, data := range l1 { s1[data] = struct{}{} } for _, data := range l2 { s2[data] = struct{}{} } r := make([]int, 0, len(l1)) for _, data := range l1 { if _, ok := s2[data]; ok { continue } r = append(r, data) } for _, data := range l2 { if _, ok := s1[data]; ok { continue } r = append(r, data) } return r } |
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 |
package culc import ( "fmt" "testing" "github.com/magiconair/properties/assert" ) func TestCulcIntersection(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{3, 4, 5} result := CulcIntersection(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } func TestCulcUnion(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{1, 2, 3, 4, 5, 6, 7} result := CulcUnion(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } func TestCulcDifference(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{1, 2} result := CulcDifference(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } func TestCulcSymmetricDifference(t *testing.T) { l1 := []int{1, 2, 3, 4, 5} l2 := []int{3, 4, 5, 6, 7} expected := []int{1, 2, 6, 7} result := CulcSymmetricDifference(l1, l2) assert.Equal(t, expected, result) fmt.Printf("Result: %v\n", result) } |
コメントを残す
コメントを投稿するにはログインしてください。