1

スレッドを使用してソート アルゴリズム (クイックソート) を最適化しようとしています。std::sort() 実装ですでにかなり優れていることはわかっていますが、コンピューターの最適化でそれを打ち負かし、同時にスレッドについて学習しようとしています。

それで、私の質問は、再帰的なクイックソート機能でスレッドをどのように使用するのですか?

これが関数です（質問にとって重要ではないものは削除されています）：

template <typename T>
void quicksort(T arr[], const int &size, const int &beginning, const int &end)
{
    // Algorithm here
    thread t1(quicksort, arr, size, beginning, slow - 1);
    thread t2(quicksort, arr, size, slow + 1, end);
}

私が間違っていて、さらに多くのコードが必要になった場合は、お知らせください。更新します。

私はVisual Studio 2012を使用していますが、現在、エラーは次のように述べています。

error C2661: 'std::thread::thread' : no overloaded function takes 5 arguments

また、各パラメーターで ref(arr) などを呼び出してみましたが、同じエラーが発生しました。

編集: @mfontanini による解決策を試した後、エラーなしでコンパイルできますが、実行すると次のようになります:

Debug Error!

Program: ...sktop\VisualStudio\Projects\SpeedTester\Debug\SpeedTester.exe

R6010
- abort() has been called


(Press Retry to debug the application)

何度も何度も繰り返しました。最終的に、コード 3 で終了します。

4

2 に答える 2

1

あなたの主な問題は、おそらく、スポーンする必要がjoin()あることです。事前または実装呼び出しthreadなしでスレッド オブジェクトが破棄された場合。join()detach()std::terminate()

detach()全体的な並べ替えを完了するには、すべての部分的な並べ替えが完了していることを知る必要があるため、必要はありません。したがって、ingjoinは正しいことです。

さらに、改善できる点がいくつかあります。

  • ints を参照渡ししないでください。値渡しは、単純なスカラー型の場合により効率的であり、他のスレッドからローカル変数を参照することは、一般的にはお勧めできません (正当な理由とプロトコルがない限り)。
  • あまりにも多くのスレッドを開始します。パーティショニング後、2 つのサブソート用に 2 つのスレッドが必要ですが、3 つ必要です。現在のスレッドも引き続き実行されるため、新しいスレッドを 1 つだけ作成し、現在のスレッドで他のサブソートを実行する必要があります。（そしてjoin()、完了したら他の部分。）
  • パーティションが小さくなったときに、新しいスレッドを作成し続けるべきではありません。再帰のオーバーヘッドがアルゴリズムの複雑さの利点よりも高くなるため、通常は、クイックソートにカットオフ サイズを設定し、小さいサイズには非再帰的なもの (挿入ソートなど) を使用することをお勧めします。同時ソートでは、同様のカットオフがさらに重要です。スレッドのオーバーヘッドは、単純な再帰呼び出しよりもはるかに高く、小さい (そして近くにある) パーティションでは、スレッドが同じキャッシュ ラインに頻繁にアクセスし始め、速度が低下します。さらに。
  • 一般に、無制限にスレッドを作成することはお勧めできません。それは最終的にプラットフォームの制限に達します。使用するスレッドの数を制限する (アトミック カウンターを使用) かstd::async、既定の起動ポリシーなどを使用して、プラットフォームが処理できる以上のスレッドを起動しないようにすることができます。
于 2013-02-24T13:38:56.777 に答える