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 という名前の 2 つのチャネルが Quicksort 関数になります。

1. QuickSort はどのように引数として取り込み、取り出しますか? 以下のラインから受信しますか？

  in <- rand.Intn(1000)

2. この場合、チャネルを使用するのが最適ですか? 動的に値を受け取るのはかなりきれいに見えます...チャネルなしでソートするだけで何が違うのでしょうか? このケースは速いですか？

4

3 に答える 3

2

そのオリジナル版を書きました！

私の元の記事は、あなたの2番目の質問に答えていると思います...

楽しみのために - チャンネルベースのクイックソート。

入力をインデックス化できなくてもクイックソートを作成できるのは興味深いことです。比較の場合は O(n log n) かもしれませんが、チャネルと go ルーチンの場合は O(n) なので、おそらくこれまでで最も効率的なクイックソートではありません ;-)

また、ソートされた入力を入力すると、最悪の場合の複雑さ O(n²) になるため、そうしないでください。

これはちょっと楽しいですが、非常に多くのチャネルと goroutine を使用するため、従来のクイックソートよりも遅くなり、より多くのメモリを使用します。

于 2013-11-12T15:23:55.717 に答える
1

1. QuickSort はどのように引数として取り込み、取り出しますか? 以下のラインから受信しますか？

このコードは、「in」と呼ばれるチャネルにランダムに 100 個をプッシュします。以前に、このチャネルへの参照をクイックソート関数に渡しました。これは、関数にスレッドセーフ スタックを渡し、呼び出し元のコンテキストから新しい要素をそのスタックにプッシュするのと同じ考え方です。

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

2.この場合、チャネルを使用するのが最適ですか? 動的に値を受け取るのはかなりきれいに見えます...チャネルなしでソートするだけで何が違うのでしょうか? このケースは速いですか？

これは、チャネルをいかに柔軟に使用できるか (およびストリーミングの種類) を示すクールなおもちゃの例だと思います。ほとんどの一般的なケースでは、通常、スライスを取得してsort.Sortを呼び出す方がはるかに高速/簡単になります。また、実際のほとんどのケースでは、 buffer を使用してチャネルを作成することでスループットが向上することに注意してください。これにより、ゴルーチン間のスケジューラーの切り替えが減少するためです。チャネルは非常に高速ですが、それでもオーバーヘッドがあり、実際に並行して処理していない場合、そのオーバーヘッドは何のメリットもありません。

並行して処理したい場合は、GOMAXPROCS > 1 に設定し、バッファリングされたチャネルを使用することを忘れないでください。

于 2013-11-11T21:29:47.553 に答える
-1

質問 1 の答えはイエスです。この例の QuickSort は引数として 2 つのチャネルを想定しています。1 つは int を読み取り、もう 1 つはソート後に int を書き込みます。これは、stdin と stdout を使用して unix コマンド ラインで sort を使用するのと非常によく似ています。

質問 2 の答えについては、これは標準的な問題を解決するために Go チャネルと Go ルーチンを使用する例にすぎません。ソートが戻るのを待っている間に他の作業を行う場合にのみ、より高速になります。

このコードで可能な実際の高速化は、QuickSort 関数内でチャネルとゴルーチンを使用することです。基盤となるハードウェアに十分なコアがあり、プログラムをマルチスレッド化できる場合、これはシングル スレッド バージョンよりも大幅に高速になる可能性があります。

チャネルとスレッドの要点は、スレッド化されたコードを書くという困難なしに、基盤となるハードウェアを簡単に利用できるようにすることです。比較のために、このバージョンの pthread ベースのクイックソートを見て、go コードと比較してください。

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

于 2013-11-11T21:36:33.623 に答える