Archivo

Entradas Etiquetadas ‘ejemplos’

Preincremento y postincremento (x++ != ++x)

Jueves, 27 de Enero de 2011 Gaspar Fernández 2 comentarios

Hace unos días un alumno de clases particulares me preguntó la diferencia entre estos dos; me pareció una pregunta interesante ya que los únicos usos que había visto eran como única sentencia:

a++;
++a;

En este uso no hay diferencia, puesto que hagamos las cosas en el orden que las hagamos el resultado será igual; aunque en este ejemplo tampoco se tiene clara la idea del orden de las operaciones. Pero veamos otro ejemplo:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(int argc, char *argv[])
{
  int a=10;
  int b;

  b=a++;
  printf("a=%d\nb=%d\n", a, b);
}

Vemos que estamos realizando un postincremento de a, o lo que es lo mismo, incrementamos la variable a después de las demás operaciones (asignar a b el valor de a).

Por lo tanto, si a vale 10, b tomará el valor 10 y tras eso a incrementará 1 pasando a valer 11.
Al ver la salida podemos observar:

$ ./prepost
a=11
b=10

En cambio podemos crear este programa también (igual que el anterior cambiando a++ por ++a),

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(int argc, char *argv[])
{
  int a=10;
  int b;

  b=++a;
  printf("a=%d\nb=%d\n", a, b);
}

Cuya salida es:

$ ./prepost2
a=11
b=11

En este caso, preincrementamos a. Antes de cualquier operación incrementamos la variable. Por tanto, si a vale 10, incrementamos esa variable pasando a valer 11 y luego asignamos ese valor a b.

La gran ventaja de esto es que con la experiencia suficiente nos ayuda a reducir el código que escribimos y optimizar la velocidad de nuestros programas. Además, a la hora de crear nuestros programas podremos ahorrar mucho código, sobre todo a la hora de lidiar con punteros de cadenas o imágenes donde, en ocasiones, podemos realizar tareas de forma más fácil.

Dejo algunos ejemplos más, aunque sencillos del uso de estos operadores:

Mareando un poco la perdiz

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(int argc, char *argv[])
{
  int a=10;
  int b=5;

  b=a++ + ++b;
  printf("a=%d\nb=%d\n", a, b);
}

Que da como salida:

$ ./prepost3
a=11
b=16

En este caso… cogemos a (que vale 10), luego incrementamos b (que valía 5 y pasa a valer 6), sumamos los dos valores (que da en total 16) y luego incrementamos a (que pasa a valer 11).

En un do-while

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

int main(int argc, char *argv[])
{
  int a;

  a=0;
  do
    printf("Bucle a=%d\n", a);
  while (++a<5);
}

Cuya salida es:

$ ./preposw
Bucle a=0
Bucle a=1
Bucle a=2
Bucle a=3
Bucle a=4

En este caso, al finalizar cada iteración, incrementamos a y luego miramos si es menor que 5; por lo que, en la última vuelta del bucle, si a vale 4, incrementaremos su valor (pasando a ser 5) y luego veremos que ya no es menor que 5 por lo que saldremos del bucle.

En contraposición podemos hacer:

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

int main(int argc, char *argv[])
{
  int a;

  a=0;
  do
    printf("Bucle a=%d\n", a);
  while (a++<5);
}

Cuya salida es:

$ ./preposw
Bucle a=0
Bucle a=1
Bucle a=2
Bucle a=3
Bucle a=4
Bucle a=5

En este caso, al verificar que a < 5 antes de incrementar a. Cuando a vale 4, haremos la comparación, cuando todavía es menor que 5 e incrementaremos. Daremos otra vuelta más con a valiendo 5, donde, en la siguiente comparación (a<5) ahora sí que saldrá del bucle, aunque si verificáramos el valor de a tras salir del bucle sería 6.

Contar caracteres a mano

Un ejemplo tonto más, para contar las letras de una cadena:

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int main(int argc, char *argv[])
{
  int i=0;
  char *str="HOLA";

  // Con esto vale
  while (str[++i]!='\0');

  printf("Longitud: %d\n", i);
  }

Salida:

$ ./prepos
Longitud: 4

En este caso, dentro del while, primero incrementamos i, luego comparamos str[i] con ‘\0′ y si efectivamente tiene ese valor saldremos del bucle. No se crea un bucle infinito porque el incremento se produce (aunque sea en la misma sentencia de la comparación).
Hay que tener cuidado con este ejemplo, ya que si la cadena está vacía (es decir, que el primer carácter que encontremos sea \0) tal vez este método produzca resultados inesperados, ya que nunca llegamos a comparar el carácter 0 (incrementamos antes de comparar ese carácter). Una posible solución es inicializar i a -1.

Nota: Todo lo comentado aquí vale tanto con preincremento/postincremento como con predecremento/postdecremento (–a, a–), ya que son operaciones muy similares.

Categories: C/C++, Cosas que damos por hechas Tags: , , , , , , ,

Fibonacci recursivo en C [ intentemos no repetir operaciones! ]

Lunes, 21 de Junio de 2010 Gaspar Fernández 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: , , , , , , , , , , , , , , , ,

Visita otras webs de la red