Archivo

Entradas Etiquetadas ‘funciones’

Fibonacci recursivo en C [ intentemos no repetir operaciones! ]

Lunes, 21 de Junio de 2010 admin Sin comentarios

fibo
Es un ejercicio muy típico cuando se está aprendiendo con funciones recursivas es la sucesión de Fibonacci, aquella en la que F(n)=F(n-1)+F(n-2).
Aunque esta técnica podemos (y deberíamos) utilizarla para una gran cantidad de algoritmos. A veces es necesario sacrificar un poco la memoria del sistema (sin pasarnos) para agilizar y hacer más rápido el programa. Debemos adoptar una solución que beneficie al usuario, no es plan de dejarlo sin memoria, pero tampoco es plan de que la solución se eternice.

Una primera implementación puede ser la siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int fibonacci_simple(int n)
{
  /* La función normal, recursiva */
  if (n>2)
    return fibonacci_simple(n-1) + fibonacci_simple(n-2);
  /* Este es el caso más común,  */
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)       
    return 1;
  else if (n==0)
    return 0;
  else
    return -1;          /* Error */
}

Si creamos un programa de ejemplo como este:

1
2
3
4
5
6
7
8
9
10
int main(int argc, char *argv[])
{
    unsigned int numero;

    /* Generamos Fibonaccis */
    for (numero=0; numero<48; numero++)
      printf("%u\n", fibonacci_simple(numero));

    return 0;
}

Podemos observar que para generar la secuencia de 48 números (he escogido este valor, porque a partir de ahí no tenemos suficiente de 32bits para almacenar el valor obtenido), tardamos varios minutos, en concreto, en mi equipo (Pentium M 1.73MHz), echó algo más de 10 minutos. ¡ 10 minutos ! Es un buen rato para lo que ha hecho.
Si lo estudiamos detenidamente (en negrita pongo las veces que llamamos a fibonacci_simple() sin necesidad):

  • fibonacci_simple(0)
  • fibonacci_simple(1)
  • fibonacci_simple(2)
  • fibonacci_simple(3) (que llama a fibonacci_simple(2) y fibonacci_simple(1) )
  • fibonacci_simple(4) (que llama a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) ) y a fibonacci_simple(2) )
  • fibonacci_simple(5) (que llama a fibonacci_simple(4) ( que llama a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) ) y a fibonacci_simple(2) ) y a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) )

Yo creo que con esto nos hacemos una idea de lo que quiero decir, se repiten demasiadas operaciones, seguro que hay alguna forma de solucionar esto.

Propongo lo siguiente:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int fibonacci_buffer(int n)
{
  static int *fbuffer=NULL; /* Buffer */
  static int bufsize=0; /* Tamaño de buffer */
  int n3;           /* n-2 */
  int i;            /* Recorre buffers */

  if (n>2)
    {
      n3=n-2;
      if (fbuffer==NULL)
    {
      fbuffer = (int*) malloc((n3 * sizeof(int)));
      for (i=0; i<n3; i++)
        fbuffer[i]=0;   /* Ponemos buffer a 0 */

/*    printf("Creo buffer: %d -- %d\n", n3*sizeof(int), errno); */

      bufsize=n3;
    }
      else if (bufsize<n3)
    {
      fbuffer = (int*) realloc(fbuffer, n3 * sizeof(int));
/*    printf("Amplio buffer\n"); */

      for (i=bufsize; i<n3; i++) /* Ponemos a 0 la memoria nueva */
        fbuffer[i]=0;

      bufsize=n3;
    }
/*       printf("-%d--%d\n", n, fbuffer[n3-1]); */
      if (fbuffer[n3-1]!=0) /* Si se encuentra el fibonacci del número que buscamos  */
    return fbuffer[n3-1];   /* en memoria, lo devolvemos directamente */
      else
    {
      /* Si el fibonacci no se encuentra, vamos a generarlo */
      fbuffer[n3-1] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2);
      //      printf("He generado con éxito fbuffer[%d]\n", n3-1);
      return fbuffer[n3-1];
    }

/*       return fibonacci_simple(n-1) + fibonacci_simple(n-2); */
    }
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)
    return 1;
  else if (n==0)
    return 0;
  else if (n==-1)       /* Un caso nuevo n==-1 */
    free(fbuffer);      /* Liberamos memoria */

  return -1;            /* Error */
}

