アレイの回転をより効率的にする方法はありますか？

Question

円形アレイの回転をより効率的にするにはどうすればよいですか？私は優秀なソートアルゴリズムについては、このthreadで読み、それが中央に並べ替えます、配列の末尾のスペースがあるので、私は必要なもののために動作しません。

回転機能は、左右回転の両方のために働く必要があります。アレイのすべてのスペースが満たされるわけではありません。

void Quack::rotate(int r) 
{ 
    if(r > 0) //if r is positive, rotate left 
    { 
     for(int i = 0; i < r; i++) 
      items[(qBack + i) % qCapacity] = items[(qFront + i) % qCapacity]; 
      //move items in array 
    } 
    else if(r < 0) //if r is negative, rotate right 
    { 
     for(int i = 0; i < (r * -1); i++) 
      items[(qFront - i - 1) % qCapacity] = 
       items[(qBack - i - 1) % qCapacity]; 
      //move items in array 
    } 
    //if r = 0, nothing happens 

    //rotate front and back by r 
    qFront = (qFront + r) % qCapacity; 
    qBack = (qBack + r) % qCapacity; 
} 

Answer 1

私はそれを使用していないので、あなたが必要とするすべてを行うことはできません。しかし、単にこの関数本体をstd::rotate関数に置き換えることを検討したいかもしれません。

それはすでによく最適化されなければならない、とはるかに少ないアプリケーションにバグを導入する可能性が高くなります。

http://www.sgi.com/tech/stl/rotate.html

あなたがが最適化のための提案をしたい場合は、私はすべての剰余演算を避けることをお勧めします。彼らはあなたのプロセッサで実行できる最も高価な操作の1つである除算を必要とするかもしれません。彼らはあなたの目標を達成する方法を考えるのに便利な方法ですが、あなたのCPUが実行するには非常にコストがかかるかもしれません。最後に真ん中から1、そして真ん中に初めから他：あなたは二つのループを使用する場合

あなたは剰余演算子を削除することができます。

しかし、あなたは完全に回転を行うことを避けることができれば、あなたは、見ることができます。慎重であれば、無意味な完全配列トラバーサル/コピー操作を排除できる可能性があります。これを達成する方法については、OPに関するコメントを参照してください。