作为练习,我尝试在 Go 中实现快速排序的并行版本。这是我到目前为止所拥有的:
func quicksort(nums []int, ch chan int, level int, threads int) {
level *= 2;
if len(nums) == 1 { ch<- nums[0]; close(ch); return }
less := make([]int, 0)
greater := make([]int,0)
pivot := nums[0]
nums = nums[1:]
for _,i := range nums{
switch{
case i <= pivot:
less = append(less,i)
case i > pivot:
greater = append(greater,i)
}
}
ch1 := make(chan int, len(less))
ch2 := make(chan int, len(greater))
if(level <= threads){
go quicksort(less, ch1, level, threads)
go quicksort(greater,ch2, level, threads)
}else{
quicksort(less,ch1, level, threads)
quicksort(greater,ch2, level, threads)
}
for i := range ch1{
ch<-i;
}
ch<-pivot
for i := range ch2{
ch<-i;
}
close(ch)
return
}
但是,当我运行它时,我收到一条错误消息,声称程序已死锁!我很困惑到底是什么原因造成的......
提前致谢,
莱纳斯
最佳答案
该代码有一个问题,并且至少有一个潜在的错误用例:
- 缺少基本案例。考虑一下如果要求
quicksort
对空 slice 进行排序会发生什么。 - 当第一次调用
quicksort
时,比如在main()
中,如果您没有在单独的 goroutine(主线程)中生成排序器,运行顶级排序,可以阻止尝试写回 channel (取决于顶级 channel 本身是否被缓冲)。
例如:
func main() {
x := []int{3, 1, 4, 1, 5, 9, 2, 6}
ch := make(chan int)
quicksort(x, ch, 0, 0) // buggy!
for v := range(ch) {
fmt.Println(v)
}
}
这是有问题的,因为它要求主线程进行排序,但它不可避免地会在 quicksort
的这一部分阻塞:它无法与自身通信!
for i := range ch1{
ch<-i;
}
正是在写入顶级 channel 时,主线程才会死锁。
将此与我们在顶层创建 goroutine 时发生的情况进行对比:
func main() {
x := []int{3, 1, 4, 1, 5, 9, 2, 6}
ch := make(chan int)
go quicksort(x, ch, 0, 0)
for v := range(ch) {
fmt.Println(v)
}
}
现在我们避免了这个特定的死锁问题。
关于parallel-processing - Go中并行快速排序的死锁,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16987606/