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 recommendsint[] 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++.
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.
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.
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.
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With