「ズンドコチェック」なるものが流行っているらしい

Javaの講義、試験が「自作関数を作り記述しなさい」って問題だったから
「ズン」「ドコ」のいずれかをランダムで出力し続けて「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ！」って出力した後終了って関数作ったら満点で単位貰ってた
— てくも (@kumiromilk) 2016年3月9日

「習作（study）」としてはなかなか秀逸なアイデアだと思う。これで満点くれる教官も流石だが（笑）巷では「ズンドコキヨシ」とか「キヨシチェック」とか「ズンドコチェック」とか呼ばれているらしい。

というわけで

「ズン」「ドコ」のいずれかをランダムで出力し続けて「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ！」って出力した後終了って関数

を Go 言語で実装することを考えてみる。私はコレを「ズンドコ・コール（zundoko-choir）」と呼ぶことにする。

とはいえ，ズンドコ・コールを実装する事自体はそう難しくない。たとえばこんな感じ。

package main

import (
    "fmt"
    "math/rand"
    "time"
)

const (
    zun     = "ズン"
    doko    = "ドコ"
    kiyoshi = "キ・ヨ・シ！"
)

func generate() chan string {
    ch := make(chan string)
    go func() {
        var zundoko = [2]string{zun, doko}
        rand.Seed(time.Now().UnixNano())
        for {
            ch <- zundoko[rand.Intn(2)]
        }
    }()
    return ch
}

func main() {
    zundoko := generate()
    zcount := 0
    for {
        zd := <-zundoko
        fmt.Print(zd)
        if zd == zun {
            zcount++
        } else if zcount >= 4 {
            break
        } else {
            zcount = 0
        }
    }
    fmt.Print(kiyoshi)
}

「ズン」および「ドコ」をランダムに生成する部分は channel と goroutine を使えばいいだろう（generate() 関数内の処理）。擬似乱数は厳密でなくてもいいので安直に math/rand を使うことにした¹。さらに「ズン」「ズン」「ズン」「ズン」「ドコ」の配列パターンのチェックだが，「ズン」が4回以上連続で来た直後に「ドコ」が来たら OK としてみた。まぁ，これがもっとも素朴な実装でパフォーマンスとしてもそれほど遜色ない筈。

と，ここまで考えてハタと気づいた。問題は「自作関数を作り記述しなさい」なんだからメイン関数にロジック書いたらアカンやん！

というわけでまたもゴリゴリとコードを書いてパッケージにしてしまった。アホだ，私（笑）

spiegel-im-spiegel/zundoko: Zundoko-choirs

出力は標準出力に直書きするのではなく string の slice に append() することで実現する。この出力先を Choirs 型として定義した。

//Choirs - zundoko-choirs list
type Choirs struct {
    c []string
}

//Push is append choirs
func (c *Choirs) Push(s string) {
    c.c = append(c.c, s) //maybe panic if c is nil.
}

func (c *Choirs) String() string {
    if c == nil {
        return ""
    }
    content := make([]byte, 0, 128)
    for _, s := range c.c {
        content = append(content, s...)
    }
    return string(content)
}

ちなみに文字列の連結は strings.Join() 関数は使わず「文字列連結はどれが速い？」で紹介した方法を使っている。

これで最初のコードは

func generate() chan string {
    ch := make(chan string)
    go func() {
        var zd = [2]string{Zun, Doko}
        rand.Seed(time.Now().UnixNano())
        for {
            ch <- zd[rand.Intn(2)]
        }
    }()
    return ch
}

//Run zundoko-choirs
func Run() *Choirs {
    zd := generate()
    c := &Choirs{make([]string, 0)}
    zcount := 0
    for {
        s := <-zd
        c.Push(s)
        if s == Zun {
            zcount++
        } else if zcount >= 4 {
            break
        } else {
            zcount = 0
        }
    }
    c.Push(Kiyoshi)
    return c
}

と書き換えることができる。このパッケージを呼び出すメイン側は例えば

package main

import (
    "fmt"

    "github.com/spiegel-im-spiegel/zundoko"
)

func main() {
    c := zundoko.Run()
    fmt.Println(c)
}

と書けばいい。

