配列内の単純なデータ型を特定の位置に移動する最も速い方法

Question

既知のサイズの配列で単純なデータ型を特定の位置に移動する最も速い方法は何ですか？

私はintとして記憶されたゲームボードを回転していた特定の場合には、[9]
[0,1,2,3,4,5,6,7,8]私はそれぞれ回転に必要なこれらの配列のベクトルを持っていた私のユースケースで[6,3,0,7,4,1,8,5,2]

---

となります。

基板レイアウト：

board1|corners|centers 
0 1 2 | 0 2 | 1 
3 4 5 |  | 3 5 
6 7 8 | 6 8 | 7 

board2|corners|centers 
6 3 0 | 6 0 | 3 
7 4 1 |  | 7 1 
8 5 2 | 8 2 | 5 

私が思いついた最速の方法は、に配列エントリを割り当てるためのパブリック変数を作成し、バックメモリにコピーすることでした。

私はそれがはるかに遅いクロックする..though
int[] b = new int[] {b[6], b[3], b[0], b[7], b[4], b[1], b[8], b[5], b[2]};
を推奨しています同様の質問 here、（単一スレッドの半分以下の速度）

---

どちらも比較的あるのを見てきた

int layout[9]; 
int pub_layout[9]; 

#include <cstring> // for std::memcpy 
void rotate(int layout[]) 
{ 
    pub_layout[4] = layout[4]; // center 

    pub_layout[0] = layout[6]; // corner four 
    pub_layout[6] = layout[8]; 
    pub_layout[8] = layout[2]; 
    pub_layout[2] = layout[0]; 

    pub_layout[1] = layout[3]; // center four 
    pub_layout[3] = layout[7]; 
    pub_layout[7] = layout[5]; 
    pub_layout[5] = layout[1]; 

    std::memcpy(layout,pub_layout,sizeof(pub_layout)); 
} 

高速（see a test here）

これが最速の方法でない場合は、何ですか？
私はアルゴリズムがCとC++の両方で同じであると思われます。

Answer 1

これで、memcpy呼び出しと[4]〜[4]割り当てを得ることができます。変数putAsideに対する2つの割り当てを失います。だから、確かに少し速いです。

int layout[9]; 
int putAside; 

void rotate(int[] layout) 
{ 
    putAside = layout[0]; 
    layout[0] = layout[6]; // corner four 
    layout[6] = layout[8]; 
    layout[8] = layout[2]; 
    layout[2] = putAside; 

    putAside = layout[1]; 
    layout[1] = layout[3]; // center four 
    layout[3] = layout[7]; 
    layout[7] = layout[5]; 
    layout[5] = putAside; 
} 

Answer 2

最速の方法は、非常にタイトなループでプロセッサキャッシュを使用することが考えられます：

void rotate(int in[3][3], int out[3][3]) 
{ 
    int i, j, k; 
    for (i=0,k=2;i<3;i++,k--) 
     for (j=0;j<3;j++) 
      out[j][k] = in[i][j]; 
} 

注：board[9]はboard[3][3]に相当し、内で連続3つのintの3列として9つのint型を見てメモリなので、あなたが好きなら：

void rotate(int in[9], int out[9]) 
{ 
    int i, j, k; 
    for (i=0,k=2;i<3;i++,k--) 
     for (j=0;j<3;j++) 
      out[j*3+k] = in[i*3+j]; 
} 

あなたがして、inとoutが同じであることができることを要求されるべき次を使用する必要があります：あなたは任意の変換を適用するために、より柔軟な方法をしたい場合は

void rotate(int in[9], int out[9]) 
{ 
    int tmp[9]; 
    int i, j, k; 
    for (i=0,k=2;i<3;i++,k--) 
     for (j=0;j<3;j++) 
      tmp[j*3+k] = in[i*3+j]; 
    //memcpy(out,tmp, sizeof(tmp)); // use this... 
    for(i=0;i<9;i++) out[i]=tmp[i]; //..or this, whichever clocks faster 
} 

Answer 3

、次のようなものも非常に高速になります：

：

template <int _1, int _2, int _3, int _4, int _5, int _6, int _7, int _8, int _9> 
struct transfomer { 
    board& _in; 
    operator board() const { 
     return { _in[_1], _in[_2], _in[_3], _in[_4], _in[_5], _in[_6], _in[_7], _in[_8], _in[_9] }; 
    } 
}; 

void rotate3(board& layout) { 
    layout = transfomer<6, 3, 0, 7, 4, 1, 8, 5, 2>{layout}; 
} 

ここで私はとboardを定義しました

typedef array<int, 9> board; 

はい、暗黙の変換演算子（通常は悪いIMOですが、ここでは便利です）に依存します。）（注：私はarray<>で作業するためにあなたのテストを少し修正しました。同じテストを実行すると、上記のコードはほぼ同じですが、平均でわずかに改善されています）。