尽管存在 WaitGroup，Goroutines 似乎还是被中断了

尽管存在 waitgroup，但我遇到了 goroutine 未结束的问题。在附加的代码中，您可以看到堆排列算法的实现。我想加快速度，因此我为每个可能的第一个数字创建了一个 goroutine，从而将每个 goroutine 的排列减少为 (n-1)!。总的来说，我应该仍然有 n! 排列 (n*(n-1)!= n!)，但我的主例程似乎在子例程完成之前退出。然后我尝试跟踪执行的排列。与我的信念相反，执行的排列数量不是恒定的，但在 n! 下总是有点（对于低 n）或非常多（对于大 n）。

例如 n=4 每次的排列都是 24，即 4! ，这样所有的 goroutine 就结束了。如果我有一个更高的数字，例如 n=8，我会得到一个大约 13500 的值，而不是预期的 40000 = 8!。

这种行为从何而来？如何确保主程序退出之前所有 goroutine 都已完成？

package main

import (
    "fmt"
    "sync"
)

var wg sync.WaitGroup
var permutations int

func main() {

    n := 9

    wg.Add(n)

    for i := 0; i < n; i++ {

        var arr []int
        for j := 0; j < n; j++ {
            if i != j {
                arr = append(arr, j+1)
            }
        }
        go threadFunction(n-1, i+1, arr)
    }

    wg.Wait()

    fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {

    defer wg.Done()

    heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {

    if k == 1 {
        arr = append(arr, prefix)
        // fmt.Println(arr)
        permutations++
    } else {
        heapPermutation(k-1, prefix, arr)

        for i := 0; i < k-1; i++ {
            if k%2 == 0 {
                arr[i], arr[k-1] = arr[k-1], arr[i]
            } else {
                arr[0], arr[k-1] = arr[k-1], arr[0]
            }
            heapPermutation(k-1, prefix, arr)
        }
    }
}

（可以轻松实现相同的行为，例如在 https://go.dev/play/ 上，因此它的重现性非常好。）

Video Summarization

一款可以自动将长视频制作成短片的桌面软件

下载

正确答案

在您的代码中，goroutine 同时访问 permutations 变量。当您增加 n 的值时，工作量会增加，这会成为导致意外结果的问题。

你可以使用mutex，它将确保当时只有一个goroutine可以访问permutations。

package main

import (
    "fmt"
    "sync"
)

var wg sync.WaitGroup
var permutations int
var permutationsMutex sync.Mutex

func main() {

    n := 9

    wg.Add(n)

    for i := 0; i < n; i++ {

        var arr []int
        for j := 0; j < n; j++ {
            if i != j {
                arr = append(arr, j+1)
            }
        }
        go threadFunction(n-1, i+1, arr)
    }

    wg.Wait()

    fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {

    defer wg.Done()

    heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {

    if k == 1 {
        arr = append(arr, prefix)
        permutationsMutex.Lock()
        permutations++
        permutationsMutex.Unlock()
    } else {
        heapPermutation(k-1, prefix, arr)

        for i := 0; i < k-1; i++ {
            if k%2 == 0 {
                arr[i], arr[k-1] = arr[k-1], arr[i]
            } else {
                arr[0], arr[k-1] = arr[k-1], arr[0]
            }
            heapPermutation(k-1, prefix, arr)
        }
    }
}