Goroutinen scheinen trotz der Existenz von WaitGroup unterbrochen zu sein

Frageninhalt

Ich habe ein Problem damit, dass Goroutine trotz der Existenz einer Wartegruppe nicht endet. Im beigefügten Code können Sie die Implementierung des Heap-Permutationsalgorithmus sehen. Ich wollte die Dinge beschleunigen, also habe ich für jede mögliche erste Zahl eine Goroutine erstellt und so die Permutationen jeder Goroutine auf (n-1)!。总的来说，我应该仍然有 n! 排列 (n*(n-1)!= n!)，但我的主例程似乎在子例程完成之前退出。然后我尝试跟踪执行的排列。与我的信念相反，执行的排列数量不是恒定的，但在 n! 下总是有点（对于低 n）或非常多（对于大 n) reduziert.

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

Woher kommt dieses Verhalten? Wie kann sichergestellt werden, dass alle Goroutinen abgeschlossen sind, bevor das Hauptprogramm beendet wird?

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

(Das gleiche Verhalten kann leicht erreicht werden, z. B. auf https://go.dev/play/, daher ist es sehr reproduzierbar.)

Richtige Antwort

In Ihrem Code greift Goroutine gleichzeitig auf Werte von permutations 变量。当您增加 n zu , erhöht sich die Arbeitsbelastung, was zu einem Problem werden kann, das zu unerwarteten Ergebnissen führt.

Sie können mutex，它将确保当时只有一个goroutine可以访问permutations verwenden.

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

Das obige ist der detaillierte Inhalt vonGoroutinen scheinen trotz der Existenz von WaitGroup unterbrochen zu sein. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!