On Thursday, 1 September 2016 at 09:53:59 UTC, Miguel L wrote:
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;
}
}
}
Very sorry again: Rotate4 was not correct with negative offsets.
This implementation works correctly:
void Rotar4(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 - -2 -
* 1,8,3,4,5,6,7,2 - a=7 b=1
* 7,8,3,4,5,6,1,2 - a=6 b=0
* 7,6,3,4,5,8,1,2 - a=5 b=1
* 5,6,3,4,7,8,3,4 - a=4 b=0
* 3,6,5,4,7,8,1,2 - a=3 b=1
* 3,4,5,6,7,8,1,2 - a=2 b=0
--------------------
1,2,3,4,5,6,7,8,9 - 2 -
* 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
*/
long a,b;
T tmp;
if(n>0)
{
a=0;
b=input.length-n;
while(a<input.length-n)
{
tmp=input[b];
input[b]=input[a];
input[a]=tmp;
++a;
++b;
if(b>=input.length)
b=input.length-n;
}
}
else
{
a=input.length-1;
long b0=-n-1;
b=b0;
while(a>=-n)
{
tmp=input[b];
input[b]=input[a];
input[a]=tmp;
--a;
--b;
if(b<0)
b=b0;
}
}
}
Also, forgot to specify I am using LDC with -05.
Updated benchmark results:
Rotate0: 0.344186s
Rotate1: 1.76369s
Rotate2: 0.169968s
Rotate3: 0.354091s
Rotate4: 0.156231s
