GoでPythonのrandom.shuffle()を実装し、カイ二乗検定を用いたユニットテストをする

背景

Goでコントリビュートできそうなレポジトリを探していると、goshというレポジトリがあった。
これは、JavaScriptやPythonでの構文をGoで書く、というものだった。
面白そうだったので、Pythonのshuffleを実装し、PRを出そうと思った。
Pythonのshuffleというのは、配列を受け取り、その配列の要素の順番をランダムに変換して返す、というのだった。
commitしようとしていたコードは、以下だった。

func Shuffle(s []interface{}) []interface{} {
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(s), func(i, j int) { s[i], s[j] = s[j], s[i] })
	return s
}

しかし、commitしようとした時にはもう実装されていたのでissueを閉じた。
github.com
commitしようとした時のテストコードは、

• shuffleする前とした後で配列の長さが等しい
• shuffleする前とした後で配列の要素が等しい

ことを確認するものだった。
しかしよく考えると、上のコードでは破壊的な操作はしておらず、上記の2項目は自明であった。
肝心なのは、

• shuffleによって、要素の順番が満遍なく変換されている

ことを確認することだった。
今回のような、ランダム性をテストする時にはどうしたらよいかを調べてみると、以下のスライドがあった。
speakerdeck.com
このスライドによると、カイ二乗検定によってランダム性をテストできる、ということだった。

カイ二乗検定とは

帰無仮説が正しければ検定統計量が漸近的にカイ二乗分布に従うような統計的検定法の総称である。
カイ二乗検定 - Wikipedia

ざっくりとした感じで例を出す。
サイコロを振って、目が均等に出ているかどうかを検定したいとする。
実際に振ってみて出た目の回数を観測度数、目が均等に出ている場合の回数を期待度数という。
それぞれの回数が以下の場合、

サイコロの目	1	2	3	4	5	6	合計
観測度数	17	22	21	14	22	24	120
期待度数	20	20	20	20	20	20	120

という計算でを求める。
このが、棄却域より小さければ、目が均等に出ていることが保証される。
棄却域は有意水準と自由度で決まる。
有意水準は、たいてい5%か1%で、自由度は、(要素の数 - 1)で、今回だったら、(目の数6 - 1 )= 5となる。
棄却域の分布表は以下から取得できる。
http://www3.u-toyama.ac.jp/kkarato/2016/statistics/handout/chisqdist.pdf

コードの概要

今回作ったリポジトリが以下である。
github.com

shuffle.goには、先述したshuffleのコードを書いている。
https://github.com/wafuwafu13/go-chi-square-test/blob/master/shuffle.go

package chi_square

import (
	"math/rand"
	"time"
)

func Shuffle(s []interface{}) []interface{} {
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(s), func(i, j int) { s[i], s[j] = s[j], s[i] })
	return s
}

テストは、[]interface{}{"a", "b", "c", "d", "e"}というスライスをShuffleに渡したとき、うまくシャッフルできているかを確認する。
カイ二乗検定を行うChiSquareは、第1引数に有意水準、第2引数に自由度、第3引数に観測度数、第4引数に期待度数をとり、が棄却域より小さい場合にtrue、大きい場合にfalseを返している。

Shuffleを100回実行したとき、スライスの先頭、つまり"a"の位置が、0,1,2,3,4番目にくる回数がそれぞれ等しかったら、うまくシャッフルできているといえる。
よって、期待度数は、[]float64{20, 20, 20, 20, 20}となる。
https://github.com/wafuwafu13/go-chi-square-test/blob/master/shuffle_test.go#L28
観測度数は、実際にShuffleを100回実行し、"a"のインデックスを累計して求めている。
https://github.com/wafuwafu13/go-chi-square-test/blob/master/shuffle_test.go#L27
有意水準は5%に設定し、自由度は(配列の長さ-1)で求められている。
https://github.com/wafuwafu13/go-chi-square-test/blob/master/shuffle_test.go#L29

if !ChiSquare(5, len(expected_frequency)-1, observation_frequency, expected_frequency) {
	 t.Error("not shuffled")
}

の計算および、棄却域との比較は、chi_square.goでやっている。
https://github.com/wafuwafu13/go-chi-square-test/blob/master/chi_square.go

...
x += (math.Pow(observation_frequency[i] - expected_frequency[i], 2)) / expected_frequency[i]
...
	if x > rejection_area {
		return false
	} else {
		return true
	}
...

テスト実行と結果

実際にテストを実行してみると、以下のような出力を得る。
https://github.com/wafuwafu13/go-chi-square-test/blob/master/chi_square.go#L14

$ go test
x: 1.0999999999999999, rejection_area: 9.49
PASS
ok      go-chi-square-test      0.474s

の値、つまり出力xの値は実行するたびに異なる。
このことからもシャッフルがうまく行われていることがわかる。

< go test
x: 4.1, rejection_area: 9.49
PASS
ok      go-chi-square-test      0.148s

また、shuffle.goのrand.Seed(time.Now().UnixNano())の処理を消すと、出力xの値は実行するたびに同じになり、(テストの結果をログに残しておけば?)シャッフルの処理がうまく行われていないこともわかる。

ちなみに、テスト対象のスライスを[]interface{}{"a", "a", "a", "a", "a"}にすると、毎回"a"が0番目にあると判定されてしまうので、テストは落ちる。(そもそも同じ要素だけのスライスをshuffleする動機が謎なので落ちて正解という捉え方もできる)
https://github.com/wafuwafu13/go-chi-square-test/blob/master/shuffle_test.go#L9

$ go test
x: 400, rejection_area: 9.49
--- FAIL: TestShuffle (0.00s)
    shuffle_test.go:30: not shuffled
FAIL
exit status 1
FAIL    go-chi-square-test      0.414s

テスト対象のスライスによってexpected_frequencyの値を変えてTableDrivenTestsすればよいと思うけど、もう満足したので終わる。