Archivo

Entradas Etiquetadas ‘cache’

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: , , , , , , , , , , , , , , , ,

Caché+Compresión+Palabras clave en ficheros CSS y JS

Viernes, 22 de Enero de 2010 admin Sin comentarios

Cuando nos aventuramos en un proyecto web con más o menos visitas, queremos que sea lo más rápido para el usuario y para ello enviar la menor cantidad de información (si nuestro hosting nos cobra además por transferencia también ganamos por esto), para ello podemos comprimir la información (y ya lo soportan la mayoría de los navegadores).
Aunque tenemos que tener en cuenta que si comprimimos información (la compresión es un proceso algo pesado), estamos gastando recursos de CPU que, si lo pensamos, estar comprimiendo la misma información a cada petición que nos hagan de un fichero Javascript es tontería; por tanto, una vez que lo comprimamos, lo almacenamos en disco, que este tipo de información no ocupa tanto.
Por otra parte, si eres de los que realizan una plantilla más o menos completa y la publica con pequeñas modificaciones en diferentes webs, o incluso estar preparados para que un cliente nos cambie la gama de colores y no echarnos las manos a la cabeza; o por ejemplo cuando tenemos que tener en cuenta el mismo color tanto en el código CSS como en el Javascript, podemos escribir ciertas palabras clave dentro del fichero CSS y Javascript que nuestro script PHP traducirá antes de enviar la información al usuario final.

Para ello, y para poco más es el siguiente script:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
<?
/* tcjs.php versión 0.05 Copyright 2010 Gaspar Fernández*/

/* Inclusión de keywords y compresión de archivos JS y CSS */

/* El código fuente se entrega tal cual, sin garantía para ser */
/* estudiado y utilizado en cualquier entorno libre y no libre. */
/* Eso si, agradecería que me comunicárais si lo usáis en un proyecto */
/* mandando un mail a blakeyed@totaki.com; sólo para saber que esto  */
/* se está usando en algún lugar del mundo :) */

/* Configuración del script */

/* $basepath normalmente es la ruta donde se encuentra el script. Es la ruta base
absoluta a partir de la cual se encuentran todos los archivos. Esta ruta será padre
de la ruta donde se encuentre el fichero CSS o JS que llamaremos. */
$basepath = '/home/gaspy/proyectos/www/poesiabinaria/tests/';
/* $httppath es la URL base de nuestra web o sección, normalmente será la dirección con la que
abriremos el directorio web correspondiente a $basepath. */
$httppath = 'http://localhost/poesiabinaria/tests/';
/* $cachedir es el directorio donde se encontrarán los cachés de los ficheros JS y CSS */
$cachedir = $basepath.'var/gzcache/';
/* $excluded_files es un archivo de texto donde se encuentran (uno por línea) todos los ficheros
que no pasarán por el procesador. Sólo serán comprimidos y guardados en caché. */
$excluded_files = $basepath.'var/excluded';
/* $definiciones_file es un archivo php que incluiremos cargando las definiciones necesarias para
completar el contenido de los CSS y JS. Puede haber un fichero de definiciones tanto raiz como
en el directorio donde se encuentra el CSS o JS a procesar.*/
$definiciones_file = 'lib/tcjc_defs.php';
/* FIN de Configuración del script */

function gf_getgz_cachefile($file)
{
/* Obtenemos un nombre de fichero único para los archivos de cache */
global $cachedir;
$getstr = $file.sizeof($file).filemtime($file);
$hash = base_convert(md5($getstr),16,36); /* Hash en base36 */

return $cachedir.$hash;
}

function add_ending_slash($path)
{
/* Añade una barra al final de la ruta del directorio */
$sep = (PHP_OS == 'Windows')? '\':'/';
$path .= (substr($path,-1) == $sep)? '':$sep;
return $path;
}

function genera_y_cachea($file, $cachefile)
{
/* Genera el cache, sustituyendo las definiciones */
global $basepath, $definiciones_file, $httppath;

$definiciones = array ('%%http_path%%' => $httppath);
/* Si tenemos un archivo auxiliar para incluir definiciones */
if (file_exists($basepath.$definiciones_file))
require_once($basepath.$definiciones_file);

$local_defs = add_ending_slash(dirname($file)).$definiciones_file;

if (file_exists($local_defs))
require_once($local_defs);

$triggers = array_keys($definiciones);
$reemplaz = array_values($definiciones);
$contenidos = file_get_contents($file);
$contenidos = str_replace($triggers, $reemplaz, $contenidos);
file_put_contents($cachefile, $contenidos);
$gz = gzopen($cachefile.".gz","wb5");
gzwrite($gz, $contenidos);
gzclose($gz);
}

function comprime($file, $cachefile)
{
/* Símplemente comprime el archivo */
$contenidos = file_get_contents($file);

file_put_contents($cachefile, $contenidos); /* Hacemos un backup también */
$gz = fopen($cachefile.".gz","wb");
fwrite($gz, gzencode($contenidos));
fclose($gz);
}

function interpretar($file)
{
/* Mira el archivo de excluidos y si no debo interpretarlo, devuelve false */
global $excluded_files;
if (file_exists($excluded_files))
{
$excl = file ($excluded_files);
return (!in_array($file, $excl)); /* Si la encontramos, devolvemos FALSE */
}
return true;
}

