#はじめに
Atcoderなどの練習用に、色々なアルゴリズムをgolangで書く練習をしているなかで、組み合わせ問題(combination)を解くさいに、どのような方法が良いかを調べていました。
その中で参考にしたサイト(https://qiita.com/kokardy/items/a18b574d548c212e58e6) ではgolangらしく並列処理を利用してコードが紹介されていました。
自分の理解のためにも、これを素直に二重配列を利用したものに書き換えてベンチマークをしてみました。
参考もとのコードの速さが際立っていたので備忘録を含めて書いておきます。
この解析はMacBookPro go1.14.2で測定しました。

#参考にした並列処理のコード
参照元: https://qiita.com/kokardy/items/a18b574d548c212e58e6

func Combinations(list Replacer, select_num int, repeatable bool, buf int) (c chan Replacer) {
    c = make(chan Replacer, buf)
    index := make([]int, list.Len(), list.Len())
    for i := 0; i < list.Len(); i++ {
        index[i] = i
    }
    var comb_generator func([]int, int, int) chan []int
    if repeatable {
        comb_generator = repeated_combinations
    } else {
        comb_generator = combinations
    }
　　 go func() {
        defer close(c)
        for comb := range comb_generator(index, select_num, buf) {
            c <- list.Replace(comb)
        }
    }()
    return
}

#二重配列を利用したコード

func combination(list []string, select_num int) [][]string {
        combi := make([][]string, 0)
        switch {
        case select_num == 0:
                return [][]string{{}}
        case select_num == len(list):
                return [][]string{list}
        case len(list) < select_num:
                return nil
        default:
                for i := 0; i < len(list); i++ {
                        subCombi := combination(list[i+1:], select_num-1)
                        for _, subList := range subCombi {
                                newCombi := append([]string{list[i]}, subList...)
                                combi = append(combi, newCombi)
                        }
                }
                return combi
        }
}

#Benchmark結果
1000個のint配列を作ってbenchmarkを取ってみました。
圧倒的に速度。。。おおよそ1000倍早いとは。。

h0801Toby001:bench toby$ go test -bench . -benchmem
goos: darwin
goarch: amd64
BenchmarkArrayCombination-4   	       6	 170055299 ns/op	135015690 B/op	 2008002 allocs/op
BenchmarkChanCombination-4    	  124047	     10958 ns/op	    2362 B/op	      39 allocs/op
PASS
ok  	_/Users/toby/Dropbox/Documents/program/atcoder/test/bench	4.781s

#所感
二重配列の処理は、毎回帰ってくるたびにsliceにappendしているのがとにかく重そうです。
channelに入れるだけだと軽いのかな。
二重配列の場合でも、事前に必要なだけsliceを確保していおくと早いのかな。