Es algo más enrevesado, ya que usamos variables estáticas (podríamos hacer variables globales, con cuidado), así evitamos que la información que vamos almacenando se pierda entre ejecuciones de la función; por otra parte, utilizamos malloc() y realloc() para reservar sólo la memoria que vamos necesitando.
Por otra parte para reducir la memoria utilizada, hacemos que fibonacci(3) se almacene en la posición 0 del buffer (porque el de 2, 1 y 0, ya nos los sabemos); por otra parte… la variable n3 vale n-2; esto es simplemente porque si tenemos que calcular fibonacci(5), y sabemos que fibonacci(3) está almacenado en fbuffer[0], fibonacci(4) estará en fbuffer[1] y fibonacci(5) estará en fbuffer[2]; es decir tenemos que almacenar 3 valores de fibonacci (5-2=3).
Por otra parte, siempre que reservamos memoria ponemos los nuevos espacios a 0, ya que comprobamos que no hay ningún valor almacenado si éstos son 0.

Con el almacén de los números conseguimos que el esquema anterior se quede en:

  • fibonacci_buffer(0)
  • fibonacci_buffer(1)
  • fibonacci_buffer(2)
  • fibonacci_buffer(3) (que llama a fibonacci_buffer(2) y fibonacci_buffer(1)
  • fibonacci_buffer(4) (que llama a fibonacci_buffer(3) ( que saca el valor del buffer ) y a fibonacci_simple(2) )
  • fibonacci_buffer(5) (que llama a fibonacci_buffer(4) (que saca el valor del buffer) y a fibonacci_buffer(3) (que saca el valor del buffer)

Con este algoritmo consigo generar todos los números en 4ms.

¿Será posible simplificarlo un poco más?
Sólo hay que ver cómo se hace la generación de valores de forma recursiva. Si lo pensamos bien, cuando llamamos a fibonacci_buffer(5) la primera vez y lo queremos almacenar en fbuffer[2] llamaremos a fibonacci_buffer(4) (que se almacenará en fbuffer[1], y éste llamará a fibonacci_buffer(3) (que se almacenará en fbuffer[0]); es decir, lo primero que se generará será fbuffer[0], luego fbuffer[1] y por último fbuffer[2]… ¡ vamos por orden ! Sabiendo esto, nos podremos ahorrar el código de poner a 0 los elementos del buffer sabiendo cuál es el último elemento generado.

Para los incrédulos, podemos eliminar el comentario de la línea:

1
//    printf("He generado con éxito fbuffer[%d]\n", n3-1);

y ejecutar… veremos con qué orden se van generando los números.

Bien, intentemos eliminar las puestas a 0 de los elementos del buffer.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int fibonacci_buffer2(int n)
{
  static int *fbuffer=NULL; /* Buffer */
  static int bufsize=0;         /* Tamaño de buffer */
  static int bpos=0;            /* Recorre buffers */
  int n3;           /* n-2 */

  if (n>2)
    {
      n3=n-2;
      if (fbuffer==NULL)
    {
      fbuffer = (int*) malloc((n3 * sizeof(int)));
      bufsize=n3;   /* Mantenemos bufsize por si redimensionamos el buffer */
    }
      else if (bufsize<n3)
    {
      fbuffer = (int*) realloc(fbuffer, n3 * sizeof(int));
      bufsize=n3;      
    }

      /* Utilizamos bpos para saber cuál es el último elemento del buffer */
      /* que hemos rellenado. */
      if (bpos>=n3)         /* Si se encuentra el fibonacci del número que buscamos  */
    return fbuffer[n3-1];   /* en memoria, lo devolvemos directamente */
      else
    {
      /* Si el fibonacci no se encuentra, vamos a generarlo */
      fbuffer[n3-1] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2);
      bpos=n3;
      return fbuffer[n3-1];
    }

/*       return fibonacci_simple(n-1) + fibonacci_simple(n-2); */
    }
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)
    return 1;
  else if (n==0)
    return 0;
  else if (n==-1)       /* Un caso nuevo n==-1 */
    free(fbuffer);      /* Liberamos memoria */

  return -1;            /* Error */
}

Con este algoritmo, consigo generar la secuencia en 2ms. Bastante más rápido que con el primer algoritmo, parece que la puesta a 0 del buffer llevaba su tiempo.

Para concluir, quiero proponer otra solución basada en arrays, supongo que muchos estaréis más familiarizados con estos:

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
31
32
33
int fibonacci_buffer3(int n)
{
  static int fbuffer[MAX_FIB];
  static int bufsize=0;         /* Tamaño de buffer */
  int n3;           /* n-3 */

  if (n>2)
    {
      n3=n-3;

      if (bufsize>n3)           /* Si se encuentra el fibonacci del número que buscaos  */
    return fbuffer[n3]; /* en memoria, lo devolvemos directamente */
      else
    {
      /* Si el fibonacci no se encuentra, vamos a generarlo */
      fbuffer[n3] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2); /* y lo guardamos */
      bufsize=n3+1;
      /* Al ser fibonacci recursivo, y asignar el tamaño después de la generación */
      /* el buffer se rellenará por orden, es decir, el primero que se rellenará */
      /* será el [0], luego el [1], luego el [2]... */
      return fbuffer[n3];
    }

    }
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)
    return 1;
  else if (n==0)
    return 0;

  return -1;            /* Error, seguramente me hayan pasado un n negativo*/
}

