0

http://play.golang.org/p/Xn3Qw7xAi3

很难理解渠道。

在这里我有

func main() {
  in := make(chan int)
  out := make(chan int)
  go QuickSort(in, out)

  for i := 0; i < 100; i++ {
    in <- rand.Intn(1000)
  }
  close(in)

  for i := range out {
    fmt.Println(i)
  }
}

这使得名为 in、out 和 goroutine 的两个通道成为函数 Quicksort。

1. QuickSort 如何将参数作为参数输入和输出？它是否从下面的行接收？

  in <- rand.Intn(1000)

2.这种情况下使用渠道是最优的吗？动态接收值看起来很整洁......没有通道排序会有什么不同？这种情况比较快？

4

3 回答 3

2

我写了它的原始版本！

我原来的文章回答了你的第二个问题，我认为......

只是为了好玩 - 基于频道的快速排序。

有趣的是，您可以在不索引输入的情况下进行快速排序。比较可能是 O(n log n)，但通道和 go 例程是 O(n)，所以可能不是最有效的快速排序；-)

如果你给它排序输入，它也有最坏的情况复杂度 O(n²)，所以不要那样做！

这真的很有趣——但它使用了大量的通道和 goroutines，这将使它比传统的快速排序更慢并且使用更多的内存。

于 2013-11-12T15:23:55.717 回答
1

1. QuickSort 如何将参数作为参数输入和输出？它是否从下面的行接收？

此代码将 100 个随机数推入称为“in”的通道。您之前将此通道的引用传递给了快速排序函数。这与我将一个函数传递一个线程安全堆栈，然后从调用者上下文将一个新元素推送到该堆栈上的想法相同。

  for i := 0; i < 100; i++ {
    in <- rand.Intn(1000)
  }
  close(in)

2.这种情况下使用渠道是最优的吗？动态接收值看起来很整洁......没有通道排序会有什么不同？这种情况比较快？

我认为这是一个很酷的玩具示例，说明了如何灵活地使用通道（以及流式排序）。在最常见的情况下，获取切片并调用sort.Sort通常会更快/更容易。同样值得注意的是，在大多数实际情况下，您将通过创建带有缓冲区的通道来获得更好的吞吐量，因为这将减少 goroutine 之间的调度程序切换。通道非常快，但它们仍然有开销，如果您实际上没有并行处理，那么开销不会给您带来任何好处。

如果您想并行处理，请不要忘记设置 GOMAXPROCS > 1 并使用缓冲通道。

于 2013-11-11T21:29:47.553 回答
-1

问题 1 的答案是肯定的。示例中的 QuickSort 需要两个通道作为参数，一个用于读取整数，一个用于在排序后写入整数。这与在带有 stdin 和 stdout 的 unix 命令行上使用 sort 非常相似。

至于问题 2 的答案，这只是一个使用 Go Channels 和 goroutine 解决标准问题的例子。如果您在等待排序返回时还有其他工作要做，那只会更快。

此代码中真正可能的加速是在 QuickSort 函数中使用通道和 goroutine。如果您的底层硬件有足够的内核允许您对程序进行多线程处理，这可能比单线程版本快得多。

Go 通道和线程的重点是让您可以轻松利用底层硬件，而不会遇到编写线程代码的困难。为了进行比较，请查看此版本的基于 pthread 的快速排序并将其与 go 代码进行比较。

http://sc12.supercomputing.org/hpceducator/PythonForParallelism/codes/parallelQuicksort.c

于 2013-11-11T21:36:33.623 回答