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 による順列列挙のパフォーマンス研究 2. スタックを用いたやり方

関連記事

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

はじめに

前回、DFS には再帰を用いるやり方とスタックを用いるやり方があるということで、再帰を用いるやり方の方を探っていきました。
今回はスタックを用いるやり方について同様に探っていきます。
再帰呼び出しは言語によって重かったりとかもあると思うので、再帰を避けることでもっとパフォーマンスの良い実装が見つかるといいなぁという感じです。
前回得られた「使用可能な数字をチェックリスト式で管理した方が良さそう」「1 つの配列を全順列分使い回した方が良い」といった結論は、今回は自明になったものとして最初から導入していきます。

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

実装

下準備

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

コールスタックを再現する

「再帰呼び出し」と「スタック」の共通点を考えてみて、「そういえば再帰呼び出しはコール"スタック"を積み上げてるな…」と思い浮かびました。そこから「コールスタックもどきを自分で実装すれば再帰しなくてもいいのでは?」と思い至ったので、試してみることにします。

コールスタックについて詳しく知っているわけではないですが、積む必要がありそうな情報はおそらく、ある一つの実行中の関数呼び出しについて

  • 各引数や変数の中身
  • どこまでコードを実行したか

あたりじゃないでしょうか。

ちょっと再帰の場合のコードを見てみましょう。

combinatorics/perm.go
func PermutationsRecursive6(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)

    var body func(pos int)
    body = func(pos int) {
        if pos == k {
            f(pattern)
            return
        }

        for num := range checklist {
            if checklist[num] {
                continue
            }

            pattern[pos] = num
            checklist[num] = true
            body(pos + 1)
            checklist[num] = false
        }
    }
    body(0)
}

この body 関数を繰り返し呼んだ時、コールスタックには

  • 各引数や変数の中身
    • pos の中身
    • num の中身
  • どこまでコードを実行したか
    • checklist[num] = false の直前まで実行した

といった情報がどんどん積まれていくのではないかと思われます。

「どこまでコードを実行したか」の情報は今回 1 パターンしかないので、これから実装するコードスタックもどきにはこの情報は要らなそうです。
posnum の情報だけ積んでみます。

combinatorics/perm.go
type callStackItem0 struct {
    pos          int // 順列の何桁目について扱っているか
    chosenNumber int // 順列の該当桁にどの数字を入れているか。上で言う`num`。
}

type callStack0 struct {
    last *callStack0Node
}

type callStack0Node struct {
    parent *callStack0Node
    value  *callStackItem0
}

func newCallStack0() *callStack0 {
    return &callStack0{nil}
}

func (s *callStack0) push(elem *callStackItem0) {
    node := callStack0Node{s.last, elem}
    s.last = &node
}

