实施Heap的置换算法时Golang范围内的通道具有奇怪的行为

I was trying to implement Heap's Algorithm in go using channels. The code below is working fine when just printing the slices on the screen, but when using channels to delivery the arrays to a for/range loop on main function some unexpected behaviour occurs and the slices/arrays are printed in duplicity and not all permutations are sent. I thought that maybe i'm closing the channel earlier than the main function is able to print the results but i wouldn't expect that double print. Why is this happening and how can i make it work.

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

}

2个回答

It looks like permch is modifying a at the same time as main is printing it, so your output is garbled.

I can think of three easy fixes:

  1. Guard access to a with a mutex.
  2. Put a copy of a on the channel:
  3. Have some kind of return signal from main that it has printed and permch can continue. (don't really recommend this, but it works).

Number 2 is pretty simple:

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

and is what I would recommend.

For #1, just declare a var m sync.Mutex as a package variable and Lock is anytime you read or modify a. This is a race condition though between the reader and the next modification, as you pointed out, so it probably isn't a good solution after all.

fixed version on playground using #3

dswm97353
dswm97353 当我尝试使用Mutexes时,我可以使比赛检测程序静音,但无法获取我想要的是无频道版本的行为.play.golang.org / p / fSt9MfIyOi
3 年多之前 回复
dowjgrm6787
dowjgrm6787 它对我不起作用,正如我预期的那样:play.golang.org/p/QuD0aE3tQH
3 年多之前 回复
doushibu2453
doushibu2453 是的#1在那种比赛条件下不太好。 查看修改。
3 年多之前 回复
dongyanjing5975
dongyanjing5975 您能告诉我如何实施#1或#2吗? 我认为添加另一个从main到goroutine的信号通道有点麻烦。 我试过使用内置的copy()和make()创建一个新的基础数组,但是我认为问题取决于在permch更改它的同时主要打印该数组。 而且我真的不知道如何使用互斥锁,因为我可以将部分锁定在更改数组的permch中,但是它不能保证它将等待main()打印数组。
3 年多之前 回复



您的问题是切片是引用类型,并且正在多个goroutine中进行访问。 在 perm </ code>中,您要在完成每个步骤的处理后直接打印 a </ code>。 在 permch </ code>中,您正在通过通道发送 a </ code>,但随后立即开始再次对其进行修改。 由于通过通道发送的每个切片都引用相同的基础数组,因此您有一个竞争条件,即您的下一个循环迭代是否更改main中的 a </ code>或您的 Println()</ code>调用 </ p>

通常,如果您在使用goroutines的任何程序中遇到意外行为,则可能</ em>存在竞争条件。 使用 -race </ code>标志运行程序以查看位置。</ p>

编辑:</ strong>另外,关闭通道对例程没有影响 从频道阅读</ em>。 可以继续读取通道,直到其缓冲区为空,这时它将开始返回该类型的零值。 通道的范围循环仅在通道关闭并且其缓冲区为空</ em>时终止。</ p>
</ div>

展开原文

原文

Your problem is that slices are reference types, and are being accessed in multiple goroutines. In perm, you're printing a directly as you finish processing it at each step. In permch, you're sending a over the channel, but then immediate starting to modify it again. Since each slice sent over the channel refers to the same underlying array, you have a race condition as to whether your next loop iteration alters a or your Println() call in main gets to that array first.

In general, if you're running into unexpected behavior in any program using goroutines, you probably have a race condition. Run the program with the -race flag to see where.

Edit: also, closing a channel has no effect on a routine reading from the channel. A channel can continue to be read until its buffer is empty, at which point it will start returning the zero value for that type instead. Range loops over a channel will only terminate once the channel is closed and its buffer is empty.

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