尽管存在 WaitGroup，Goroutines 似乎被中断了 [关闭]

Question

我有一个问题，尽管有 WaitGroup，但 goroutines 没有结束。在附加的代码中，您可以看到堆的排列算法的实现。我想加快速度，所以我为每个可能的第一个数字创建了一个 goroutine，从而将每个 goroutine 的排列减少到

(n-1)!

。总的来说，我应该还有

n!

排列（

n*(n-1)! = n!

），但我的主例程似乎在子例程完成之前就退出了。然后我尝试跟踪执行的排列。与我的信念相反，执行的排列数不是恒定的，但总是比

n

低一点（对于低

n

）或很多（对于大

n!

）。 例如。

n=4

的排列每次都是 24，即

4!

因此所有的 goroutines 都完成了。但是如果我有一个更大的数字，比如

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/ 上，因此它非常可重现）

提前致谢。

Answer 1

在您的代码中，goroutines 并发访问

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)
        }
    }
}