Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法(仮名)

関連記事

本記事は Geek-Space Advent Calendar 2020 の 6 日目です。(間に合ってない)

はじめに

ここまでは、探索途中の情報をスタックに溜めたり、または再帰呼び出しを使ってコールスタックに溜めたりすることで、樹形図のノード間を複雑に右往左往していく動きを再現していきました。

さて、我々が順列を考える時の思考について、今一度分析してみます。

例として、[0, 1, 2, 3, 4, 5, 6] の 7 つから 4 つを取り出して並べる順列について考えてみましょう。
さて、1, 0, 6, 5 の次の順列は何でしょうか?

多くの人はこう考えるんじゃないでしょうか。
「まず 4 桁目の数値を上げようとしてみよう。5 の次は 6。これは 3 桁目で使っている。6 より上は無い。じゃあ 3 桁目を上げる必要があるな。あ、3 桁目も上げることができない。じゃあ 2 桁目だ。1 は 1 桁目で使ってるけど、2 なら空いてるぞ。じゃあ 1, 2 までは確定で、3, 4 桁目は残りの数を使って一番小さいやつにすればいいな。3 桁目は 0, 4 桁目は 1 と 2 がもう埋まってるから、3 だな。よし、1, 2, 0, 3。」

この思考を分析してみると、実は樹形図の発想なんて要らないことが分かります。
枝がここまでどう生えているかとか、把握する必要がない。
今までどう溜め込むか苦心してきた「探索途中の情報」ですが、実は我々はそんなものを溜め込まずに、目の前の順列を見るだけで次の順列を判断できるのです。

というわけで、今回はこの思考法をそのままコードで表現してみます。
「この思考法」といちいち呼ぶのもアレなので、テキトーに「繰り上がり法」と名付けました。(N 進法で値を増やして繰り上がりを処理するような思考に近いので。ちなみに重複順列だと完全に N 進法になります。)

コードは前回同様、全てこちらのリポジトリに上げてあります。
https://github.com/ikngtty/benchmark-go-combinatorics

実装

下準備

計測環境については前回と同様なので省略。

まずはそのまま実装

combinatorics/perm.go
func PermutationsWithCarrying0(n, k int, f func([]int)) {
    pattern := make([]int, k)
    // 最初の順列をセット
    for i := range pattern {
        pattern[i] = i
    }

    for {
        f(pattern)

        // 値増やしチャレンジ
        pos := k - 1 // 着目する桁。まずは右端から。
        for {
            // -1桁目を増やそうとしてる
            // = 0桁目で更に繰り上がりが起きたということ
            // = 最後の順列の更にその次の順列を作ろうとしている状況
            // = 処理を切り上げるタイミング
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]

            willBreak := false // 大域脱出用
            for newNum := oldNum + 1; newNum < n; newNum++ {
                // 数字が使われていたらスキップ
                willContinue := false // 大域脱出用
                for i := 0; i < pos; i++ {
                    if pattern[i] == newNum {
                        willContinue = true // 大域脱出
                        break
                    }
                }
                // 大域脱出
                if willContinue {
                    continue
                }

                // 使われていない数字を見つけたケース
                // -> 今見ている桁をその数に書き換えて、値増やし成功。
                pattern[pos] = newNum
                willBreak = true // 大域脱出
                break
            }
            // 大域脱出
            if willBreak {
                break
            }

            // 今見ている桁の値はこれ以上増やせないというケース
            // -> 繰り上がり。見る桁を一つ左にずらして繰り返す。
            pos--
        }

        // 繰り上がった桁(値を増やした桁より右の桁全部)を埋める。なるべく小さい数字で埋める。
        for pos++; pos < k; pos++ {
            for num := 0; num < k; num++ {
                // 数字が使われていたらスキップ
                willContinue := false
                for i := 0; i < pos; i++ {
                    if pattern[i] == num {
                        willContinue = true
                        break
                    }
                }
                if willContinue {
                    continue
                }

                // 使われていない数字を見つけたケース
                // -> その数で書き換え
                pattern[pos] = num
                break
            }
        }
    }
}
PermutationsRecursive6       191816791 ns           96 B           2 allocs
PermutationsWithSlice7       183175502 ns         9504 B           9 allocs
PermutationsWithCarrying0    602414196 ns           80 B           1 allocs

今回の測定結果の上に並べた 2 つの測定結果は、今までの最速記録群です。この辺には全然勝てないですが、そんなに悪くもないですね。

チェックリストを使う

いつものやつです。

