Golang range through channel 在实现堆排列算法时具有奇怪的行为

Question

我试图在 go 使用频道中实现 Heap's Algorithm。当仅在屏幕上打印切片时，下面的代码工作正常，但是当使用通道将数组传递到 main 函数上的 for/range 循环时，会发生一些意外行为并且 slices/arrays 以口是心非的方式打印并且并非所有排列都已发送。我想也许我在主要功能能够打印结果之前关闭频道，但我不希望双重打印。为什么会发生这种情况，我该如何让它发挥作用。

package main

import "fmt"

func perm(a []int64) {
    var n = len(a)
    var c = make([]int, n)
    fmt.Println(a)
    i := 0
    for i < n {
        if c[i] < i {
            if i%2 == 0 {
                a[0], a[i] = a[i], a[0]
            } else {
                a[c[i]], a[i] = a[i], a[c[i]]
            }
            fmt.Println(a)
            c[i]++
            i = 0
        } else {
            c[i] = 0
            i++
        }
    }
}

func permch(a []int64, ch chan<- []int64) {
    var n = len(a)
    var c = make([]int, n)
    ch <- a
    i := 0
    for i < n {
        if c[i] < i {
            if i%2 == 0 {
                a[0], a[i] = a[i], a[0]
            } else {
                a[c[i]], a[i] = a[i], a[c[i]]
            }
            ch <- a
            c[i]++
            i = 0
        } else {
            c[i] = 0
            i++
        }
    }
    close(ch)
}

func main() {
    var i = []int64{1, 2, 3}
    fmt.Println("Without Channels")
    perm(i)
    ch := make(chan []int64)
    go permch(i, ch)
    fmt.Println("With Channels")
    for slc := range ch {
        fmt.Println(slc)
    }

}

Answer 1

你的问题是切片是引用类型，并且在多个协程中被访问。在 perm 中，您在完成每个步骤的处理后直接打印 a。在 permch 中，您正在通过频道发送 a，但随后立即开始再次修改它。由于通过通道发送的每个切片都引用相同的底层数组，因此您有一个竞争条件，即您的下一个循环迭代是否改变 a 或您在 main 中的 Println() 调用首先到达该数组。

一般来说，如果您在任何使用 goroutine 的程序中运行遇到意外行为，您可能存在竞争条件。运行带-race标志的程序看在哪

编辑： 另外，关闭频道对频道中的例程读取没有影响。可以继续读取通道，直到其缓冲区为空，此时它将开始返回该类型的零值。通道上的范围循环只会在通道关闭后终止并且其缓冲区为空。

Answer 2

看起来 permch 在修改 a 的同时 main 正在打印它，所以你的输出是乱码。

我可以想到三个简单的修复方法：

使用互斥锁保护对 a 的访问。
在频道上复制 a：
从 main 打印出某种 return 信号，permch 可以继续。（真的不推荐这个，但它有效）。

数字 2 非常简单：

a2 := make([]int64, len(a))
copy(a2,a)
ch <- a2

这是我推荐的。

对于#1，只需将var m sync.Mutex 声明为包变量，而Lock 是您读取或修改a 的任何时间。正如您所指出的，这是 reader 和下一个修改之间的竞争条件，所以它可能不是一个好的解决方案。

fixed version on playground using #3

Golang range through channel 在实现堆排列算法时具有奇怪的行为

Golang range through channel with odd behaviour when inplementing Heap's permutation algorithm

permutation

range

go

channels

heaps-algorithm