0

私は現在、クイックソート アルゴリズムの実装を書いています。特に配列の分割について、効率性に疑問があります。並べ替えの前に配列を分割する方法には、ピボットまたは分割要素を選択して配列の最初の要素にする必要があり (最も効率的な方法ではないことはわかっています)、次に 2 つの変数「high」を設定します。および "low" - それぞれ配列の最後のインデックスと最初のインデックスになります。特定の要素を切り替えて、それらが等しくなるまで低値と高値をインクリメントおよびデクリメントすることにより、配列を分割する while ループのセットアップがあります。

私の質問は、switch ステートメントを使用して、移動するインデックスを制御するのではなく、2 つの個別の while ループを設定することです。この場合、switch ステートメントを使用するとより効率的ですか?

関連するコードは次のとおりです。

    //used to determine which side of the array to move the element to
    #define RIGHT 1
    #define LEFT 0

    void partition( int nums[], int size )
    {
         int pivot = nums[0], low = 0, high = size - 1, turn = LEFT;

         while ( low != high )
         {

             switch (turn)
             {
                case RIGHT:
                     if ( nums[low] >= pivot )
                     {
                         nums[high] = nums[low];
                         high--;
                         turn = LEFT;
                     }
                     else
                         low++;
                     break;

                case LEFT:
                     if ( nums[high] <= pivot )
                     {
                         nums[low] = nums[high];
                         low++;
                         turn = RIGHT;
                     }
                     else
                         high--;
                     break;
            }
        }

        nums[low] = pivot;
     }
4

2 に答える 2

1

私の推測では2つのループですが、測定してください

通常、不変式をループの外に移動することをお勧めします。この最適化は、コードホイストと呼ばれます。またはループ不変コードモーション。 明らかな理由で勝ちます。さて、あなたの場合、何が不変であるかはコンパイラーには明らかではありませんが、ターン変数はlowおよびhighよりもバリアントが少ないことがわかっています。

したがって、私の推測では、2 つのループの方が優れていると思いますが、確実に知る唯一の方法は、それを測定することです。

于 2013-01-22T05:21:54.863 に答える
1

実際に試してみないとわかりません。コンパイラは、驚くべきことを行うことがあります (驚くほど良いことも悪いことも)。一般に、状態はプログラムカウンターに保持されるため、2 つのループに移動する方が高速であると予想されますが、コンパイラーはそれ以上のことを行う可能性があります。また、コンパイル時の最適化設定によっても異なります。

于 2013-01-22T05:12:56.163 に答える