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:
These are the different algorithms:
void Rotate0(T)(T[] input, int n) pure
{
if(n>0)input=input[($-n)..$]~input[0..($-n)];
if(n<0)input=input[(-n)..$]~input[0..(-n)];
}
void Rotate(T)(T[] input, int n) pure
{
if(n>0)
std.algorithm.bringToFront(input[0..($-n)],input[($-n)..$]);
else if(n<0)
std.algorithm.bringToFront(input[0..(-n)],input[(-n)..$]);
}
void reverse(T)(T[] a, long sz) pure {
long i, j;
for (i = 0, j = sz; i < j; ++i, --j) {
T tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
void Rotate2(T)(T[] array, long amt) pure {
/*
the algorithm from Jon Bentley's book, "Programming Pearls 2nd
Edition"
O(n) time and no extra memory usage (since array was specified),
*/
if (amt < 0)
amt = array.length + amt;
reverse(array, array.length-amt-1);
reverse(array[array.length-amt..$], amt-1);
reverse(array, array.length-1);
}
void Rotate3(T)(T[] input, long n) pure
{
if(n<0)
n=input.length+n;
auto tmp=input[($-n)..$].dup;
for(auto j=input.length-1;j>=n;--j)
input[j]=input[j-n];
input[0..n]=tmp;
}
void Rotate4(T)(T[] input, long n) pure
//No extra memory, just swapping of elements
{
/* 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 - 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
*/
if(n<0)
n=input.length+n;
long a=0,b=input.length-n;
T tmp;
while(a<input.length-n-1)
for(auto k=0;k<input.length-n;k++)
{
tmp=input[b];
input[b]=input[a];
input[a]=tmp;
++a;
++b;
if(b>=input.length)
{
b=input.length-n;
}
}
}
This is the times I got for 4000000 iterations of each rotating
an array of 29 elements 2 positions(2000000 iterations to the
left, and 2000000 iterations to the right).
Rotate0: 0.300493s
Rotate1: 1.60528s
Rotate2: 0.145162s
Rotate3: 0.337595s
Rotate4: 0.0853269s
This is the test/benchmark function code, sorry for the long
asserts.
void RotateBenchmark()
{
int[]
a=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30];
Rotate0(a,2);
assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
Rotate0(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
Rotate1(a,2);
assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
Rotate1(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
Rotate2(a,2);
assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
Rotate2(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
Rotate3(a,2);
assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
Rotate3(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
Rotate4(a,2);
assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
Rotate4(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
auto init1 = TickDuration.currSystemTick();
for(auto i=0;i<2000000;++i)
Rotate0(a,2);
for(auto i=0;i<2000000;++i)
Rotate0(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
writeln("Rotate0: ",(TickDuration.currSystemTick() -
init1).to!("seconds",float),"s");
init1 = TickDuration.currSystemTick();
for(auto i=0;i<2000000;++i)
Rotate1(a,2);
for(auto i=0;i<2000000;++i)
Rotate1(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
writeln("Rotate1: ",(TickDuration.currSystemTick() -
init1).to!("seconds",float),"s");
init1 = TickDuration.currSystemTick();
for(auto i=0;i<2000000;++i)
Rotate2(a,2);
for(auto i=0;i<2000000;++i)
Rotate2(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
writeln("Rotate2: ",(TickDuration.currSystemTick() -
init1).to!("seconds",float),"s");
init1 = TickDuration.currSystemTick();
for(auto i=0;i<2000000;++i)
Rotate3(a,2);
for(auto i=0;i<2000000;++i)
Rotate3(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
writeln("Rotate3: ",(TickDuration.currSystemTick() -
init1).to!("seconds",float),"s");
init1 = TickDuration.currSystemTick();
for(auto i=0;i<2000000;++i)
Rotate4(a,2);
for(auto i=0;i<2000000;++i)
Rotate4(a,-2);
assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
writeln("Rotate4: ",(TickDuration.currSystemTick() -
init1).to!("seconds",float),"s");
}
