関連記事
本記事は Geek-Space Advent Calendar 2020 の 5 日目です。（間に合ってない）
- Golang による順列列挙のパフォーマンス研究 1. 再帰を用いたやり方
- Golang による順列列挙のパフォーマンス研究 2. スタックを用いたやり方 （本記事）
- Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法（仮名）
- Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙
はじめに
前回、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 パターンしかないので、これから実装するコードスタックもどきにはこの情報は要らなそうです。
pos と num の情報だけ積んでみます。
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
再帰相手にも勝ちまくれるようになりました。アイヤー。