Goroutines kelihatan terganggu walaupun wujud WaitGroup

Kandungan soalan

Saya ada masalah goroutine tidak tamat walaupun wujud waitgroup. Dalam kod yang dilampirkan, anda boleh melihat pelaksanaan algoritma pilih atur timbunan. Saya mahu mempercepatkan perkara, jadi saya mencipta goroutine untuk setiap nombor pertama yang mungkin, dengan itu mengurangkan pilih atur setiap goroutine kepada (n-1)!。总的来说，我应该仍然有 n! 排列 (n*(n-1)!= n!)，但我的主例程似乎在子例程完成之前退出。然后我尝试跟踪执行的排列。与我的信念相反，执行的排列数量不是恒定的，但在 n! 下总是有点（对于低 n）或非常多（对于大 n).

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

Dari mana datangnya perangai ini? Bagaimana untuk memastikan bahawa semua goroutine telah selesai sebelum program utama keluar?

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

(Tingkah laku yang sama boleh dicapai dengan mudah, cth. di https://go.dev/play/, jadi ia sangat boleh dihasilkan semula.)

Jawapan betul

Dalam kod anda, goroutine mengakses serentak Pada nilai permutations 变量。当您增加 n , beban kerja bertambah, yang boleh menjadi masalah yang membawa kepada hasil yang tidak dijangka.

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

Atas ialah kandungan terperinci Goroutines kelihatan terganggu walaupun wujud WaitGroup. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!