Rle Array - Mchiz

[ethernet]

       RLE Array  

Espero que el código que aquí envío sea de tanta ayuda para muchos de vosotros como lo fue para mi en su momento. Se trata de un... 'manager' sobre el manejo de la compresion RLE en general. Lo chulo que tiene ( creo ) es que puedes tener en memoria un array RLE y acceder a ella como si fuese un array normal. Sacrificas un poco de tiempo de ejecución, pero puedes ahorrar muchísima memoria.
Personalmente me vi impulsado a hacer esto programando un algoritmo de busqueda de caminos. Desde un punto del mapa se podian ir a un montonazo, pero siempre tenias que pasar por uno de los X vecinos que tuvieses en ese momento, que suelen ser pocos ( en mi caso 3 como mucho ). Utilizaba una tabla de enrutamiento. Bien, sin comprimir la puñetera tabla me ocupaba algo así como 500 megas de memoria. Al pasarle el RLE consegui que se quedara en medio mega!! Al ver esto me di cuenta que no debía guardarmelo para mi solo :)
No utilicé exactamente los algoritmos que he puesto aquí, porque aquél código está un poco hecho polvo y sólo servía para comprimir valores numéricos. Ahora lo he hecho un poco más general y sirve para cualquier tipo de dato ( vivan los templates! ). No sé si me ha quedado intuitivo o no; yo pienso que sí, pero si alguien tiene mejoras, ya sabéis :)
Un saludote a todos!!

Un ejemplo de como se usan es el siguiente

//--------------------------------------------------------------------------------------------------------------------
// Programa ejemplo de las clases RLE.
//--------------------------------------------------------------------------------------------------------------------
#include
#include

#include "RLEArray.h"

void main( ) {
   // Array en crudo para comprimir
   int rawArray[ ] = {
      1, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 23, 23, 23

   };

   // Comprimimos 'rawArray'. El resultado esta en rleArray
   NSRLE::Array< int > *rleArray = NSRLE::compress< int >( rawArray, sizeof( rawArray ) / sizeof( rawArray[ 0 ] ) );

   printf( "\nArray comprimido con exito" );

   // Comprobamos por si no se ha podido reservar memoria para el array
   assert( rleArray );

   // Elementos REALES del array RLE
   printf( "\nElementsCount: %d", rleArray->getElementsCount( ) );
   
   // Imprimimos los valores de cada uno...

   for( unsigned int i = 0; i < rleArray->getElementsCount( ); ++i )
      printf( "\nArray[ %d ]: %d", i, rleArray->getElement( i ) );

   // Informacion acerca de la memoria ocupada...
   printf( "\nDatos ocupados NO comprimidos: %d bytes",
      sizeof( NSRLE::Bucket< int > ) // Tamaño de un bucket ( dato )

      *
      rleArray->getElementsCount( ) // Numero REAL de buckets ( en este caso 4 + 2 + 2 + 58 )
   );
   printf( "\nDatos ocupados comprimidos: %d bytes",
      sizeof( NSRLE::Bucket< int > ) // Tamaño de un bucket ( dato )

      *
      rleArray->getBucketsCount( ) // Numero de buckets comprimidos ( en este caso 4 )
   );

   // Descomprimimos el array RLE. El resultado esta en decompressedArray
   int *decompressedArray = NSRLE::decompress< int >( rleArray );

   // Comparamos todos los elementos del array RLE con el array acabado de descomprimir. Asi veremos si ha habido algun error
   for( unsigned int i = 0; i < rleArray->getElementsCount( ); ++i )

      assert( decompressedArray[ i ] == rleArray->getElement( i ) );

   printf( "\nArray RLE descomprimido con exito" );

   getch( );

   delete rleArray;

   rleArray = NULL;

   delete [ ]decompressedArray;
   decompressedArray = NULL;
}



Puedes descargarte el código de la siguiente dirección:

http://www.stratos-ad.com/codigosemana/rlearray.zip

Si quieres enviar tu propio código solo tienes que hacerlo a eth_cotd@lycos.es

[/list]

[Mars Attacks]

 Y si en vez de

Código [Seleccionar] Expand


// Imprimimos los valores de cada uno...
for( unsigned int i = 0; i < rleArray->getElementsCount( ); ++i )
printf( "\nArray[ %d ]: %d", i, rleArray->getElement( i ) );


haces

Código [Seleccionar] Expand


// Imprimimos los valores de cada uno...
unsigned int elem_count=rleArray->getElementsCount( );
for( unsigned int i = 0; i <elem_count; ++i )
printf( "\nArray[ %d ]: %d", i, rleArray->getElement( i ) );


