先日、集合や族を扱うパッケージを書いていたところ、mapやsliceが混じった構造でどのようにEqual
を実装するかで少しハマりました。reflect.DeepEqual
の実装を見て解決したので備忘として整理します。
ちょうどGoで違うmapであることをテストする でも、同じような課題に遭遇された方がいたようです。
考え方
まず、mapのEqual
を実装するときに定義する2つのmapが等しい
は、大きく以下の2つになると思います。
- 中身の要素が同じmapは、等しい(ポインタが異なることは気にしない)
- 中身が同じでも、ポインタが異なれば、等しくない
それぞれ、以下のように比較できます。
1. 中身の要素が同じmapは、等しい(ポインタが異なることは気にしない)
この場合は、中身を比較すればいいので、reflect.DeepEqual
で簡潔に書くことができます。
2. 中身が同じでも、ポインタが異なれば、等しくない
こちらは中身を見る必要はなく、ポインタだけを比較します。
コード
上記それぞれ実装すると以下のようになります。
package main import ( "fmt" "reflect" ) func main() { m1 := map[int]int{ 1: 1, 2: 2, } m2 := map[int]int{ 1: 1, 2: 2, } fmt.Printf("%p\n%p\n", m1, m2) // 0x10444240 // 0x10444260 fmt.Print("1: ") if reflect.DeepEqual(m1, m2) { fmt.Println("same") } else { fmt.Println("different") } // 1: same fmt.Print("2: ") if reflect.ValueOf(m1).Pointer() == reflect.ValueOf(m2).Pointer() { fmt.Println("same") } else { fmt.Println("different") } // 2: different }
https://play.golang.org/p/tlVEfsHYojr
mapとsliceの組み合わせ
単純なmapの比較は、上記のDeepEqual
を使う場合が多いのですが、今回ハマったのは、以下のように集合Set
と集合族Family
を扱おうとしたときです。
※今回実装したかったのは、要素が同じ集合族は同じ(上記の1.のパターン)と見なしたかったため、1.のパターンのみを考えます。
type Set map[int]struct{} type Family []Set
以下のようにSet
の順番が異なる集合族の比較をするとdifferent
が返ってきます。
package main import ( "fmt" "reflect" ) type Set map[int]struct{} type Family []Set func main() { f1 := Family{ Set{1: struct{}{}, 2: struct{}{}}, Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}}, } f2 := Family{ Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}}, Set{1: struct{}{}, 2: struct{}{}}, } if reflect.DeepEqual(f1, f2) { fmt.Println("same") } else { fmt.Println("different") } // different }
https://play.golang.org/p/euz02m_InVS
この理由はreflect.DeepEqual
の実装を見るとわかります。
内部実装のdeepValueEqual
では、型ごと(今回だとsliceとmap)に比較方法が異なります。
sliceの比較は以下のようになっており、
順序も含めた比較
が行われます。
for i := 0; i < v1.Len(); i++ { if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) { return false } }
このため、上記の例では{1,2}
と{3,4,5}
を格納した順序が違い、different
となりました。
mapはもともと順序を意識させないデータ構造のため、DeepEqual
で比較すれば十分です。
ワークアラウンド
sliceを用いたまま、上記を解決するためには、なんらかの形で順序を揃えてあげる必要があります。
今回、自分が解決したかった問題では、Family
中のSet
は互いに素という条件があったため、
集合中の最大要素でソートすることで解決を図りました。
package main import ( "fmt" "reflect" "sort" ) type Set map[int]struct{} type Family []Set func main() { f1 := Family{ Set{1: struct{}{}, 2: struct{}{}}, Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}}, } f2 := Family{ Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}}, Set{1: struct{}{}, 2: struct{}{}}, } f1 = mySort(f1) f1 = mySort(f2) if reflect.DeepEqual(f1, f2) { fmt.Println("same") } else { fmt.Println("different") } } // same func mySort(f Family) Family { sort.Slice(f, func(i, j int) bool { var maxi, maxj int for k := range f[i] { if k > maxi { maxi = k } } for k := range f[j] { if k > maxj { maxj = k } } return maxi < maxj }) return f }
https://play.golang.org/p/CdHW_gKPxrS