Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fastest way to move simple data types in array to specific positions

What is the fastest way to move simple data types in array of known size to specific positions?

The specific case I had was rotating a game board stored as an int[9]
[0,1,2,3,4,5,6,7,8] becomes [6,3,0,7,4,1,8,5,2]


In my use case I had a vector of these arrays, which each needed rotating.

Board Layout:

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

The fastest method I came up with was to create a public variable to assign the array entries to, and then copy the memory back.

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

I have seen a similar question here, which recommends
int[] b = new int[] {b[6], b[3], b[0], b[7], b[4], b[1], b[8], b[5], b[2]};
..though it clocks much slower (less than half the speed on a single thread)


Both are relatively fast (see a test here)

If this is not the fastest method, what is?
I suspect the algorithm will be the same in both C and C++.

like image 555
ti7 Avatar asked Nov 03 '15 06:11

ti7


People also ask

How do you move items in an array?

Use the splice() method to remove the element at the specific index from the array. Use the splice() method to insert the element at the new index in the array. The splice method changes the original array by removing or replacing existing elements, or adding new elements at a specific index.

Are arrays faster than map?

Arrays have a better performance than maps since you know which element you want to access, as much as maps have constant access, arrays have instant access if called by their index.

How do you move specified number of elements to the end of an array in JavaScript?

Run a for loop from index i = 0 till X-1. In each iteration take the element at current index and append it at the end of the array. After the iteration is complete, use the JavaScript splice() method to remove first X elements from the array to get the resultant array.


1 Answers

With this one you gain the memcpy call and the [4] to [4] assignment. You lose two assignments to the putAside variable. So it is surely a little bit faster.

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;
}
like image 171
Joël Hecht Avatar answered Nov 09 '22 23:11

Joël Hecht