¿No ganarías algo de velocidad en ese for al no tener que llamar todo el rato a ese valor de la estructura o daría igual?

[NeLo]

 Mars Attack tiene razón :blink:

Es un "error" típico en los bucles.

Excelente el COTW.

Saludos.

PD: ethernet, ¿por qué la dirección de e-mail para enviar el COTW es eth_cotd@lycos.es? O_O  

[Haddd]

 Un código fantástico. Gracias por compartirlo con todos nosotros.

[Mars Attacks]

 Code Of The Doom. Está claro  ;)

Y me ha parecido una barbaridad ese pedazo de factor de compresión. ¿Puedes explicar mejor en qué consiste lo del RLE para gente no programadora?

[Juan Mellado]

 Hola a todos,
buen código MChiz.

Se me ha ocurrido que se podría parametrizar un poco más el template Bucket añadiendo el tipo de _count como parámetro. Algo así:

Código [Seleccionar] Expand


template < class Type, class Size >
class Bucket {
public:
Bucket( )
: _count( 0 ) {
}

Bucket( Type data, Size count )
: _count( count )
, _data( data ) {
}

virtual ~Bucket( ) {
 destroy( );
}

void destroy( ) {
}


void setData( Type data ) { _data = data; }
Type getData( ) const { return _data; }

void setCount( Size count ) { _count = count; }
Size getCount( ) const { return _count; }

private:
Type _data;
Size _count;
};


Otra cosa:

Realmente la clase Bucket es una clase de "datos" (sin funcionalidad), como una estructura (struct) de toda la vida. Sin embargo, por cada objeto Bucket creado se reserva memoria para un puntero a la vtable (4 bytes).

Si se utiliza el tipo int (4 bytes) para _data y _count, entonces el puntero ocupa un tercio de toda la memoria ocupada por cada objeto. Para 500 K, los punteros ocupan 166 K del total.

¿Merecería la pena tratar Buckect como struct para ahorrar esa memoria?, ¿O usar structs rompe la orientación a objetos?, ¿Eficiencia contra "purismo"?, ¿Qué opináis?.

Saludos

[MChiz]

 Hola a todos!

Para Mars Attacks y NeLo:
La optimizacion que me proponeis estoy casi convencido que el compilador la efectua en modo release, ya que la funcion 'getElementsCount( )' es una funcion inline, y el compilador la substituye. En cualquier caso, si lo que digo no es cierto ( que yo juraria que si ), lo que deciis si que añadiria velocidad. Pero vaya, que eso lo hago en el programa de ejemplo. Luego cada uno que lo utilice como quiera : )

Para Mars Attacks:
La compresion RLE consiste en comprimir datos iguales QUE ESTEN SEGUIDOS. Por ejemplo, un array de diez unos quedaria comprimido en un 10 y un 1 ( El 10 es el numero de veces que el dato ( 1 ) esta repetido ). No se si me he explicado... se me da muy mal : ( Si alguien lo sabe explicar mejor... Este tipo de compresion es utilizada por los famosos archivos PCX : )

Para Juan Mellado:
La optimizacion numero 1 que me propones ( la de parametrizar el miembro '_count' ) no se si entiendo bien su cometido. Le consigo ver la ventaja, por ejemplo, si no vas a tener mas de 255 datos repetidos; asi puedes hacer que sea un unsigned char. Lo haces por eso? La verdad es que no se me habia ocurrido. Muchas gracias! : )
Acerca de la segunda optimizacion... JO-DER :b No habia pensado en ello. Pero dandole vueltas... quieres decir que no tratara la clase como una estructura? La vtable solo es necesaria si la clase tiene funciones virtuales o siempre esta ahi? Es que hasta ahi no llego :b Si es como tu dices, personalmente la trataria como una estructura... es mas, no se porque leches la he hecho clase :b En mis trabajos, si solo son datos, los hago como estructuras... Pero bueno, asi he aprendido esto : ) Muchas gracias nuevamente!!

Para todos:
Me alegro MUCHISIMO que os haya gustado el codigo de la semana!! Esto anima muchisimo : ) Intentare pensar en alguna otra cosa. Muchas gracias, en serio. Esto anima mucho. A ver si otra gente se monta al carro : )

Besitos a las nenas y pataitas a los nenes :b

[ethernet]

 Yo propongo dos cosas:

Transparencia en el acesso a datos y mejorar rapidez en el acceso a los mismos.

Por otra parte en la compresion recorres el vector 2 veces cuando solo es necesario recorrerlo 1 y haces tantas reservas de memoria como numero diferente de datos hay cuando recorriendolo dos veces solo necesitas hacer un new.

enhorabuena por el cotw!!

