1

私はクイックソートの並列化に取り組んでおり、スレッドは最初の試みです。スレッド化されていないバージョンは正しくソートされますが、スレッド化されたものはそうではありません (驚くことではありません)。私が興味深いと思ったのは、スレッドを削除したが、boost::bind 呼び出しを維持したとき、まだ機能しないことでした。boost::bind が私が望むものではない場合は、提案を提供してください。バインドは、関数をブースト スレッドで動作させる最も簡単な (または唯一の) 方法のようです。

void Quicksort( fVec &Array, const int Left, const int Right )
{
    if( Right <= Left )
        return;

    int pivot = Left;
    const int pivotNewIndex = Partition( Array, Left, Right, pivot );

    // These function calls make it work fine
    //Quicksort( Array, Left, pivotNewIndex - 1 );
    //Quicksort( Array, pivotNewIndex + 1, Right );

    // boost::bind calls only swaps one element, doesn't actually sort
    boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
    boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();

    // threaded version that doesn't work, same as above
    //boost::thread threadA( boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 ) );
    //threadA.join();
    //boost::thread threadB( boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right ) );
    //threadB.join();
}
4

1 に答える 1

7

Boost bind は多かれ少なかれ、呼び出されたときに、必要な引数で必要な関数を呼び出すファンクターを作成します。この場合、ファンクターを作成していますが、決して呼び出していません。試す：

boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();

最初の引数がそれを台無しにしていると推測しています。バインドには引数をコピー可能にする必要があると思いますが、参照は実際にはそうではありません。おそらくコピーを作成して参照を渡すため、何も変更されていません。試す：

boost::bind( &Quicksort, boost::ref(Array), Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, boost::ref(Array), pivotNewIndex + 1, Right )();

fVec とは何か、および並べ替え対象の配列へのポインターを渡さない理由を知っておくと役立ちます。

また、このスレッド化の方法では、あまりスピードアップしない可能性が高いことに注意してください。これは、並べ替えが非常に小さいため、新しいスレッドの開始とスケジューリングのオーバーヘッドが利点よりもはるかに大きくなるためです (さらに、膨大な数のスレッドを作成することになります)。悪い）。本当に必要なのは、最適なサイズ以上のチャンクで動作し、固定数のスレッドを持つスレッドプールです。制限より小さいサイズに達すると、すべてが順次実行されます (さらに小さいサイズの場合は、明らかにクイックソートから挿入ソートに変更する必要があります)。

また、参加する順序はとにかくシリアル実行につながることに注意してください...両方のスレッドを開始した後に両方のスレッドに参加する必要があります。

于 2008-11-08T07:31:43.417 に答える