• Miguel L (158/158) Sep 01 2016 Hi
• Miguel L (38/43) Sep 01 2016 Sorry Rotate4 had a bug, there was an extra for that was not
• Miguel L (72/118) Sep 01 2016 Very sorry again: Rotate4 was not correct with negative offsets.
• Johan Engelen (2/4) Sep 01 2016 And the version of LDC too please ;-)
• Miguel L (3/7) Sep 01 2016 LDC version is: ldc2-1.1.0-beta2-win64-msvc

Miguel L <mlabayru gmail.com> writes:

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

}

Miguel L <mlabayru gmail.com> writes:

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

}

Miguel L <mlabayru gmail.com> writes:

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

Johan Engelen <j j.nl> writes:

On Thursday, 1 September 2016 at 10:37:18 UTC, Miguel L wrote:
 
 Also, forgot to specify I am using LDC with -05.

And the version of LDC too please ;-)

Miguel L <mlabayru gmail.com> writes:

On Thursday, 1 September 2016 at 13:16:19 UTC, Johan Engelen 
wrote:
 On Thursday, 1 September 2016 at 10:37:18 UTC, Miguel L wrote:
 
 Also, forgot to specify I am using LDC with -05.

 And the version of LDC too please ;-)

LDC version is: ldc2-1.1.0-beta2-win64-msvc