Nelo: no hay ninguna razon, simplemente cuando pille ese mail no tenia pensado el nombre de la seccion ;)


saludos

[MChiz]

 

Transparencia en el acesso a datos y mejorar rapidez en el acceso a los mismos.

Que propones para ambos casos? : )

Por otra parte en la compresion recorres el vector 2 veces cuando solo es necesario recorrerlo 1 y haces tantas reservas de memoria como numero diferente de datos hay cuando recorriendolo dos veces solo necesitas hacer un new.

hm? Creo que esto no lo entiendo. Necesito recorrer el array dos veces para:
1.- Cuento cuantos datos distintos hay en el array y me quedo con la cuenta
2.- Una vez tengo la memoria reservada, me voy guardando los datos ahi.

Si hubiese usado STL esto no haria falta, pero es que no me gusta usarlas. Siempre que se puede utilizar news grandes lo hago. No te fragmenta la memoria y favoreces la cache.
Explicame que es lo que tienes pensado, por favor!!

Aioos!

[ethernet]

 Para la transparencia usaría iterator y un interface similar a stl para poder cambiar rápidamente tu código (cambiando un typedef y ya está). Por orta parte usaría una clase como sort de STL (http://www.sgi.com/tech/stl/sort.html) en la que en el template se le indicara la función de comparación. Hay tipos que puede q no tengan sobrecargado ==.

Para agilizar la búsqueda en getElement() usaría el típico truco de buscar la mitad, si es mayor pillar la mitad superior, sino la inferior (un arbol vaya ;) puesto que tienes ordenados por índice.

dos cosas: por qué getElement no retorna una referencia?
                 Has pensado en la posibilidad de escribir en el array? se complica el tema XD
saludos ;)

[MChiz]

 Hola!

Para la transparencia usaría iterator y un interface similar a stl para poder cambiar rápidamente tu código (cambiando un typedef y ya está).

Esto no lo acabo de entender... cambiar el codigo a que?

Por orta parte usaría una clase como sort de STL (http://www.sgi.com/tech/stl/sort.html) en la que en el template se le indicara la función de comparación. Hay tipos que puede q no tengan sobrecargado ==.

Esta otra cosa no la conocia. Es algo que no me acababa de gustar. Muchas gracias : ), lo mirare!

Para agilizar la búsqueda en getElement() usaría el típico truco de buscar la mitad, si es mayor pillar la mitad superior, sino la inferior (un arbol vaya  puesto que tienes ordenados por índice.

Pues si. No me acorde... nuevamente, gracias! Todos estos cambios los hare a partir de la semana que viene, que esta me viene un poco mal...

Saludoteees!

[ethernet]

 tienes un codigo asi:

Código [Seleccionar] Expand


template <class T>
class foo
{

   void f( T &o)
   {
         T::iterator v;
         for(v = o.begin();v != o.end(); ++v){...}
         cout << o[9]  ;

   }
   

};


imagiínate q quieres usar un std::vector o un RLEArray con esa clase, no tendrías q cambiar nada.
Es solo un comentario, eso debe ir en funfción del interfaz que uses tu.

saludos  

[Juan Mellado]

 [MChiz]
Exacto, lo has pillado.  :D

La propuesta número 1, además de para lo que comentas, es para no tener que utilizar unsigned int forzosamente. Ya que normalmente los tipos básicos se redefinen con typedef (Ejemplo: typedef unsigned int UINT32). Al otro template habría que hacerle algo parecido.

Respecto a la segunda sugerencia. Al crear el array de objetos con new, SÍ, se crea un puntero a la vtable por cada objeto. Si tienes dudas, aparte de preguntar ;) , te sugiero que uses el depurador. Pones un breakpoint en la sentencia que crea el array, y una vez creado, miras el contenido de la memoria del puntero devuelto (hex dump), verás los punteros.


[ethernet]
Una cosa que no me ha quedado clara, ¿cómo utilizar la búsqueda binaria en getElement() si el array está comprimido con RLE?.  Para irse a la mitad de la lista debe recorrer secuencialmente la lista, y sumar los _count hasta encontrar la mitad de la lista. No puede ir directamente a la mitad. ¿No?

No sé, no lo veo. A bote pronto, se me ocurre que guarde una lista con unos pocos punteros (o lo que sea, en función de un criterio determinado) que indique donde se encuentra la mitad, la mitad de la mitad, la mitad de la mitad, y así sucesivamente, para luego recorrer linealmente la porción adecuada.


Saludos

[Pogacha]

 Yo hubiese hecho algo asi:


ArregloRLE.h

Código [Seleccionar] Expand