combinatorics/perm.go
func PermutationsWithCarrying1(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)
    for i := range pattern {
        pattern[i] = i
        checklist[i] = true
    }

    for {
        f(pattern)

        pos := k - 1
        for {
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]
            checklist[oldNum] = false

            willBreak := false
            for newNum := oldNum + 1; newNum < n; newNum++ {
                if checklist[newNum] {
                    continue
                }

                pattern[pos] = newNum
                checklist[newNum] = true
                willBreak = true
                break
            }
            if willBreak {
                break
            }

            pos--
        }

        for pos++; pos < k; pos++ {
            for num := 0; num < k; num++ {
                if checklist[num] {
                    continue
                }

                pattern[pos] = num
                checklist[num] = true
                break
            }
        }
    }
}
PermutationsRecursive6       191816791 ns           96 B           2 allocs
PermutationsWithSlice7       183175502 ns         9504 B           9 allocs
PermutationsWithCarrying0    602414196 ns           80 B           1 allocs
PermutationsWithCarrying1    149944171 ns           96 B           2 allocs

最速出ました!
やはりチェックリストによる使用済み番号管理は欠かせない模様。

ループをまとめる

ここまでのコードは、「前半:右端の桁から繰り上がりで徐々に左に進むループ」「後半:繰り上がった桁を埋め直すために右端へと戻っていくループ」の 2 つのループを並べる構成でした。
この 2 つのループをまとめて 1 つのループにすることができます。

combinatorics/perm.go
func PermutationsWithCarrying2(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)
    // 最初の順列をセット
    for i := range pattern {
        pattern[i] = i
        checklist[i] = true
    }

    // 前回は 1 ループ 1 順列のループがあって、その内部に 1 ループ 1 桁のループがあった。
    // 今回はいきなり 1 ループ 1 桁から始まる感じ。
    pos := k // まずは右端の更に右から。`f`を実行したらすぐ右端に戻ってくる。
    for pos > -1 {
        if pos == k {
            f(pattern)
            pos--
            continue
        }

        oldNum := pattern[pos]
        if oldNum > -1 {
            checklist[oldNum] = false
        }

        // 値増やしチャレンジ
        willContinue := false // 大域脱出用
        for newNum := oldNum + 1; newNum < n; newNum++ {
            if checklist[newNum] {
                continue
            }

            // 値増やしチャレンジ成功 -> 右へ進む
            pattern[pos] = newNum
            checklist[newNum] = true
            pos++
            willContinue = true // 大域脱出
            break
        }
        // 大域脱出
        if willContinue {
            continue
        }

        // 値増やしチャレンジ失敗 -> 繰り上がり。左へ進む。
        pattern[pos] = -1 // 一旦-1にしておくのがポイント
        pos--
    }
}

繰り上がりの時に、その桁の数字を -1 にしておくのがポイントです。
これにより、左向きに繰り上がっていく時の値増やしチャレンジと、右向きに値を埋めていく時の値増やしチャレンジを、同じコード(元の値から少しだけ値を増やそうとチャレンジする)で行うことができます。

PermutationsRecursive6       191816791 ns           96 B           2 allocs
PermutationsWithSlice7       183175502 ns         9504 B           9 allocs
PermutationsWithCarrying1    149944171 ns           96 B           2 allocs
PermutationsWithCarrying2    170103707 ns           96 B           2 allocs

依然優秀ですが、少し遅くなりました。
工夫しすぎてむしろ複雑化してしまった感じもあるので、あんまりオススメできないですね。

まとめ

結論実装を再掲:

combinatorics/perm.go
func PermutationsWithCarrying1(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)
    for i := range pattern {
        pattern[i] = i
        checklist[i] = true
    }

    for {
        f(pattern)

        pos := k - 1
        for {
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]
            checklist[oldNum] = false

            willBreak := false
            for newNum := oldNum + 1; newNum < n; newNum++ {
                if checklist[newNum] {
                    continue
                }

                pattern[pos] = newNum
                checklist[newNum] = true
                willBreak = true
                break
            }
            if willBreak {
                break
            }

            pos--
        }

        for pos++; pos < k; pos++ {
            for num := 0; num < k; num++ {
                if checklist[num] {
                    continue
                }

                pattern[pos] = num
                checklist[num] = true
                break
            }
        }
    }
}

今回の計測結果群は以下:

PermutationsWithCarrying0    602414196 ns           80 B           1 allocs
PermutationsWithCarrying1    149944171 ns           96 B           2 allocs
PermutationsWithCarrying2    170103707 ns           96 B           2 allocs

優秀ですね。

最速シリーズを今一度まとめ:

PermutationsRecursive6       191816791 ns           96 B           2 allocs
PermutationsWithSlice7       183175502 ns         9504 B           9 allocs
PermutationsWithCarrying1    149944171 ns           96 B           2 allocs

繰り上がり法が一番速いですね。まあでも僅差なので割とどれでもいい気がします。
「競プロでどれを使うか」とか考える時は、書きやすさで選ぶと良いと思います。
個人的には再帰が一番書きやすいですが、再帰に慣れない人は繰り上がり法が良いんじゃないでしょうか。

Next: Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙

ikngtty
580日ぐらい無職やりました。社会人リハビリ中。
http://ikngtty.hatenablog.com/
realglobe
「世界のすべてをWebAPI化する」ことを目指す技術ベンチャーです。
https://realglobe.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away