2

作为一个练习，我正在尝试在 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
}

但是，当我运行它时，我收到一个错误，声称程序已死锁！我很困惑是什么导致了这个......

提前致谢，

莱纳斯

4

1 回答 1

3

该代码有一个问题，并且至少有一个潜在的错误用例：

  1. 它缺少一个基本案例。考虑如果quicksort要求对空切片进行排序会发生什么。
  2. 第一次调用quicksort时，比如在 a 中main()，如果你不在单独的 goroutine 中生成排序器，运行顶层排序的主线程可能会阻止尝试写回通道（取决于顶层通道本身是否缓冲的）。

例如：

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

并且在此处写入顶级通道时，主线程将死锁。

对比一下如果我们在顶层创建一个 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)
    }
}

现在我们避免了那个特殊的死锁问题。

于 2013-06-07T19:26:30.740 回答