问题内容
尽管存在 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/ 上,因此它的重现性非常好。)
正确答案
在您的代码中,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) } } }