ところで「ズン」「ドコ」の出力は Choirs 型で保持られているので，末尾の5要素のパターンを調べる別の方法もあると気づく。たとえばこんな感じ。

var matchingPattern = []string{Zun, Zun, Zun, Zun, Doko}

func (c *Choirs) match() bool {
    if c == nil {
        return false
    }
    if len(c.c) < 5 {
        return false
    }
    return reflect.DeepEqual(c.c[len(c.c)-5:], matchingPattern)
}

この関数を使えば Run() 関数は

//Run2 zundoko-choirs (another logic)
func Run2() *Choirs {
    zd := generate()
    c := &Choirs{make([]string, 0)}
    for {
        s := <-zd
        c.Push(s)
        if c.match() {
            break
        }
    }
    c.Push(Kiyoshi)
    return c
}

となり随分すっきりする。ただこれコストが高くつきそうである。というわけで，これも調べてみた。まず以下のベンチマークを書く。

package zundoko

import "testing"

func BenchmarkRun1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        Run()
    }
}

func BenchmarkRun2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        Run2()
    }
}

BenchmarkRun1 が従来のもの， BenchmarkRun2 が先程の match() 関数を使ったバージョンである。結果は以下のとおり。

$ go test -bench Run -benchmem
testing: warning: no tests to run
PASS
BenchmarkRun1-4    50000     28141 ns/op    1800 B/op     9 allocs/op
BenchmarkRun2-4    30000     40102 ns/op    3912 B/op   115 allocs/op
ok      github.com/spiegel-im-spiegel/zundoko   4.261s

乱数の要素が絡むので毎回同じ値ではないが，傾向としてはこんな感じ。 BenchmarkRun2 のほうが allocation 回数が圧倒的に多いのが分かるだろう。これがスピードにもダイレクトに反映されている感じである。

今回は「「ズン」が4回以上連続で来た直後に「ドコ」が来たら OK」という単純なロジックだったが，もっと複雑なパターンが要求される場合は工夫が必要かもしれない²。

「ズン」と「ドコ」の出現回数を数える関数も作ってみた。

//CountZunDoko returns count of "ZUN" and "DOKO" choirs
func (c *Choirs) CountZunDoko() (int, int) {
    z := 0
    d := 0
    if c == nil {
        return z, d
    }
    for _, s := range c.c {
        switch s {
        case Zun:
            z++
        case Doko:
            d++
        }
    }
    return z, d
}

たとえば generate() 関数内で使っている擬似乱数パッケージを別のものに換えた時に統計処理で簡単な性能評価ができるかもしれない。今回はそこまではしなけど（擬似乱数の話はいずれやりたい）。

こうやって手遊びでコードを弄るのは楽しいものである。

ブックマーク

ズンドコキヨシまとめ - Qiita
ズンドコキヨシ with Go (n番煎じ) - Qiita
ズンドコキヨシGolang並列版 - Qiita : 「ズン」「ドコ」の生成部分を CPU の数だけ並列処理で行わせてひとつの channel に入力するというユニークな実装
「ズンドコキヨシ」と擬似乱数 - Qiita : Qiita で擬似乱数について簡単にまとめてみた。整理できたらこちらでも記事にするかも

参考図書

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES): Alan A.A. Donovan (著), Brian W. Kernighan (著), 柴田芳樹 (翻訳); 丸善出版 2016-06-20; 単行本（ソフトカバー）; 4621300253 (ASIN), 9784621300251 (EAN), 4621300253 (ISBN), 9784621300251 (ISBN); 評価

著者のひとりは（あの「バイブル」とも呼ばれる）通称 “K&R” の K のほうである。この本は Go 言語の教科書と言ってもいいだろう。

reviewed by Spiegel on 2016-07-13 (powered by PA-APIv5)

math/rand の乱数生成アルゴリズムの既定は線形合同法らしい。線形合同法は性能が良くなくゲームや暗号等では使えない。math/rand の乱数生成アルゴリズムは他のものに入れ替えることができる。たとえば seehuhn/mt19937 パッケージが使える。 ↩︎
たとえば container/list や container/ring といったパッケージを使う手がある。 ↩︎