(http://www.stratos-ad.com/forums/style_images/1/pip.gif) RLE Array (http://www.stratos-ad.com/forums/style_images/1/pip.gif)
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.zipSi quieres enviar tu propio código solo tienes que hacerlo a eth_cotd@lycos.es
[/list]
Y si en vez de
// Imprimimos los valores de cada uno...
for( unsigned int i = 0; i < rleArray->getElementsCount( ); ++i )
printf( "\nArray[ %d ]: %d", i, rleArray->getElement( i ) );
haces
// 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?
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
Un código fantástico. Gracias por compartirlo con todos nosotros.
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?
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í:
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
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
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
CitarTransparencia en el acesso a datos y mejorar rapidez en el acceso a los mismos.
Que propones para ambos casos? : )
CitarPor 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!
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 ;)
Hola!
Citar
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?
Citar
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!
Citar
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!
tienes un codigo asi:
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
[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
Yo hubiese hecho algo asi:
ArregloRLE.h
//----------------------------------------------------------------------------------------------
// 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:
#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
[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
Es exactamente lo q hace el código anterior a mi post :D solo q sin leaks y sin continues guarros ;P
esto ->
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)
saludos
Hola a todos:
Pogacha:
Me cuesta bastante leer tu codigo... x(
Juan Mellado:
Pues muchas gracias por la info!! Aunque quieres decir que en Release no seria suficientemente listo como para darse cuenta? En fin, a partir de ahora sere mas estricto con el tema. Aun tengo mucho que aprender... Muchas gracias!
ethernet:
Lo del uso de iterador personalmente lo veo un poco engorroso. Soy un poco de la vieja escuela :b Aunque mayormente no haria este cambio que me dices en mi codigo porque, como ya comente, no me gustan las STL. Pero agradezco mucho tu comentario!!
Adios!!!
iterator rocks y STL rocks more
Muy bueno el COTW, seguro que lo acabo utilizando en algun sitio. Estoy de acuerdo con lo que comenta ethernet sobre la STL, al darle una interfaz similar, es más fácil(o intuitiva) de usar. P.ej.
Boost utiliza una intefaz tipo STL
Nota:
Para los principiantes que nos lean: aprended STL, una vez conocida la potencia que ofrece esta librería
estándar(forma parte de C++), sois libres de usarla o no. ;-)
Un buen sitio para empezar: www.sgi.com/tech/stl
Alguien usa STLPort? habeis notado diferencias entre las diferentes implementaciones de STL?
saludos
CitarMuy bueno el COTW, seguro que lo acabo utilizando en algun sitio.
Me alegro! De eso se trata! : )
Sobre el tema STL, yo no digo que esten mal, pero tiene el problema de que pides memoria por cada nodo que añades. Yo siempre que puedo pido todo el bloque de memoria que necesito y trabajo a partir de ahi. Los news, mientras mas grandes los puedas hacer, mejor. Es como el tema de los pools.
Por otro lado, las STL SI que las veo muy chulas para temas de Hash, por ejemplo.
Bueno, solo aclarar que no uso STL en la aplicacion de tiempo real ( en el juego, por ejemplo ) pero en aplicaciones externas, preprocesos o como querais llamarlo, hago uso intensivo : ) Facilitan mucho la vida del programador, no de la maquina : )
talogo!!
[Pogacha]
La forma de obtener el factor de compresión no es correcta. sizeof(ArregloComprimido) siempre te devuelve 16. Habría que obtener el tamaño de la memoria reservada por el objeto, no el tamaño del objeto.
[ethernet]
Claro, con el índice real sí se puede hacer. Con la implementación original no.
[Todos]
Uhm, ... a los deletes hay que ponerle los corchetes para liberar toda la memoria. :(
Uhm, ... para los valores que sólo aparecen una vez se está reservando más memoria que la que utilizan en el array. Sería interesante guardar información extra sólo para los intervalos que realmente se repiten ... <_<
+ Saludos
CitarUhm, ... para los valores que sólo aparecen una vez se está reservando más memoria que la que utilizan en el array. Sería interesante guardar información extra sólo para los intervalos que realmente se repiten ...
Esto ya lo habia pensado. De hecho, el PCX lo hace, pero no se me ocurre como conseguirlo si la compresion es con cualquier tipo de dato. El PCX, como solo comprimia valores numericos, utilizaba el bit mas alto para comprobar si eso era un numero comprimido o no. De esta forma NUNCA te ocupaba mas.
MChiz, he estado trasteando un rato para intentar minimizar la memoria reservada, y partiendo de los dos códigos anteriores me ha salido esto:
template <class Type>
class OtroArrayRLE
{
private:
typedef struct{
unsigned int begin;
unsigned int end;
unsigned int index;
}Segment;
Type * _data;
unsigned int _data_count;
Segment * _segment;
unsigned int _segment_count;
public:
OtroArrayRLE() :
_data(0), _data_count(0), _segment(0), _segment_count(0)
{
}
~OtroArrayRLE()
{
if (_data) delete [] _data;
_data_count = 0;
if (_segment) delete [] _segment;
_segment_count = 0;
}
void Adquirir(const Type * array, unsigned int n)
{
unsigned int i = 0, j = 0, data_needed = 0, segment_needed = 0;
//Primera iteración
for (; i < n; ++ i, ++ data_needed){
//Busca segmentos de elementos consecutivos con un mismo valor repetido
for (j = i; (j < n) && (array[i] == array[j]); ++ j);
//Si el tamaño del segmento es mayor que el tamaño de la estructura se guarda
if ( sizeof(Type) * (j - i) > sizeof(Segment) ){
++ segment_needed;
i = j - 1;
}
}
//Reserva memoria
_data = new Type[data_needed];
_data_count = 0;
if (segment_needed > 0) _segment = new Segment[segment_needed];
_segment_count = 0;
//Segunda iteración
i = j = 0;
for (; i < n; ++ i, ++ _data_count){
_data[_data_count] = array[i];
for (j = i; (j < n) && (array[i] == array[j]); ++j);
if ( sizeof(Type) * (j - i) > sizeof(Segment) ){
_segment[_segment_count].begin = i;
_segment[_segment_count].end = j - 1;
_segment[_segment_count].index = _data_count;
++ _segment_count;
i = j - 1;
}
}
}
Type operator[](unsigned int index)
{
//Caso base, array sin comprimir
if (_segment_count == 0){
return(_data[index]);
}
//Búsqueda binaria del índice dentro de la lista de repetidos
unsigned int i = 0;
unsigned int l = 0;
unsigned int r = _segment_count;
while(true){
i = (r - l) / 2;
if (i != 0){
if (index <= _segment[i - 1].end){
r = i;
continue; //Buscar a la izquierda
}
}
if (i != _segment_count - 1){
if (index > _segment[i].end){
l = i;
continue; //Buscar a la derecha
}
}
break; //Encontrado
}
//Índice encontrado, retorna el valor
if (index < _segment[i].begin){
return(_data[_segment[i].index - (_segment[i].begin - index)]);
}
if (index > _segment[i].end){
return(_data[_segment[i].index + (index - _segment[i].end)]);
}
return(_data[_segment[i].index]);
}
};
Básicamente guarda dos arrays, uno con los datos comprimidos, y otro con los segmentos de datos del array original que se repiten (inicio y final en el array original, e inicio en el array comprimido).
El método Adquirir recorre el array original guardando datos, y detectando segmentos. Sólo se almacena info de un segmento si el tamaño del segmento es menor que el tamaño de dicha info.
El operador [] recorre binariamente la lista de segmentos intentando localizar el índice dado, dentro de un segmento, entre dos segmentos, antes del primer segmento, o después del último segmento.
No está muy probado
:unsure:
[juan]
Con la implementacion original se puede hacer perfectamente, es mas, es lo q habeis hecho pogacha y tu. MChiz tiene q saber por huevos el indice real de forma directa o indirecta, aunque el lo haga sumando las Count de cada Bucket. Es mucho mas inteligente tener el indice real que tener la cuenta para mejorar el acceso, eso no cabe duda.
[MChiz]
Programate tu propio allocator ;), la memoria no es excusa para no usar STL
Otra cosa interesante seria tener una cache. En el cotd de flipcode hace poco aparecio un codigo llamado LRUcache (de unai landa) que puede ser util tb para tener guardados los ultimos accesos.
saludos
Hola!
Para Juan:
Muy chulo : ), pero esos continues y ese break no me gustan :b No se que mas decir!
Para ethernet:
Programarme mi allocator... me da un poco de palo xP No le he hecho nunca.
El tema de la cache esta muy interesante.
Alguien esta haciendo ya el proximo COTW??? Que el lunes se acerca! :b
talogo!
Bien ... estuve pensando en el tema y concluyo:
Sobre el codigo original:
Bueno! (ole)
La idea es interesante, no se me ocurrio nunca la idea de una clase para
almacenar datos comprimidos (este tema se lo maneja mas en c y en la programación grafica y de juegos este tema es solo una herramienta, no un fin).
Al final todas las propuestas perdieron la glamorosidad que tenia el codigo original no?. Estaba muy elegantemente estructurado.
Seria bueno enumerar la lista de aplicaciones como para evaluarlo y entenderlo.
Por ahora solo se me ocurren estas:
Entrada de teclado o eventos del juego, para grabar un demo o algo asi.
Cierta información pesada sobre el mapa o personaje, por ejemplo, en el diablo II cuando salias de una pantalla los "bichos" volvian a aparecer como nada. En este caso el algoritmo de compresion debe ser otro, pero la base es la misma.
Sobre mi codigo:
Lo arme en una hora ...
No lo investiguen mucho, era para darle un vistaso nada mas.
Pero al poco tiempo se me ocurrio la idea que implemento Juan Mellado, que por cierto es mejor que el hashing o cualquier cosa de esas ( no tuve la vision para verlo en el momento ).
Sobre el factor de compresion, ni lo pense ... como era para notar la idea
El tema de las estructuras Bucket, Segmento o vectores paralellos:
Tienen una regla, si vas a pasar como argumento estos datos, metelos en una estructura o clase, pero si no, siempre convienen los vectores paralelos y pasar un indice (Afirma el ingeniero Hugo Reiquebuer).
En este caso todos los datos quedan dentro de la capsula, externamente no nos interesa como se repiten o no, por ende los vectores paralelos sobran, pero si los datos son complejos como en el codigo de Juan Mellado es preferible la estructura.
A fin de cuentas para mejorar la busqueda debes almacenar elementos repetidos y elementos que no se repiten y cuantos como datos.
Juan Mellado:
Segmento[i+1].Start==Segmento.End+1 ? Message("Segmento.End superfluo") : Message("No entendí"); ;)
Hace unos años se me ocurrio un metodo que usa este principio para mejorar la compresion RLE.
void Descomprimir(FILE *in, FILE *out)
{
char c,d;
while(!FEOF(in))
{
c=fgetc(in); // cuantos
if(c>0) // se repiten
{
d=fgetc(in); // que se repite
while(c--) fputc(out,d);
} else
if(c<0) // no se repiten
while(c++) fputc(out,fgetc(in));
}
}
Por sierto alguna busqueda binaria sin continue y sin recursion que alguien pueda aportar nos caeria bien y si alguien implemento una version final del ArregloRLE con STD seria bueno verla. O_O
Saludos
Pogacha.
Citar
Segmento[i+1].Start==Segmento.End+1 ? Message("Segmento.End superfluo") : Message("No entendí");
Output: No entendí.
Ejemplo:
Array original: {1, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 17, 23, 23, 23, 23, 23};
Array comprimido: {1, 10, 5, 17, 23}
Array de segmentos {begin, end, index}: { {1,
6, 1}, {
7,
10, 2}, {
12, 16, 4} }
Cuando hay dos segmentos juntos si coincide end
+ 1 con begin[i+1]. Pero no cuando hay datos sin comprimir entre dos segmentos.
Saludos
Hola, es la primera vez que posteo por estos foros, aunque algunos ya me conocereis del irc.
Interesante y original el codigo, algunos comentarios:
-Hay que tener en cuenta que RLE solo funcionara en casos muy concretos. Por otro lado, el coste de getElement es _muy_ grande, por lo que solo se hace util con arrays pequeños. Y para ganar un par de bytes, tampoco hace falta que te compliques demasiado. Y tambien deberia poder crearse y ampliarse el array poco a poco para que el ahorro de memoria sea continuado, porque de esta forma lo que tienes es mas bien un "liberador de recursos", en vez de un array. Esto implicaria usar una lista o un array que se autoincremente, estilo std::vector. La allocacion de std::vector si es rapida, ya que cada vez que debe ampliar el array reserva mas memoria que la que necesita (p.ej. duplicar el tamaño del array cuando necesite crecer es habitual), aunque claro esta que esto no seria lo mas eficiente en cuanto a uso de memoria
-He entendido antes que decis que usar un struct en vez de una clase elimina la vtable. Un struct es identico a una clase, solo cambia el nivel de acceso por defecto (public en vez de private). Lo que eliminara la vtable sera no tener ningun metodo virtual.
-Un interface tipo stl con iterators estaria bien, pero no olvides un operator[] ;). Por otro lado, aprovechando esto, podria optimizarse para un acceso secuencial a los datos mas rapido, ya que no tendrias que realizar la busqueda desde 0 en cada iteracion.
-La clase Bucket me da la impresion de que estaria mejor dentro de la clase Array. La funcion que realiza compress() opino que deberia estar disponible desde el constructor de Array y adicionalmente como un metodo en la clase. Igual para decompress(). Ademas, de esta forma meterias la administracion de memoria dentro de la clase, depender de deletes es odioso y acabas con leaks a la minima. El metodo setBuckets() opino que sobra, no le veo mucho sentido ya que se supone que nadie va a utilizar la clase Bucket directamente. Lo mismo para la getBuckets(), o bien deberia devolver un puntero a datos const, para evitar al menos que puedan modificar el array desde fuera "sin avisar" y cargarse todo, si la intencion de dar acceso al array interno es poder ampliar la funcionalidad, derivas de la clase y añades la funcionalidad que quieras. Para ello, es mejor acostumbrarse a usar private solamente en los datos que realmente son depedientes de la implementacion y no del interface, y protected para el resto de datos que no quieres que los usarios vean, pero si alguien que quiera ampliar la clase.
Juan Mellado:
-Ten en cuenta lo que ocurriria si copias un objeto Array a otro. Tendrias dos instancias apuntando al mismo puntero, a la minima todo haria -chof-. Por ello, seria necesario un operator= y un constructor de copia (aunque sean privados o aunque no tengan implementacion, para al menos evitar que se pueda copiar y le suelte un error de compilacion/linkado).
-No es necesario comprobar si el puntero vale 0 antes de hacer un delete, él mismo lo comprueba. El typedef para el struct tambien es redundante.
Algunas de las cosas que comento ya las ha implementado Juan en su modificacion.
Hola Diego, bienvenido.
Gracias por tus comentarios.
Citar
... seria necesario un operator= y un constructor de copia ...
Por supuesto. Y el destructor debería ser virtual si se preveé herencia, ¿no?
Citar
-No es necesario comprobar si el puntero vale 0 antes de hacer un delete, él mismo lo comprueba.
Uhm!, no lo sabía. He estado mirando, y sí, es cierto. Gracias. Siempre lo he comprobado.
Citar
El typedef para el struct tambien es redundante
Lo del typedef es costumbre para todos los tipos, lo prefiero.
Nota: Si alguien quita el typedef en el código (sin hacer nada más que eso) declarará una variable Segment, no una estructura llamada Segment.
Saludos