前言
最近在用Go并发实现n皇后问题中遇到很多的坑，在此进行记录。
n后问题以及单线程实现
n后问题：简单来说就是在n*n的棋盘上放置n个皇后，使每两者之间都不在同一行，同一列，同一斜线上。求满足条件的解的个数？
// array[i] 代表第 i 行n皇后放置位置为第 arry[i] 列，index代表当前要放置皇后的行号
type Process struct {
array []int
index int
}
// 检查该行放置后会不会冲突
func check(process Process) bool {
array := process.array
k := process.index
for i := 0; i < k; i++ {
if array[i] == array[k] {
return true
}
if int(math.Abs(float64(array[k]-array[i]))) == k-i {
return true
}
}
return false
}
func NQueen(process Process, n int) int {
if process.index >= n {
return 1
}
res := 0
for j := 0; j < n; j++ {
process.array = append(process.array, j)
if check(process) == false {
process.index++
res += NQueen(process, n)
process.index--
}
process.array = process.array[:len(process.array)-1]
}
return res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
return NQueen(process, n)
}
func main() {
fmt.Println(Provide(12))
}
错误的并发代码
思路：创建协程去执行 NQueen 函数，并将结果放入 channel，最后累加得到最终结果。于是，代码可能是下面这个样子的：
// 其他函数不变
func NQueen(ch chan int, process Process, n int) {
if process.index >= n {
ch <- 1
return
}
count := 0
newch := make(chan int, n)
for j := 0; j < n; j++ {
process.array = append(process.array, j)
if check(process) == false {
process.index++
count++
go NQueen(newch, process, n)
process.index--
}
process.array = process.array[:len(process.array)-1]
}
res := 0
for i := 0; i < count; i++ {
res += <-newch
}
ch <- res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
ch := make(chan int, 1)
NQueen(ch, process, n)
return <-ch
}
这样，你可能发现，答案并不是我们预期的那样。
分析：
（1）这里只传入同一个 process 实例，那么多个协程同时对他们操作，不加以控制的话，肯定会出现问题；所以我们给每个协程一份单独的 process 实例。
（2）第二个，我们着重来讲 process.array = append(process.array, j) 问题。
append函数机制
首先明确我们的需求：重新开辟内存空间，值为原来数组切片基础上，增加一个元素
append机制：
当切片还有可用容量，调用append，会将值直接加到切片中，这时原切片和现切片共用底层数组，所以地址相同。
而当容量不足，系统会重新开辟一块儿内存，所以原切片和现切片底层数组不同。
func main() {
ch := make([]int, 5)
ch = append(ch, 1, 2, 3, 4)
fmt.Printf("%p\n", ch)
aa := append(ch, 5)
fmt.Printf("%p\n", aa)
bb := append(ch, 5, 6)
fmt.Printf("%p\n", bb)
}
所以，我们每次初始化新的切片，使系统分配不同的内存空间。
代码实现
type Process struct {
array []int
index int
}
func check(process Process) bool {
array := process.array
k := process.index - 1
for i := 0; i < k; i++ {
if array[i] == array[k] {
return true
}
if int(math.Abs(float64(array[k]-array[i]))) == k-i {
return true
}
}
return false
}
func NQueen(ch chan int, process Process, n int) {
if process.index >= n {
ch <- 1
return
}
count := 0
newch := make(chan int, n)
for j := 0; j < n; j++ {
newProcess := Process{
array: make([]int, 0),
index: process.index + 1,
}
newProcess.array = append(newProcess.array, process.array...)
newProcess.array = append(newProcess.array, j)
if check(newProcess) == false {
count++
go NQueen(newch, newProcess, n)
}
}
res := 0
for i := 0; i < count; i++ {
res += <-newch
}
ch <- res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
ch := make(chan int, 1)
NQueen(ch, process, n)
return <-ch
}
func main() {
fmt.Println(Provide(8))
}
如何限流
何为限流，就是同一时刻创建恒定个协程。这里我们用channel来进行限流。
type Process struct {
array []int
index int
}
func check(process Process) bool {
array := process.array
k := process.index - 1
for i := 0; i < k; i++ {
if array[i] == array[k] {
return true
}
if int(math.Abs(float64(array[k]-array[i]))) == k-i {
return true
}
}
return false
}
var channel = make(chan int, 5)
func NQueen(ch chan int, process Process, n int) {
<-channel
if process.index >= n {
ch <- 1
return
}
count := 0
newch := make(chan int, n)
for j := 0; j < n; j++ {
newProcess := Process{
array: make([]int, 0),
index: process.index + 1,
}
newProcess.array = append(newProcess.array, process.array...)
newProcess.array = append(newProcess.array, j)
if check(newProcess) == false {
channel <- 1
count++
go NQueen(newch, newProcess, n)
}
}
res := 0
for i := 0; i < count; i++ {
res += <-newch
}
ch <- res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
ch := make(chan int, 1)
channel <- 1
NQueen(ch, process, n)
return <-ch
}
func main() {
fmt.Println(Provide(8))
}
网友评论