Les Goroutines semblent interrompues malgré l'existence de WaitGroup

Contenu de la question

J'ai un problème avec la goroutine qui ne se termine pas malgré l'existence du groupe d'attente. Dans le code ci-joint, vous pouvez voir l'implémentation de l'algorithme de permutation de tas. Je voulais accélérer les choses, j'ai donc créé une goroutine pour chaque premier numéro possible, réduisant ainsi les permutations de chaque goroutine à (n-1)!。总的来说，我应该仍然有 n! 排列 (n*(n-1)!= n!)，但我的主例程似乎在子例程完成之前退出。然后我尝试跟踪执行的排列。与我的信念相反，执行的排列数量不是恒定的，但在 n! 下总是有点（对于低 n）或非常多（对于大 n).

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

D'où vient ce comportement ? Comment s'assurer que toutes les goroutines sont terminées avant la fin du programme principal ?

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

(Le même comportement peut être facilement obtenu, par exemple sur https://go.dev/play/, donc c'est très reproductible.)

Bonne réponse

Dans votre code, goroutine accède simultanément aux valeurs de permutations 变量。当您增加 n , la charge de travail augmente, ce qui peut devenir un problème entraînant des résultats inattendus.

Vous pouvez utiliser 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)
        }
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!