Rle Array - Mchiz

[ethernet]

 Es exactamente lo q hace el código anterior a mi post :D solo q sin leaks y sin continues guarros ;P

esto ->

Código [Seleccionar] Expand



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

[MChiz]

 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!!!

[ethernet]

 iterator rocks y STL rocks more

[Zaelsius]

 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. ;-)

[ethernet]

 Un buen sitio para empezar: www.sgi.com/tech/stl

Alguien usa STLPort? habeis notado diferencias entre las diferentes implementaciones de STL?

saludos

[MChiz]

 

Muy 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!!

[Juan Mellado]

 [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

[MChiz]

 

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 ... 

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.

[Juan Mellado]

 MChiz, he estado trasteando un rato para intentar minimizar la memoria reservada, y partiendo de los dos códigos anteriores me ha salido esto:

Código [Seleccionar] Expand


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:  

[ethernet]

 [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

[MChiz]

 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!

[Pogacha]

 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.

[Juan Mellado]

 

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

[Diego]

 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.

[Juan Mellado]

 Hola Diego, bienvenido.

Gracias por tus comentarios.

... seria necesario un operator= y un constructor de copia ...

Por supuesto. Y el destructor debería ser virtual si se preveé herencia, ¿no?

-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.

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