golangでの組み合わせ問題で並列処理と単純な二重配列を利用した際の速度比較

はじめに

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を確保していおくと早いのかな。