Esta solución es muy parecida a las anteriores, aunque nos quitamos del medio la reserva de memoria, reducimos las líneas de código, ya que no vamos a alojar tantos valores diferentes… para esta secuencia serían unos 48 * 4 (sizeof(int)) = 192 bytes, y bufsize la utilizamos para ver cuál es el último elemento del buffer con información válida (como vimos antes, se rellenarán por orden, así que sólo tendríamos que llevar la cuenta). Las variables estáticas, como dije, podemos hacerlas globales (y quitarles el static, aunque queda más elegante como static).

Con esta solución tardo unos 5ms de media en generar la secuencia de números.

Foto: Eustaquio Santimano (Flickr)

Categories: C/C++ Tags: , , , , , , , , , , , , , , , ,

Documentando el código con Doxygen

Domingo, 11 de Abril de 2010 admin Sin comentarios

librosssTanto o más importante que tirarse horas programando una aplicación es su documentación, y debemos hacerlo aunque nosotros seamos los únicos que intervengamos en su desarrollo.
Algo que siempre digo en mis clases de programación es que a poco que compliquemos el código si no comentamos lo que estamos haciendo, en séis meses cuando toque hacer una siguiente versión no tendremos ni idea de lo que hace; y esto conlleva pasar más tiempo para hacer las modificaciones que necesitamos, que al final se traducen en dinero.

Doxygen es una de esas herramientas que nos hacen la vida más fácil, ya que analizará los comentarios de nuestros archivos fuente y generará un documento (html, latex…) con todas las clases, funciones, métodos, variables globales, definiciones, etc que contenga nuestro código; se generará un documento muy valioso para hacer futuras modificaciones.

Este programa tiene multitud de opciones y palabras clave que podemos ver en su documentación. Pero yo comentaré lo justo para empezar, ya que no queremos perder mucho tiempo y queremos empezar a documentar código. Hay muchos lenguajes soportados, pero tanto para C, C++, PHP y algunos otros podemos hacer comentarios con /* …. */ o //, pues bien, Doxygen leerá los comentarios que comiencen por /** (barra, asterisco, asterisco) o /// (tres barras). Lo que situemos como comentario será la descripción de la función, clase, método, o lo que sea que pongamos detrás; así como la descripción del propio fichero que pondremos como primer comentario al principio de nuestro código.

Para Doxygen existen algunas palabras clave como por ejemplo:

  1. @file : Especifica el propio fichero que editamos, útil para la descripción del fichero.
  2. @brief : Breve descripcion de la función, método, clase, variable… que estamos describiendo.
  3. @date : Fecha
  4. @author : Autor
  5. @version : Versión
  6. @param : Parámetro (en caso de funciones y métodos)
  7. @return : Valor de la salida (en caso de funciones y métodos)

Propongo un pequeño código en PHP que no hace nada, pero que se documentará bien:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
<?php
 /**
******************************************************
*  @file test.php
*  @brief Breve descripción
* Pequeña documentación del archivo
* @author Gaspar
* @version 2.0
* @date Marzo 2010
*
*
*******************************************************/

/**
* Variable global
*/
$var_global='VALOR';

/** Ahora me da por definir cosas */
define('defino_algo', 'DEFINICION');
/*
* Description: Esta función algo hará
*
* @param $cadena
* Esto es una cadena graciosa
* @param $vector
* Esto es un vestor gracioso
*
* @return string
* Cadena resultante

*/
function estoyprobando($cadena, $vector)
{
}

/**
******************************************************
* @brief Clase para hacer pruebas
*
******************************************************/
class TestingPHP
{
/**
*************************************************************
* @brief Constructor
*************************************************************/
function __construct()
{
}

/**
*************************************************************
* @brief Metodo 1
* @param $par Primer parametro de entrada
*
* @return Genero una salida
*************************************************************/
function metodo1($par)
{

}
};
?>;

Para documentarlo con Doxygen, tendremos que hacer lo siguiente:

$ doxygen -g testing.cfg

