On Thursday, 1 September 2016 at 09:36:16 UTC, Miguel L wrote:
Hi
I recently needed a very optimized array rotation algorithm, so
I did this benchmark, hope you find it interesting. I am a bit
surprised by the poor results of std.algorithm.bringToFront:
[...]
Sorry Rotate4 had a bug, there was an extra for that was not
neccesary, this is the correct implementation:
void Rotate4(T)(T[] input, long n) pure
{
/* 1,2,3,4,5,6,7,8 - 2 -
* 7,2,3,4,5,6,1,8 - a=0 b=8-2=6
* 7,8,3,4,5,6,1,2 - a=1 b=7
* 7,8,1,4,5,6,3,2 - a=2 b=6
* 7,8,1,2,5,6,3,4 - a=3 b=7
* 7,8,1,2,3,6,5,4 - a=4 b=6
* 7,8,1,2,3,4,5,6 - a=5 b=7
--------------------
1,2,3,4,5,6,7,8,9 - 3 -
* 7,2,3,4,5,6,1,8,9 - a=0 b=9-3=6
* 7,8,3,4,5,6,1,2,9 - a=1 b=7
* 7,8,9,4,5,6,1,2,3 - a=2 b=8
* 7,8,9,1,5,6,4,2,3 - a=3 b=6
* 7,8,9,1,2,6,4,5,3 - a=4 b=7
* 7,8,9,1,2,3,4,5,6 - a=5 b=8
*/
if(n<0)
n=input.length+n;
long a=0,b=input.length-n;
T tmp;
while(a<input.length-n-1)
{
tmp=input[b];
input[b]=input[a];
input[a]=tmp;
++a;
++b;
if(b>=input.length)
{
b=input.length-n;
}
}
}
