Menu
Search

Forums

Forum Index

Thread overview
Different array rotation algorithms benchmark
Sep 01, 2016
Miguel L
Sep 01, 2016
Miguel L
Sep 01, 2016
Miguel L
Sep 01, 2016
Johan Engelen
Sep 02, 2016
Miguel L
September 01, 2016
Gravatar of Miguel LPosted by Miguel LReply
Miguel L
Gravatar of Miguel L


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

}
September 01, 2016
Gravatar of Miguel LPosted by Miguel L
in reply to Miguel L		Reply
Miguel L
Gravatar of Miguel L
Posted in reply to Miguel L


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

}
September 01, 2016
Gravatar of Miguel LPosted by Miguel L
in reply to Miguel L		Reply
Miguel L
Gravatar of Miguel L
Posted in reply to Miguel L


Reply
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
September 01, 2016
Gravatar of Johan EngelenPosted by Johan Engelen
in reply to Miguel L		Reply
Johan Engelen
Gravatar of Johan Engelen
Posted in reply to Miguel L


Reply
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 ;-)
September 02, 2016
Gravatar of Miguel LPosted by Miguel L
in reply to Johan Engelen		Reply
Miguel L
Gravatar of Miguel L
Posted in reply to Johan Engelen


Reply
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