func (s *callStack0) pop() *callStackItem0 {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func (s *callStack0) peek() *callStackItem0 {
    return s.last.value
}

func (s *callStack0) empty() bool {
    return s.last == nil
}

func PermutationsWithStack0(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    callStack := newCallStack0()
    pattern := make([]int, k)

    callStack.push(&callStackItem0{pos: 0, chosenNumber: -1})
    for !callStack.empty() {
        // この1ループ内では、このコールスタックアイテムが担当する桁について
        // 値を増やすことを試みる
        env := callStack.peek()

        // 該当桁が右端を超えている時は、完成した順列をコールバック関数に渡し、
        // この桁については終了
        if env.pos == k {
            f(pattern)

            callStack.pop()
            continue
        }

        // 該当桁についてチェックリストの使用済みチェックを外しておく
        if env.chosenNumber > -1 {
            checklist[env.chosenNumber] = false
        }

        // 値増やしチャレンジ
        willContinue := false // 大域脱出用
        for env.chosenNumber++; env.chosenNumber < n; env.chosenNumber++ {
            // 使おうとする数字が使用済みならスキップ
            if checklist[env.chosenNumber] {
                continue
            }

            // 使用可能な数字を無事見つけたケース
            // 見つけた数字で順列を書き換え
            pattern[env.pos] = env.chosenNumber
            checklist[env.chosenNumber] = true

            // 1つ右の桁担当のコールスタックアイテムを積む。再帰呼び出しに相当。
            newEnv := callStackItem0{
                pos: env.pos + 1, chosenNumber: -1,
            }
            callStack.push(&newEnv)
            willContinue = true // 大域脱出
            break
        }
        // 大域脱出
        if willContinue {
            continue
        }

        // 値を増やすのに失敗したケース
        // コールスタックを1つ掘り下げて、1つ左の桁に戻って考え直す
        callStack.pop()
    }
}
PermutationsRecursive6   191816791 ns           96 B           2 allocs
PermutationsWithStack0  1004648553 ns    315651624 B    19728208 allocs

比較対象の PermutationsRecursive6 は前回記事での優勝記録です。全然勝てない…。

「各桁に今どの数字を入れているか」の情報を、コールスタックアイテムから省く

各桁に今どの数字を入れているかは、生成中の順列を見れば分かります。

combinatorics/util.go
type IntStack struct {
    last *intStackNode
}

type intStackNode struct {
    parent *intStackNode
    value  int
}

func NewIntStack() *IntStack {
    return &IntStack{nil}
}

func (s *IntStack) Push(elem int) {
    node := intStackNode{s.last, elem}
    s.last = &node
}

func (s *IntStack) Pop() int {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func (s *IntStack) Peek() int {
    return s.last.value
}

func (s *IntStack) Empty() bool {
    return s.last == nil
}
combinatorics/perm.go
func PermutationsWithStack1(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    posStack := NewIntStack() // コールスタックアイテムが`pos`のみになった
    pattern := make([]int, k)
    // 生成中の順列には、「まだちゃんと値を入れていない」という情報を
    // ちゃんと-1として埋め込む必要が出てきた
    for i := range pattern {
        pattern[i] = -1
    }

    posStack.Push(0)
    for !posStack.Empty() {
        pos := posStack.Peek()

        if pos == k {
            f(pattern)

            posStack.Pop()
            continue
        }

        chosenNumber := pattern[pos] // 生成中の順列から値取得
        if chosenNumber > -1 {
            checklist[chosenNumber] = false
        }

        willContinue := false
        for chosenNumber++; chosenNumber < n; chosenNumber++ {
            if checklist[chosenNumber] {
                continue
            }

            pattern[pos] = chosenNumber
            checklist[chosenNumber] = true

            posStack.Push(pos + 1)
            willContinue = true
            break
        }
        if willContinue {
            continue
        }

        pattern[pos] = -1 // ちゃんと-1にリセットしないといけない
        posStack.Pop()
    }
}
PermutationsRecursive6   191816791 ns           96 B           2 allocs
PermutationsWithStack0  1004648553 ns    315651624 B    19728208 allocs
PermutationsWithStack1   572861294 ns    157825764 B     9864104 allocs

再帰には相変わらず勝てる気がしませんが、先の実装と比べると、やたら速くなりました。
構造体に比べて int の方が遥かに軽く扱えるということなんでしょうか。

樹形図のノードをスタックに積む

ここまでのやり方は、「for 文開始 -> ある桁の値をちょっとだけ増やす -> break(次のスタックアイテムへ) -> 戻ってきたら続きからまた for 文開始 -> ちょっとだけ増やしたらまた break」みたいな感じでした。
例えば「3 桁目に 1 を入れる -> 3 を入れる -> 4 を入れる」の場合、「for -> 1 -> break -> for -> 3 -> break -> for -> 4 -> break」という感じです。
このちまちま何度も for 文を使う感じ、なんかすごい無駄な気がします。

さて、DFS についてたとえば Wikipedia を調べてみると、どうやらスタックの使い方が違うことが分かります。
木構造の各ノードをスタックに積むのが普通みたいですね。
こっちのやり方なら、「for -> 4 をスタックに積む -> 3 をスタックに積む -> 1 をスタックに積む -> break」と一回の for 文実行でひと通り済ませることができます。
言葉で言っても分かりづらそうなので、以下が実際のコード;

combinatorics/perm.go
type patternNode2 struct {
    pos    int // 順列の何桁目か
    number int // 該当桁の数字
}

type patternNodeStack2 struct {
    last *patternNodeStack2Node
}

type patternNodeStack2Node struct {
    parent *patternNodeStack2Node
    value  *patternNode2
}

func newPatternNodeStack2() *patternNodeStack2 {
    return &patternNodeStack2{nil}
}

func (s *patternNodeStack2) push(elem *patternNode2) {
    node := patternNodeStack2Node{s.last, elem}
    s.last = &node
}

func (s *patternNodeStack2) pop() *patternNode2 {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func PermutationsWithStack2(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    patternNodeStack := newPatternNodeStack2()
    pattern := make([]int, k)

    patternNodeStack.push(&patternNode2{pos: -1, number: 0})
    for !patternNodeStack.empty() {
        patternNode := patternNodeStack.pop()

        // 以前の順列のノードに関する後始末をここで行っている
        for i := patternNode.pos; i < k; i++ {
            if i > -1 && pattern[i] > -1 {
                checklist[pattern[i]] = false
                // `pattern`もリセットしておかないと`checklist`のリセット時に
                // 狂いが生じる。
                pattern[i] = -1
            }
        }

        // ノード通りに順列を書き換え
        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
            checklist[patternNode.number] = true
        }

        // 該当桁が右端の場合、完成した順列をコールバック関数に渡し、
        // この桁については終了
        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        // 1つ右の桁担当のコールスタックアイテムをひと通り積む
        for num := n - 1; num >= 0; num-- {
            if checklist[num] {
                continue
            }

            childNode := patternNode2{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack.push(&childNode)
        }
    }
}

以前は peek したり pop したりだったのが、今回はひたすら pop するだけなので、その辺も分かりやすくなったと思います。

一方で、ノードを扱った後の後始末(チェックリストのリセット)のタイミングが「次の順列についてのノードを取り扱い始めた時の最初」という歪なタイミングになってしまい、このへんは分かりづらくなりました。
「1 ノード : 1 スタックアイテム : 1 処理」が対応している形なので、ノードを一度移ってしまったらもう元のノードに帰ってくるタイミングが無く、こうなっています。

PermutationsWithStack0  1004648553 ns    315651624 B    19728208 allocs
PermutationsWithStack1   572861294 ns    157825764 B     9864104 allocs
PermutationsWithStack2   843198178 ns    315651816 B    19728210 allocs

パフォーマンスはまあまあですね。

ポインタではなく値でスタックアイテムを持つ

上記のコードで、各スタックアイテムは一度作ったら特に値を書き換えることなく使い捨てるようになりました。
この場合、スタックアイテムが参照(ポインタ)である必要はありません。
値にしたらパフォーマンスがどう変わるか見てみましょう。

combinatorics/perm.go
type patternNode3 struct {
    pos    int
    number int
}

type patternNodeStack3 struct {
    last *patternNodeStack3Node
}

type patternNodeStack3Node struct {
    parent *patternNodeStack3Node
    value  patternNode3 // ポインタから値になった
}

func newPatternNodeStack3() *patternNodeStack3 {
    return &patternNodeStack3{nil}
}

// 引数`elem`がポインタから値になった
func (s *patternNodeStack3) push(elem patternNode3) {
    node := patternNodeStack3Node{s.last, elem}
    s.last = &node
}

// 返り値がポインタから値になった
func (s *patternNodeStack3) pop() patternNode3 {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func (s *patternNodeStack3) empty() bool {
    return s.last == nil
}

// `patternNode3`を使うようになったこと以外は、
// `PermutationsWithStack2`とほぼ同じ。
func PermutationsWithStack3(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    patternNodeStack := newPatternNodeStack3()
    pattern := make([]int, k)

    patternNodeStack.push(patternNode3{pos: -1, number: 0})
    for !patternNodeStack.empty() {
        patternNode := patternNodeStack.pop()

        for i := patternNode.pos; i < k; i++ {
            if i > -1 && pattern[i] > -1 {
                checklist[pattern[i]] = false
                pattern[i] = -1
            }
        }

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
            checklist[patternNode.number] = true
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for num := n - 1; num >= 0; num-- {
            if checklist[num] {
                continue
            }

            childNode := patternNode3{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack.push(childNode)
        }
    }
}
PermutationsWithStack1   572861294 ns    157825764 B     9864104 allocs
PermutationsWithStack2   843198178 ns    315651816 B    19728210 allocs
PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs

結構速くなりました。

"-1桁目"から始めるのをやめる

だんだん

if patternNode.pos > -1 {
}

みたいな細かい if 文が増えてきて気持ち悪くなってきました。
どうやら -1 桁目(実際には存在せず、実装の都合で設けている)で始めているのが、今の実装と相性が悪そうです。
おとなしく 0 桁目から始めてみます。

combinatorics/perm.go
func PermutationsWithStack4(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    patternNodeStack := newPatternNodeStack3()
    pattern := make([]int, k)

    // エッヂケースとして別途処理しなきゃいけなくなった
    if k == 0 {
        f(pattern)
        return
    }

    // 0桁目のノード準備。-1桁目と違いn個分ある。
    for num := n - 1; num >= 0; num-- {
        patternNodeStack.push(patternNode3{pos: 0, number: num})
    }

    for !patternNodeStack.empty() {
        patternNode := patternNodeStack.pop()

        for i := patternNode.pos; i < k; i++ {
            if pattern[i] > -1 { // 条件減った
                checklist[pattern[i]] = false
                pattern[i] = -1
            }
        }

        // if文消えた
        pattern[patternNode.pos] = patternNode.number
        checklist[patternNode.number] = true

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for num := n - 1; num >= 0; num-- {
            if checklist[num] {
                continue
            }

            childNode := patternNode3{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack.push(childNode)
        }
    }
}

ちょっとすっきりした箇所もあればちょっと煩雑になった箇所もあり、という感じ。イマイチですね。

PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack4   663686560 ns    315651548 B     9864106 allocs

パフォーマンスは当然大して変わらないです。

チェックリスト式から整数配列式に戻す

ノードの後始末なんてしなきゃいけないからこんなややこしいコードになるんや!
なんで後始末が必要なんや!
チェックリストを管理しなきゃいけないからや!
というわけで、ここでチェックリストをやめてみます。
使用可能な数字群の管理には、代わりに元の整数配列を使うことにします。

combinatorics/perm.go
type patternNode5 struct {
    pos    int
    number int
    rest   []int // 樹形図の該当ノードより右のノードに使える、まだ使っていない数字群
}

type patternNodeStack5 struct {
    last *patternNodeStack5Node
}

type patternNodeStack5Node struct {
    parent *patternNodeStack5Node
    // 検証の結果、構造体の要素が1つ増えた今でも参照より値の方がパフォーマンスが良かった
    // (具体的な検証結果についてはだるいので省略)
    value  patternNode5
}

func newPatternNodeStack5() *patternNodeStack5 {
    return &patternNodeStack5{nil}
}

func (s *patternNodeStack5) push(elem patternNode5) {
    node := patternNodeStack5Node{s.last, elem}
    s.last = &node
}

func (s *patternNodeStack5) pop() patternNode5 {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func (s *patternNodeStack5) empty() bool {
    return s.last == nil
}

func PermutationsWithStack5(a []int, k int, f func([]int)) {
    patternNodeStack := newPatternNodeStack5()
    pattern := make([]int, k)

    patternNodeStack.push(patternNode5{pos: -1, number: 0, rest: a})
    for !patternNodeStack.empty() {
        patternNode := patternNodeStack.pop()

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for i := len(patternNode.rest) - 1; i >= 0; i-- {
            // i番目の項目を抜いた配列を新しく作る
            newRest := make([]int, len(patternNode.rest)-1)
            for j := 0; j < i; j++ {
                newRest[j] = patternNode.rest[j]
            }
            for j := i + 1; j < len(patternNode.rest); j++ {
                newRest[j-1] = patternNode.rest[j]
            }

            childNode := patternNode5{
                pos:    patternNode.pos + 1,
                number: patternNode.rest[i],
                rest:   newRest,
            }
            patternNodeStack.push(childNode)
        }
    }
}

ちょっとスッキリして分かりやすくなったんじゃないでしょうか。

PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack5   969391196 ns    557476872 B    16099412 allocs

代わりにパフォーマンスは悪化しました。
やはり我々はもうチェックリスト無しでは行きていけないのだ…。

生成中の順列配列から残りの使用可能な数字を判断する

チェックリストに代わる策をめげずにもう 1 つ試してみます。

combinatorics/perm.go
func PermutationsWithStack6(n, k int, f func([]int)) {
    patternNodeStack := newPatternNodeStack3()
    pattern := make([]int, k)

    patternNodeStack.push(patternNode3{pos: -1, number: 0})
    for !patternNodeStack.empty() {
        patternNode := patternNodeStack.pop()

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

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

            childNode := patternNode3{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack.push(childNode)
        }
    }
}
PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack5   969391196 ns    557476872 B    16099412 allocs
PermutationsWithStack6  1170586330 ns    315651632 B     9864109 allocs

うん。駄目ですね。

操作内容を構造体で表してスタックに積む

ここまで問題としてきたのは、「スタックに沿って樹形図のノードを処理していくと、ノードを処理したあと(そこからもっと右に生えていくノードも全部処理したあと)の後始末をしたい時に、そのノードを表すスタックアイテムがもう無くなっているので、次のノードに移ってから無理やり前のノードについて後始末しなければいけなくなり、コードが煩雑になる」という点でした。

解決策としてここまで「後始末の必要性をなくせばいいのでは?」と取り組んできたけれども、どれもパフォーマンスを犠牲にする結果に。

今度は別の解決策として、「じゃあ後始末のためのスタックアイテムも積んでおけばいいじゃない」というのを試してみます。

この場合、スタックアイテムにはノードの情報だけでなく「通常処理をすべきか後始末をすべきか」の情報が必要になってきます。
こうなってくると、スタックアイテムが指すものはノード自体というよりも、「このノードをこうしろ」という「操作内容」の方が近いです。

combinatorics/perm.go
const (
    // 操作の種類
    operationMode7ReflectValue = iota // 通常処理1
    operationMode7ExecuteOrDelegate   // 通常処理2
    operationMode7ResetValue          // 後始末
)

type operation7 struct {
    pos    int // 該当ノードについて、順列の何桁目か
    number int // 該当ノードについて、該当桁の数字
    mode   int // 操作の種類
}

type operationStack7 struct {
    last *operationStack7Node
}

type operationStack7Node struct {
    parent *operationStack7Node
    value  operation7
}

func newOperationStack7() *operationStack7 {
    return &operationStack7{nil}
}

func (s *operationStack7) push(elem operation7) {
    node := operationStack7Node{s.last, elem}
    s.last = &node
}

func (s *operationStack7) pop() operation7 {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func (s *operationStack7) empty() bool {
    return s.last == nil
}

func PermutationsWithStack7(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    operationStack := newOperationStack7()
    pattern := make([]int, k)

    operationStack.push(operation7{
        pos:    -1,
        number: 0,
        mode:   operationMode7ExecuteOrDelegate,
    })
    for !operationStack.empty() {
        operation := operationStack.pop()

        switch operation.mode {
        case operationMode7ReflectValue:
            pattern[operation.pos] = operation.number
            checklist[operation.number] = true

        case operationMode7ExecuteOrDelegate:
            if operation.pos == k-1 {
                // Execute
                f(pattern)
            } else {
                // Delegate
                for num := n - 1; num >= 0; num-- {
                    if checklist[num] {
                        continue
                    }

                    // スタックなので、先に入れた操作ほど後に実行されることに注意
                    operationStack.push(operation7{
                        pos:    operation.pos + 1,
                        number: num,
                        mode:   operationMode7ResetValue,
                    })
                    operationStack.push(operation7{
                        pos:    operation.pos + 1,
                        number: num,
                        mode:   operationMode7ExecuteOrDelegate,
                    })
                    operationStack.push(operation7{
                        pos:    operation.pos + 1,
                        number: num,
                        mode:   operationMode7ReflectValue,
                    })
                }
            }

        case operationMode7ResetValue:
            checklist[operation.number] = false
        }
    }
}

通常処理と後始末を分けるついでに、通常処理も 2 つに分けることにより、"-1 桁目"について通常処理 1(順列への値の反映)をスキップしなければいけない部分も綺麗に書けました。
冗長な気もしますが、個人的には他のパターンより書きやすかったです。

PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack5   969391196 ns    557476872 B    16099412 allocs
PermutationsWithStack6  1170586330 ns    315651632 B     9864109 allocs
PermutationsWithStack7  1766143475 ns    946954664 B    29592321 allocs

しかしパフォーマンスは悪くなる一方。

いっそ操作を関数で表してスタックに積む

操作ってそれもう関数じゃ〜ん、と思ったので、関数自体をスタックに積めないか試してみました。

combinatorics/util.go
type FuncStack struct {
    last *funcStackNode
}

type funcStackNode struct {
    parent *funcStackNode
    value  func()
}

func NewFuncStack() *FuncStack {
    return &FuncStack{nil}
}

func (s *FuncStack) Push(elem func()) {
    node := funcStackNode{s.last, elem}
    s.last = &node
}

func (s *FuncStack) Pop() func() {
    value := s.last.value
    s.last = s.last.parent
    return value
}

func (s *FuncStack) Peek() func() {
    return s.last.value
}

func (s *FuncStack) Empty() bool {
    return s.last == nil
}
combinatorics/perm.go
func PermutationsWithStack8(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    operationStack := NewFuncStack()
    pattern := make([]int, k)

    reflectValue := func(pos, number int) {
        pattern[pos] = number
        checklist[number] = true
    }
    resetValue := func(number int) {
        checklist[number] = false
    }
    // 中で再帰的に自身を呼ぶので、宣言を先に済ませる必要がある
    var executeOrDelegate func(pos int)
    executeOrDelegate = func(pos int) {
        if pos == k-1 {
            f(pattern)
            return
        }

        for num := n - 1; num >= 0; num-- {
            if checklist[num] {
                continue
            }

            // 以降で作る関数の中で`num`を直接参照してしまうと、実際にその関数が実行されて
            // `num`を使う頃には、`num`の値がもうfor文によって書き換えられてしまっている、
            // という状態になってしまう。
            // そのためループ毎に新しい変数`numFrozen`を作り、そっちに値を退避させておく必要がある。
            numFrozen := num
            operationStack.Push(func() {
                resetValue(numFrozen)
            })
            operationStack.Push(func() {
                executeOrDelegate(pos + 1)
            })
            operationStack.Push(func() {
                reflectValue(pos+1, numFrozen)
            })
        }
    }

    operationStack.Push(func() {
        executeOrDelegate(-1)
    })
    for !operationStack.Empty() {
        operation := operationStack.Pop()
        operation()
    }
}

いやもう再帰しちゃってるじゃん!

PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack5   969391196 ns    557476872 B    16099412 allocs
PermutationsWithStack6  1170586330 ns    315651632 B     9864109 allocs
PermutationsWithStack7  1766143475 ns    946954664 B    29592321 allocs
PermutationsWithStack8  3088975270 ns   1420431936 B    59184625 allocs

もうだめぽ。

まとめ

ここまでの計測結果を前回の優勝結果とともに全て並べてみると、

PermutationsRecursive6   191816791 ns           96 B           2 allocs
PermutationsWithStack0  1004648553 ns    315651624 B    19728208 allocs
PermutationsWithStack1   572861294 ns    157825764 B     9864104 allocs
PermutationsWithStack2   843198178 ns    315651816 B    19728210 allocs
PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack4   663686560 ns    315651548 B     9864106 allocs
PermutationsWithStack5   969391196 ns    557476872 B    16099412 allocs
PermutationsWithStack6  1170586330 ns    315651632 B     9864109 allocs
PermutationsWithStack7  1766143475 ns    946954664 B    29592321 allocs
PermutationsWithStack8  3088975270 ns   1420431936 B    59184625 allocs

このようになり、結局再帰には全然勝てませんでした。
(少なくともGo の場合は)おとなしく再帰で書いた方が良い模様。
生半可な自作スタックより、本物のコールスタックの方が色々最適化されているんですかね。

「どうしても再帰が書けないからスタックを使って書きたい!」という人は、書きやすさとパフォーマンスのトレードオフを鑑みながら、どれか好きなのを選んでください。
個人的には構造体で操作を表すやつが好きです。

と思いきや!大事な追記

「スタックをスライスで実装したらどうなるの?」というツッコミが入ったので、試してみました。

// PermutationsWithStack0のスライス使った版
func PermutationsWithSlice0(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    callStack := make([]callStackItem0, 1) // スライスに変更
    pattern := make([]int, k)

    callStack[0] = callStackItem0{pos: 0, chosenNumber: -1}
    for len(callStack) > 0 {
        env := &callStack[len(callStack)-1] // peek

        if env.pos == k {
            f(pattern)

            callStack = callStack[:len(callStack)-1] // pop(discard)
            continue
        }

        if env.chosenNumber > -1 {
            checklist[env.chosenNumber] = false
        }

        willContinue := false
        for env.chosenNumber++; env.chosenNumber < n; env.chosenNumber++ {
            if checklist[env.chosenNumber] {
                continue
            }

            pattern[env.pos] = env.chosenNumber
            checklist[env.chosenNumber] = true

            newEnv := callStackItem0{
                pos: env.pos + 1, chosenNumber: -1,
            }
            callStack = append(callStack, newEnv) // push
            willContinue = true
            break
        }
        if willContinue {
            continue
        }

        callStack = callStack[:len(callStack)-1] // pop(discard)
    }
}

// PermutationsWithSlice1以降も同様なので省略。
// また、PermutationsWithSlice3はPermutationsWithSlice2と同じなので除いた。
PermutationsRecursive6   191816791 ns           96 B           2 allocs
PermutationsWithStack0  1004648553 ns    315651624 B    19728208 allocs
PermutationsWithStack1   572861294 ns    157825764 B     9864104 allocs
PermutationsWithStack2   843198178 ns    315651816 B    19728210 allocs
PermutationsWithStack3   648371094 ns    315651576 B     9864106 allocs
PermutationsWithStack4   663686560 ns    315651548 B     9864106 allocs
PermutationsWithStack5   969391196 ns    557476872 B    16099412 allocs
PermutationsWithStack6  1170586330 ns    315651632 B     9864109 allocs
PermutationsWithStack7  1766143475 ns    946954664 B    29592321 allocs
PermutationsWithStack8  3088975270 ns   1420431936 B    59184625 allocs
PermutationsWithSlice0   234075281 ns          576 B           6 allocs
PermutationsWithSlice1   184274404 ns          336 B           6 allocs
PermutationsWithSlice2   186323035 ns         2112 B           8 allocs
PermutationsWithSlice4   183515108 ns         2496 B           6 allocs
PermutationsWithSlice5   360493641 ns     84004413 B     6235310 allocs
PermutationsWithSlice6   657643570 ns         2096 B           7 allocs
PermutationsWithSlice7   183175502 ns         9504 B           9 allocs
PermutationsWithSlice8  2023963760 ns    946958520 B    29592322 allocs

再帰相手にも勝ちまくれるようになりました。アイヤー。

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

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