Benchmark Factorial – Parámetros acumulados

Voy hacer un benckmark de 3 implementaciones de factorial:

Em primer lugar, la implementación más simple y eficiente, por siempre de los jamases, al menos para arquitecturas de Von Newman y monoprocesador:

long factorial_iterativo(long n)
{
	long i, ac = 1;
	for(i=n; i>0; i--)
		ac = ac * i;
	return ac;
}

Despues esta la recursiva lineal, típico ejemplo de recursividad. Fijaos en la linea de la llamada recursiva …

long factorial_recursivo(long n)
{
	if (n == 0)
		return 1;
	else
		return n * factorial_recursivo(n-1);
}

Y esta es la que realmente tenía curiosidad de comparar.  Es un tipo de recursividad que hace que la vuelta en lugar de ser de pila, sea de cola. Es necesario modificar la interfaz y crear una nueva función manejadora que respete la interfaz. Se trata de ir acumulando el resultado como parametro y principalmente que en la linea que se hace la llamada recursiva, solo haya una llamada recursiva.

Esta función, teoricamente implementado en Caml el compilador al pasarlo a código maquina la pasa a iterativa automaticamente. Si esto fuera tambien así en C, podríamos utilizar funciones recursivas, sin miedo a desbordar la pila y sin problemas de redimiento. Y por supuesto ganando la claridad de resolver algunos problemas de naturaleza recursiva.

long _factorial_recursivo_PA(long n, long r)
{
	if (n==0)
		return r;
	else
		return _factorial_recursivo_PA(n-1, n*r);
}

long factorial_recursivo_PA(long n)
{
	return _factorial_recursivo_PA(n, 1);
}

Los resultados son estos:

1000 iteraciones

——- n! = 160000 calculado 1000 veces——–
2.357 segs (Factorial recursivo parametros acumulados)
2.316 segs (Factorial recursivo)
0.606 segs (Factorial iterativo)
——- n! = 170000 calculado 1000 veces——–
2.714 segs (Factorial recursivo parametros acumulados)
2.522 segs (Factorial recursivo)
0.636 segs (Factorial iterativo)
——- n! = 180000 calculado 1000 veces——–
2.960 segs (Factorial recursivo parametros acumulados)
2.842 segs (Factorial recursivo)
0.662 segs (Factorial iterativo)
——- n! = 190000 calculado 1000 veces——–
3.305 segs (Factorial recursivo parametros acumulados)
3.192 segs (Factorial recursivo)
0.704 segs (Factorial iterativo)
——- n! = 200000 calculado 1000 veces——–
3.632 segs (Factorial recursivo parametros acumulados)
3.457 segs (Factorial recursivo)
0.738 segs (Factorial iterativo)
——- n! = 210000 calculado 1000 veces——–
3.902 segs (Factorial recursivo parametros acumulados)
3.764 segs (Factorial recursivo)
0.774 segs (Factorial iterativo)
——- n! = 220000 calculado 1000 veces——–
4.154 segs (Factorial recursivo parametros acumulados)
4.108 segs (Factorial recursivo)
0.814 segs (Factorial iterativo)
——- n! = 230000 calculado 1000 veces——–
4.443 segs (Factorial recursivo parametros acumulados)
4.296 segs (Factorial recursivo)
0.850 segs (Factorial iterativo)
——- n! = 240000 calculado 1000 veces——–
4.761 segs (Factorial recursivo parametros acumulados)
4.590 segs (Factorial recursivo)
0.886 segs (Factorial iterativo)
——- n! = 250000 calculado 1000 veces——–
5.027 segs (Factorial recursivo parametros acumulados)
4.945 segs (Factorial recursivo)
0.942 segs (Factorial iterativo)
——- n! = 260000 calculado 1000 veces——–
5.401 segs (Factorial recursivo parametros acumulados)
5.273 segs (Factorial recursivo)
0.999 segs (Factorial iterativo)
——- n! = 270000 calculado 1000 veces——–
5.704 segs (Factorial recursivo parametros acumulados)
5.572 segs (Factorial recursivo)
1.020 segs (Factorial iterativo)
——- n! = 280000 calculado 1000 veces——–
6.064 segs (Factorial recursivo parametros acumulados)
5.947 segs (Factorial recursivo)
1.068 segs (Factorial iterativo)
——- n! = 290000 calculado 1000 veces——–
6.356 segs (Factorial recursivo parametros acumulados)
6.307 segs (Factorial recursivo)
1.106 segs (Factorial iterativo)
——- n! = 300000 calculado 1000 veces——–
6.687 segs (Factorial recursivo parametros acumulados)
6.758 segs (Factorial recursivo)
1.127 segs (Factorial iterativo)
——- n! = 310000 calculado 1000 veces——–
6.936 segs (Factorial recursivo parametros acumulados)
6.529 segs (Factorial recursivo)
1.171 segs (Factorial iterativo)
——- n! = 320000 calculado 1000 veces——–
7.058 segs (Factorial recursivo parametros acumulados)
6.830 segs (Factorial recursivo)
1.225 segs (Factorial iterativo)

100.000 iteraciones

