Dizideki basit veri türlerini belirli konumlara taşımak için en hızlı yol

Question

Basit veri türlerini bilinen boyuttaki dizide belirli konumlara taşımanın en hızlı yolu nedir?

bir int olarak depolanan bir oyun tahtası döner vardı özel durum [9]
[0,1,2,3,4,5,6,7,8] Her döner gereken bu dizilerin bir vektör, vardı kullanımım durumda [6,3,0,7,4,1,8,5,2]

---

olur.

Kurulu Düzen:

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 

Ben ile geldi en hızlı yöntemi dizi girdileri atamak ve sonra geri belleği kopyalamak için bir ortak değişken yaratmaktı. o

---

Hem nispeten olan (tek iş parçacığı üzerinde yarısından daha az hız) çok daha yavaş saatler ..though

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)); 
} 

Ben
int[] b = new int[] {b[6], b[3], b[0], b[7], b[4], b[1], b[8], b[5], b[2]};
önerir benzer bir soru here gördük Bu hızlı yöntem değilse hızlı (see a test here)

, nedir?
Algoritmanın hem C hem de C++ 'da aynı olacağından şüpheleniyorum. Eğer memcpy çağrıyı ve [4] [4] atama kazanç bu biriyle

Answer 1

. putAside değişkenine iki ödevi kaybedersiniz. Yani kesinlikle biraz daha hızlı.

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

en hızlı şekilde çok sıkı bir döngüde işlemci önbellek kullanımı muhtemelen:

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]; 
} 

Not: board[9]board[3][3] eşdeğerdir ve bitişik 3 ints 3 dizileri olarak 9 int'leri görmektedir bellek, böylece isterseniz:

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]; 
} 

o in ve out size daha sonra, aynı olabileceği gerekli olmalı Eğer herhangi bir dönüşümü uygulamak için daha esnek bir şekilde istiyorsanız

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

, aşağıdaki gibi bir şey de oldukça hızlı olacaktır:

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}; 
} 

İşte

Ben board tanımladığınız:

aşağıdaki kullanmalıdır

typedef array<int, 9> board; 

Ve evet, örtük dönüştürme işlecine dayanır (normalde kötü IMO'dur, ancak burada yararlıdır).) (NOT: Testinizi, array<> ile çalışmak için biraz uyarladım ve aynı testi yürütmek, yukarıdaki kodun, @Joel'den el ile taşınan çözümden biraz daha iyi değilse, yaklaşık olarak aynı olduğunu gösterir)