【Golang】reflect.DeepEqualでsliceとmapを組み合わせて比較する

先日、集合や族を扱うパッケージを書いていたところ、mapやsliceが混じった構造でどのようにEqualを実装するかで少しハマりました。reflect.DeepEqualの実装を見て解決したので備忘として整理します。

ちょうどGoで違うmapであることをテストする でも、同じような課題に遭遇された方がいたようです。

考え方

まず、mapのEqualを実装するときに定義する2つのmapが等しいは、大きく以下の2つになると思います。

  1. 中身の要素が同じmapは、等しい(ポインタが異なることは気にしない)
  2. 中身が同じでも、ポインタが異なれば、等しくない

それぞれ、以下のように比較できます。

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

References