Generaremos un archivo de configuración de la documentación de ejemplo, sólo tendremos que cambiar unas cuantas cosas para generar la documentación como nosotros queramos:

  • PROJECT_NAME=Miproyecto (una sóla palabra)
  • PROJECT_NUMBER=0.2 (la versión)
  • OUTPUT_DIRECTORY=doc (Directorio donde irá la documentación)
  • OUTPUT_LANGUAGE=Spanish (Queremos documentación en español
  • EXTRACT_ALL= YES (Incluso lo que no esté documentado aparecerá en la documentación
  • EXTRACT_PRIVATE=YES (Extraeremos los métodos públicos)
  • EXTRACT_STATIC= YES (Extraeremos los métodos estáticos)
  • RECURSIVE= YES (Extracción recursiva, incluiremos los subdirectorios)
  • CREATE_SUBDIRS=YES (Creará subdirectorios a la hora de documentar, es importante si tenemos muchas líneas de código fuente (muchas funciones, clases, archivos….) ya que de otra forma situará todos los archivos de la salida en el mismo directorio, y pueden ser muchos.)
  • FILE_PATTERNS = *.php3 *.php *.c *.cpp (Todas las extensiones de nuestros archivos fuente)
  • PDF_HYPERLINKS= YES (Crearemos una salida LaTeX con enlaces que se exportarán a PDF)
  • HAVE_DOT=YES (Crearemos mejores gráficos de clases)

Tras ello hacemos:

$ doxygen testing.cfg

Tendremos en el directorio doc toda la documentación de nuestra aplicación.

Foto: br1dotcom (Flickr)

Categories: General Tags: , , , , , , , , , , , , , ,

Funciones con nombres raros, y cortos (PHP, Javascript ,C)

Viernes, 12 de Marzo de 2010 admin Sin comentarios

El objetivo de la programación, además de escribir poco (ya sabemos que todos los que programamos no queremos dejarnos las manos escribiendo), es hacer nuestro código mantenible, y para eso es necesario que nuestras funciones y métodos tengan nombres descriptivos.
Es decir, podemos definir 20 funciones: a(), b(), c(),… y mientras hacemos el programa tener un mapa mental de todas ellas, y utilizarlas, pero dentro de 6 meses, cuando vayamos a hacer la versión 2.0 de nuestro programa, ¿nos acordaremos de para qué valía cada función? Seguramente no; pero siempre que hacemos un for, lo más normal es escribir: “for (i=0;….”, “for (j=0;……)”, etc, eso sí que sale automático :)

Podemos, por ejemplo, tener nombres descriptivos, pero tal vez sean demasiado largos y muchos de ellos empezarán por las mismas letras, lo cual podemos considerarlo improductivo.

Si habéis curioseado prototype o JQuery, veréis cómo hay una llamada que se repite: $() y ella sola, con lo corta que es, hace maravillas para obtener objetos en Javascript. Los que hayan curioseado gettext recordarán la función _(), que sirve para traducir un mensaje. Estas funciones tienen en común que no vamos a parar de llamarlas en nuestros programas, sabemos lo que hacen y necesitamos una forma corta de llamarlas, ya que si desde nuestro programa llamamos a la función gettext() unas 2000 veces, estaríamos escribiendo 12000 caracteres de más, y en Javascript, si por ejemplo queremos llamar a document.getElementById(), con $() (no es lo único que hace) unas 60 veces, estaremos escribiendo unas 1320letras de más (y en Javascript eso se traduce en más transferencia por nuestra parte).

Pero cuando vamos a hacer una aplicación, todo se utiliza más o menos a un ritmo similar, aunque encontraremos tal vez funciones de formateo que llamemos constantemente, y esas funciones podrán tener un nombre raro que puede ser un símbolo. Pero con lo caprichosos que son los lenguajes de programación, ¿qué símbolos podemos utilizar? Deben ser caracteres con los que podamos empezar una función.
Aquí van algunos ejemplos para funciones PHP:

  • €();
  • ¡();
  • ç();
  • º();
  • ½();
  • _(); Pertenece a gettext
  • ł();
  • ¶();
  • ŧ();
  • ←();

C sólo permite el uso de _()

En Javascript, tenemos por ejemplo los siguientes:

  • $() Ojo con jquery y prototype
  • _()
  • º()
  • ª()
  • ß()
  • ð()
  • ŋ()
  • ħ()
  • ł()

Hay algunos más, pero no es plan de abusar, y no quiere decir que tenemos que usarlos, sólo que tenemos esa posibilidad; también muchos caracteres dependen de la codificación que utilicemos, por lo tanto pueden darnos ciertos problemas en el futuro (sobre todo en Javascript).

Categories: C/C++, General, Javascript, PHP Tags: , , , , , , , ,

Visita otras webs de la red

Easy AdSense by Unreal