//----------------------------------------------------------------------------------------------
// Titulo: RLEManager? :P
// Autor: Carlos Campaña Molinero / MChiz
// Mail: MChis@ozu.es
// Fecha: 8 - 7 - 2003
//
// Version: 1.0
//----------------------------------------------------------------------------------------------
// Modificacion no autorizada
// Autor: Pogacha
// Mail: ferreyra@arnet.com.ar
// Fecha: 21 - 7 - 2003 - 12:30 a 2:10
//---------------------------------------------------------------------------------------------
#pragma once

#ifndef __ARREGLORLE_H__
#define __ARREGLORLE_H__

// #include <assert.h> // Sencillo y corto como patada de chancho
#define NULO (0)

template < class Tipo >
class ArregloRLE
{
 public:
 ArregloRLE( )
: _Datos( NULO )
, _Repetividad_Integrada( NULO )
, _n_Elementos( 0 )
, _n_Datos( 0 )
       {
       }

       ~ArregloRLE( )
       {
   if(_Datos) delete _Datos;
   if(_Repetividad_Integrada) delete _Repetividad_Integrada;
   _Datos=NULO;
          _Repetividad_Integrada=NULO;
   _n_Elementos=0;
    _n_Datos=0;
}

 void Adquirir( const Tipo *Arreglo, unsigned int n )
 {
               int i;
  unsigned int *Repetividad= new unsigned int[n];
  _n_Elementos = n;
  _n_Datos=0;
  for(i=0;i<_n_Elementos;i++) Repetividad[i]=0;
  i=0;
  while(++i < _n_Elementos)
  {
   Repetividad[_n_Datos]++;
   if(Arreglo[i-1]!=Arreglo[i]) _n_Datos++;
  }
  _Datos=new Tipo[++_n_Datos];
  _Repetividad_Integrada= new unsigned int[_n_Datos];

               _Repetividad_Integrada[0]=0;
  for(i=1; i<_n_Datos; i++)
       _Repetividad_Integrada[i]=Repetividad[i-1]
                                             +_Repetividad_Integrada[i-1];

        for(i=0; i<_n_Datos; i++)
       _Datos[i]=Arreglo[_Repetividad_Integrada[i]];

 delete Repetividad;
}

Tipo operator[](int i)
{
    int l,r,m;
    if((unsigned int)i>_n_Elementos) return Tipo(); // Lo que quieras no importa
     l=0;
    r=_n_Datos-1;

    do {
 m=(l+r)/2;
      if(i<_Repetividad_Integrada[m]) { r=m; continue; }  
// perdon por el continue
     if(i>=_Repetividad_Integrada[m+1]) { l=m+1; continue; }
               l=r;
    } while(l<r)
           return _Datos[m];
       }

       int n_Elementos()
// yo lo dejo como publico, pero si a ustedes les gusta asi
       {
           return _n_Elementos;
       }

 private:
Tipo *_Datos;
unsigned int *_Repetividad_Integrada;
unsigned int _n_Datos;
unsigned int _n_Elementos;
};

#endif


El main.cpp seria:

Código [Seleccionar] Expand


#include <stdio.h>
#include <conio.h>

#include "ArregloRLE.h"

void main( )
{
// Arreglo en crudo para comprimir
int ArregloCrudo[ ] =
{
 1, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 23, 23, 23
};

// Creamos el ArregloRLE
ArregloRLE< int > ArregloComprimido;

// Adquirimos, o sea, comprimimos!
ArregloComprimido.Adquirir( ArregloCrudo,14);

printf( "\nArreglo comprimido con exito" );

// Imprimimos los valores de cada uno...
for(int i = 0; i < ArregloComprimido.n_Elementos( ); i++ )
 printf( "\nArreglo[ %d ]: %d", i,  ArregloComprimido[i] );

       printf("\nFactor de compresion:  %d : %d = %f",sizeof(ArregloCrudo),sizeof(ArregloComprimido),float(sizeof(ArregloCrudo))/float(sizeof(ArregloComprimido)));

// la descompresion se las dejo para luego, al igual que las tablas de hashing y toda esa onda.
       getch();
}

Si alguien no le gusta me cuenta.
Saludos Pogacha

[ethernet]

 [Juan]

hablo de hacerlo en el array de Buckets usando el indice real. De esta manera empiezas por la mitad del array de Buckets mirando el indice real al q corresponde. Si el indice q buscas esta comprendido entre ese y la mitad mas uno has acertado,si es mayor pillas los speriores y si es inferior la otra parte, repitiendo la operacion (tipica funcion recursiva).

Tp pense en algun tipo de hash (en funcion del indice real), pero no se me ocurre nada ;(

saludos