$type = (isset($_GET['type']))?$_GET['type']:false;
$file = (isset($_GET['file']))?$_GET['file']:false;

// Nos aseguramos de que las dos esté especificadas
if (($type) &amp;&amp; ($file))
{

/* Establecemos las cabeceras http necesarias */
switch ($type)
{
case 'css': header("Content-type: text/css; charset=utf-8"); break;
case 'js' : header("Content-type: text/javascript; charset=utf-8"); break;
}
header("Cache-Control: must-revalidate");

if (file_exists($basepath.$file))
{
$origftm = filemtime($basepath.$file);
$cachefile = gf_getgz_cachefile($basepath.$file); /* Genera un nombre de archivo de caché único */

@$destftm = filemtime($cachefile); /* No daremos error si no existe el archivo */

if ($origftm>$destftm)
{
/* Si el fichero original es más nuevo que su caché, lo procesamos todo de nuevo */
if (interpretar($file))
genera_y_cachea($basepath.$file, $cachefile);
else
comprime ($basepath.$file, $cachefile);
}

if ( (isset($_SERVER['HTTP_ACCEPT_ENCODING'])) &amp;&amp; (strstr($_SERVER['HTTP_ACCEPT_ENCODING'], 'gzip')))
{
header("Content-Encoding: gzip");
header("Content-Length: ".filesize($cachefile.".gz"));
readfile ($cachefile.".gz"); /* Si el navegador permite contenidos gzipeados... */
}
else
readfile ($cachefile);
}
/* else ERROR no existe el fichero CSS o JS */
}
/* else ERROR, no se ha especificado tipo de fichero o el fichero */
?>

También puedes descargarlo directamente: aquí: tcjs.php.gz (2.2Kb)
Lo que pretendo es que con este script sólo tengamos que copiar el archivo, definir un par de cosas y funcionar, y que sea totalmente transparente, tanto que nos olvidemos de que lo estamos usando.

Para instalarlo, podemos copiarlo en el directorio raiz de nuestro servidor, el ejemplo que muestro es para Apache (y es necesario tener mod-rewrite), y crear un archivo .htaccess que contenga lo siguiente:

1
2
3
4
RewriteEngine On
RewriteBase /
RewriteRule ^(.*\.css) tcjs.php?type=css&amp;file=$1
RewriteRule ^(.*\.js) tcjs.php?type=js&amp;file=$1

También tenemos que prestar atención a las primeras líneas de código del script tcjs.php:

  • $base_directory será el directorio raiz de todos los css, js, definiciones y caches (no es estrictamente necesario que sea de estos últimos). Es decir, si nuestra web está en /home/www/public_http/ no debemos llamar a nada que esté en un nivel inferior (podrán estar dentro de subdirectorios pero a partir de este punto); es más, los CSS y JS estarán por ejemplo en /home/www/public_http/js; en este caso $base_directory=’/home/www/public_http/
  • $httppath será la dirección web de menor nivel que vayamos a llamar; por ejemplo: http://www.midominio.com/
  • $cachedir será el lugar donde creemos los ficheros de caché, este directorio tiene que tener permisos para que el servidor web pueda escribir en él.
  • $excluded_files será el nombre de un archivo cuyo contenido serán todos los ficheros que no queramos que sean procesados, sólo serán comprimidos. Por ejemplo, si el fichero es /home/www/public_http/js/nieve.js y nuestro $base_directory es /home/www/public_http/, el texto que deberíamos incluir en el archivo será js/nieve.js
  • $definiciones_file es la ruta relativa a un archivo PHP que se cargará cuando vayamos a generar un CSS o JS. Puede haber dos tipos de archivo de definiciones, el global, situado en $base_directory.$definiciones_file y el local situado en (el mismo directorio que el archivo CSS a procesar).$definiciones_file. Por ejemplo:
    • $base_directory=’/home/www/public_http/’
    • El fichero JS que cargamos estará en /home/www/public_http/js/mijavascript.js
    • $definiciones_file=’defs/definiciones.php
    • tcjs.php cargará dos ficheros de definiciones situados en /home/www/public_http/defs/definiciones.php y en /home/www/public_http/js/defs/definiciones.php

El fichero de definiciones (que ya hemos visto donde está contendrá un array llamado $definiciones, pero no lo crearemos de nuevo, sino que lo continuaremos, por ejemplo:

1
2
3
4
...
$definiciones['color_base'] = '0ff00f';
$definiciones['ruta_static'] = 'http://estaticos.miservidor.com/';
$definiciones['visibilidad_mensajes'] = ($debug)?'visible':'hidden';

Podemos utilizarlo por ejemplo para definir un color de objeto desde PHP y que el CSS lo incluya (puede que debamos usarlo desde PHP también, por ejemplo para generar una imagen con ese color de fondo); para una ruta de ficheros estáticos en un servidor (normalmente en mi servidor local será otra ruta), para mostrar directamente una capa que está oculta mientras estamos programando algunas opciones en Javascript, y para muchas cosas más.

Categories: Javascript, Linux, PHP Tags: , , , , , ,

Visita otras webs de la red

Easy AdSense by Unreal