——- n! = 16000 calculado 100000 veces——–
10.794 segs (Factorial recursivo parametros acumulados)
10.182 segs (Factorial recursivo)
5.724 segs (Factorial iterativo)
——- n! = 17000 calculado 100000 veces——–
11.539 segs (Factorial recursivo parametros acumulados)
10.963 segs (Factorial recursivo)
6.474 segs (Factorial iterativo)
——- n! = 18000 calculado 100000 veces——–
12.264 segs (Factorial recursivo parametros acumulados)
11.586 segs (Factorial recursivo)
6.435 segs (Factorial iterativo)
——- n! = 19000 calculado 100000 veces——–
12.905 segs (Factorial recursivo parametros acumulados)
12.003 segs (Factorial recursivo)
6.779 segs (Factorial iterativo)
——- n! = 20000 calculado 100000 veces——–
13.541 segs (Factorial recursivo parametros acumulados)
12.892 segs (Factorial recursivo)
7.422 segs (Factorial iterativo)
——- n! = 21000 calculado 100000 veces——–
14.362 segs (Factorial recursivo parametros acumulados)
13.565 segs (Factorial recursivo)
7.644 segs (Factorial iterativo)
——- n! = 22000 calculado 100000 veces——–
14.749 segs (Factorial recursivo parametros acumulados)
13.852 segs (Factorial recursivo)
8.001 segs (Factorial iterativo)
——- n! = 23000 calculado 100000 veces——–
15.704 segs (Factorial recursivo parametros acumulados)
14.573 segs (Factorial recursivo)
8.478 segs (Factorial iterativo)
——- n! = 24000 calculado 100000 veces——–
16.463 segs (Factorial recursivo parametros acumulados)
15.879 segs (Factorial recursivo)
8.766 segs (Factorial iterativo)
——- n! = 25000 calculado 100000 veces——–
17.309 segs (Factorial recursivo parametros acumulados)
16.303 segs (Factorial recursivo)
9.391 segs (Factorial iterativo)
——- n! = 26000 calculado 100000 veces——–
17.598 segs (Factorial recursivo parametros acumulados)
16.846 segs (Factorial recursivo)
9.320 segs (Factorial iterativo)
——- n! = 27000 calculado 100000 veces——–
18.288 segs (Factorial recursivo parametros acumulados)
17.226 segs (Factorial recursivo)
9.655 segs (Factorial iterativo)
——- n! = 28000 calculado 100000 veces——–
19.001 segs (Factorial recursivo parametros acumulados)
17.973 segs (Factorial recursivo)
9.991 segs (Factorial iterativo)
——- n! = 29000 calculado 100000 veces——–
20.112 segs (Factorial recursivo parametros acumulados)
18.636 segs (Factorial recursivo)
10.480 segs (Factorial iterativo)
——- n! = 30000 calculado 100000 veces——–
20.904 segs (Factorial recursivo parametros acumulados)
18.919 segs (Factorial recursivo)
10.729 segs (Factorial iterativo)
——- n! = 31000 calculado 100000 veces——–
20.824 segs (Factorial recursivo parametros acumulados)
19.515 segs (Factorial recursivo)
11.132 segs (Factorial iterativo)
——- n! = 32000 calculado 100000 veces——–
21.585 segs (Factorial recursivo parametros acumulados)
20.344 segs (Factorial recursivo)
11.681 segs (Factorial iterativo)

Conclusión: bastante decepcionante, yo esperaba que el compilador de C, me dejara la función PA con una eficiencia cercana a la iterativa, pero soñar es gratis. Seguire investigando con los parametros -O1 , -O2, y -O3.

Tambien me falta probar el recursivo PA, con el parametro pasado por referencia en la variable r.

Conclusión2: iterativo 4ever …

Os dejo el código fuente, compilarlo sin optimización, ya que la variable calculado no se usa, y una optimización de nivel 1 se saltaría el propio bench.

#include <stdio.h>
#include <time.h>
#include <sys/time.h>

suseconds_t microtime(struct timeval * momento)
{
	struct timezone * tiempoZona=NULL;
	return gettimeofday(momento , tiempoZona)==0 ? 0 : -1;
}

double diferenciaMicroTime(struct timeval * time1 , struct timeval * time2)
{
	double diferenciaSegundos = difftime(time1->tv_sec , time2->tv_sec);
	double diferenciaMicroSegundos = (double)(time1->tv_usec-time2->tv_usec);
	return diferenciaSegundos*1000000+diferenciaMicroSegundos;
}

void benchBegin(struct timeval * inicio)
{
	microtime(inicio);
}

double benchEnd(struct timeval * inicio)
{
	struct timeval fin;
	microtime(&fin);
	double diffT = diferenciaMicroTime(&fin, inicio);
	return diffT/1000000;
}

long _factorial_recursivo_PA(long n, long r)
{
	if (n==0)
		return r;
	else
		return _factorial_recursivo_PA(n-1, n*r);
}

long factorial_recursivo_PA(long n)
{
	return _factorial_recursivo_PA(n, 1);
}

long factorial_recursivo(long n)
{
	if (n == 0)
		return 1;
	else
		return n * factorial_recursivo(n-1);
}

long factorial_iterativo(long n)
{
	long i, ac = 1;
	for(i=n; i>0; i--)
		ac = ac * i;
	return ac;
}

int main()
{
	long i,j;
	double res;
	struct timeval inicioT;
	long its = 100000;
	long desde = 16000;
	long hasta = 32000;
	long paso =  1000;

	for(j=desde;j<=hasta;j+=paso)
	{
		printf("------- n! = %ld calculado %ld veces--------\n", j, its);

		benchBegin(&inicioT);
		for(i=0; i<its; i++)
			res = factorial_recursivo_PA(j);
		res = benchEnd(&inicioT);
		printf("%.3f segs (Factorial recursivo parametros acumulados)\n", res);

		benchBegin(&inicioT);
		for(i=0; i<its; i++)
			res = factorial_recursivo(j);
		res = benchEnd(&inicioT);
		printf("%.3f segs (Factorial recursivo)\n", res);

		benchBegin(&inicioT);
		for(i=0; i<its; i++)
			res = factorial_iterativo(j);
		res = benchEnd(&inicioT);
		printf("%.3f segs (Factorial iterativo)\n", res);
	}

	return 0;
}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: