duanduan8439 2016-06-06 01:01
浏览 30
已采纳

Golang实现生成器/带通道产量:奇数通道行为

The following code implements the yield pattern in golang. As an experiment I was implementing an all permutations generator. However, when I return the slice A to channel, if I do not create a new copy of the array I get an incorrect result.

Please see the code around "???". Can someone explain what happens under the covers here? I thought that since the channel is not buffered, I was guaranteed that after publishing the array's slice to the channel I was ensured that the result would be consumed before continuing.

package main

import (
    "fmt"
)

func swap(A []int, i int, j int) {
    t := A[i]
    A[i] = A[j]
    A[j] = t
}

func recurse(A []int, c chan []int, depth int) {

    if depth == len(A) {
        // ??? Why do I need to copy the data?
        // If I do c <- A I get an incorrect answer.
        ra := make([]int, len(A))
        copy(ra, A)
        c <- ra
        return
    }

    for i := depth; i < len(A); i++ {
        swap(A, depth, i)
        recurse(A, c, depth+1)
        swap(A, depth, i)
    }
}

func yieldPermutations(A []int, c chan []int) {
    recurse(A, c, 0)
    close(c)
}

func main() {
    A := []int{1, 2, 3}
    c2 := make(chan []int)

    go yieldPermutations(A, c2)
    for v := range c2 {
        fmt.Println(v)
    }
}

If I do not copy the data, I get the following result:

[1 3 2]
[1 3 2]
[2 3 1]
[2 3 1]
[3 1 2]
[3 1 2]

Obviously, the correct result (which we get with data copy) is:

[1 2 3]
[1 3 2]
[2 1 3]
[2 3 1]
[3 2 1]
[3 1 2]
  • 写回答

1条回答 默认 最新

  • douji9734 2016-06-06 02:56
    关注

    It's a mistake to think this code is like generators/yield in Python, and that's what's causing your error.

    In Python, when you request the next item from a generator, the generator starts executing and stops when the next yield <value> statement is reached. There is no parallelism in Python's generators: the consumer runs until it wants a value, then the generator runs until it produces a value, then the consumer gets the value and continues execution.

    In your go code, the goroutine executes concurrently with the code that's consuming items. As soon as an item is read from the channel from the main code, the goroutine works concurrently to produce the next. The goroutine and the consumer both run until they reach the channel send/receive, then the value is sent from the goroutine to the consumer, then they both continue execution.

    That means the backing array of A gets modified concurrently as the goroutine works to generate the next item. And that's a race condition which causes your unexpected output. To demonstrate that this is a race, insert time.Sleep(time.Second) after the channel send. Then the code produces the correct results (albeit slowly): https://play.golang.org/p/uEa_k6Brcc

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?