Huffman en c++.
A continuación explico el código (ver la explicación del algoritmo de huffman).
Escritura a un archivo.
No se puede escribir bit por bit a un archivo. Para que nuestro programa pueda ir escribiendo bit por bit la información requerida necesitamos crear una clase (objeto) que actúe como intermediario entre el algoritmo de compresión y el archivo. La llamaremos ARCH_OUT:
class ARCH_OUT { FILE *Arch; unsigned char indice; unsigned char byte; public: ARCH_OUT(unsigned char*,unsigned char*); ~ARCH_OUT(); bool Fallo(){return !Arch;} void Bit(unsigned int); void Buffer(unsigned char*,unsigned int); };
Esta clase contiene tres variables. La primera es de tipo FILE y sirve para almacenar el puntero al archivo abierto.
Dijimos que no podemos escribir bit por bit a un archivo. Entonces haremos lo siguiente: Escribiremos los datos en un buffer de un byte, llenándolo bit a bit, y cuando esté lleno lo vaciaremos al archivo.
Entonces la segunda variable es la que nos indica en que bit del buffer vamos escribiendo, y la tercera variable es el buffer.
Ésta clase tiene un constructor y un destructor. El constructor se encarga de crear el archivo con el nombre y atributos especificados. El destructor tiene que escribir lo último que nos quedó en el buffer (si es que quedó) y cerrar el archivo.
También tiene tres métodos. El primero, llamado “Fallo”, retorna un valor verdadero si el archivo no pudo ser creado y un valor falso si fue creado exitosamente. El segundo, llamado “Bit”, recibe un bit y lo almacena en el buffer para guardarlo al archivo. Si éste último está lleno entonces vacía el buffer al archivo y pone a cero el índice.
El tercer método se encarga de escribir un buffer de bits al archivo. Esto es muy útil ya que dijimos que los caracteres codificados podían tener una longitud de bits variable. Entonces esta función simplemente recibe el puntero al buffer y la cantidad de bits que debe tomar de allí y los escribe al archivo. Debemos tener en cuenta que esta función escribirá primeramente los bits existentes en el buffer si los hay, luego los bits recién indicados, y por último dejará en el buffer los bits que no alcanzaron a completar un byte para ser escritos.
Lectura desde archivo.
Así como no se puede escribir a un archivo bit por bit, tampoco se puede leer desde un archivo bit por bit. Así que nuestra clase intermedia se llamará ARCH_IN:
class ARCH_IN { FILE *Arch; unsigned char indice; unsigned char byte; public: ARCH_IN(unsigned char*,unsigned char*); ~ARCH_IN(); bool Fallo(){return !Arch;} unsigned int Bit(); unsigned int Byte(); FILE *Base(){return Arch;} };
Las tres variables tienen el mismo propósito que las de la clase anterior (ARCH_OUT). El constructor solamente abre el archivo y pone a cero el índice. El destructor simplemente cierra el archivo. El método “Fallo” tiene el mismo objetivo que el de la clase anterior.
El método “Bit” tiene se fija si hay bits en el buffer. Si los hay, lee el que corresponde e incrementa el índice. Si no los hay, lee un byte del archivo (cargando así el buffer) y lee el primer bit incrementando luego el índice.
El método “Byte” es utilizado para leer un byte desde el archivo. Nótese que parecería que uno simplemente podría leer ese byte normalmente con las funciones estándares del lenguaje. Pero esto no es así debido a que ese byte puede, por ejemplo, ser los últimos tres bits de un byte y los primeros 5 del siguiente. Éste fenómeno se da al leer el árbol.
En esta clase no es necesaria una función para leer una cantidad de bits variable. Esto se debe a que cuando leemos el archivo original leemos byte por byte, y cuando leemos el archivo comprimido leemos bit a bit o byte a byte, pero nunca otra longitud de bits.
Y por último el método “Base” devuelve un puntero al archivo abierto para que el descompresor pueda verificar por su cuenta, de corrido (sin sucesivas llamadas al método “Byte”), los primeros caracteres del archivo. Éstos contienen el sello “hfm” que indica que el archivo está comprimido mediante este algoritmo. Ese sello lo ponemos nosotros al crear el archivo comprimido.
Hojas del árbol compresor.
Las hojas del árbol creado al comprimir tienen métodos y variables diferentes a las utilizadas para descomprimir.
Ésta es la clase “HOJA”, utilizada para comprimir (también es utilizada por los nodos):
class HOJA { unsigned int cCod; class HOJA *HojaIzquierda; class HOJA *HojaDerecha; class HOJA *pNIzq; class HOJA *pNDer; unsigned int lFrec; bool EsNodo; public: HOJA(unsigned int Codigo){pNIzq=NULL;pNDer=NULL; HojaIzquierda=NULL;HojaDerecha=NULL;lFrec=0; cCod=Codigo;EsNodo=false;} HOJA(HOJA *Izquierda, HOJA *Derecha); ~HOJA(); unsigned int Frecuencia(){return lFrec;} void Frecuencia(unsigned int Cuanto){lFrec=Cuanto;} class HOJA *HojaDer(){return HojaDerecha;} void HojaDer(HOJA *Cual){HojaDerecha=Cual;} class HOJA *HojaIzq(){return HojaIzquierda;} void HojaIzq(HOJA *Cual){HojaIzquierda=Cual;} unsigned char Codigo(){return cCod;} bool MoverADer(); bool MoverAIzq(); void CrearCodigo(class CABECERA*,struct CODIGO*); void CrearCabecera(class ARCH_OUT*); };
La variable “cCod” almacenará el código del carácter correspondiente a esa hoja si es que es una hoja y no un nodo. Esto último lo determina la variable booleana “EsNodo”. La variable “lFrec” almacenará cuantas veces se repite ese carácter en el archivo, o sea, su frecuencia.
Las variables “HojaIzquierda” y “HojaDerecha” apuntarán a la hoja inmediatamente a la izquierda o derecha mientras dure el proceso de conteo de frecuencias y ordenación según frecuencia. Recordemos que en este periodo el árbol no es un árbol todavía sino una alfombra de hojas.
Cuando ya hayamos recorrido todo el archivo y contado todas sus frecuencias y ordenado las hojas según su frecuencia empezaremos a armar el árbol. Las variables “pNIzq” y “pNDer” apuntarán a la hoja u nodo que se encuentre inmediatamente abajo a la derecha o abajo a la izquierda de este nodo. En el caso de que este objeto fuera una hoja y no un nodo, ambas variables estarían puestas a cero, ya que no tendrían nada abajo.
Veamos ahora el constructor. Como dijimos que este objeto puede ser tanto una hoja como un nodo, el constructor está sobrecargado. Así, si queremos crear una hoja llamaremos al constructor pasándole como argumento solamente el código del carácter para esa hoja. Si en cambio le pasamos dos argumentos, la clase interpretará que es un nodo y supondrá que le estamos pasando el puntero a la hoja izquierda y a la derecha.
El destructor también es interesante. Éste destruye primero las hojas u nodos que tenga abajo, si es que los tiene. De esta forma uno elimina el nodo de la raíz del árbol y éste se encarga de eliminar todo el árbol antes de desaparecer.
Como las variables del objeto son privadas y no públicas, los siguientes 7 métodos simplemente devuelven el valor de alguna de estas variables al que lo solicite.
Cuando queramos armar el árbol necesitaremos ir ordenando las hojas y nodos según su frecuencia. Para eso necesitaremos moverlas a la derecha o a la izquierda de la otra hoja u nodo. De eso se encargan los métodos “MoverADer” y “MoverAIzq”.
La función “CrearCabecera” es recursiva. La primera llamada debe ser a la raíz del árbol. Éste se encargará de ir llamando a cada nodo y hoja para que vayan escribiendo en el archivo su parte del código de la composición del árbol, que debe ser leído después por el descompresor para saber como era el árbol. Este método recibe como parámetro el puntero a la clase intermedia al archivo de salida.
La función “CrearCodigo” también es recursiva, y se encarga de crear los nuevos códigos para cada carácter de acuerdo a su ubicación en el árbol.
Hojas del árbol descompresor.
Este árbol es más simple que el anterior:
class HOJA_DESC { class HOJA_DESC* pHDer; class HOJA_DESC* pHIzq; bool EsNodo; unsigned int Cod; public: HOJA_DESC(class ARCH_IN*); ~HOJA_DESC(); unsigned int Descomprimir(class ARCH_IN*,FILE*, unsigned int); };
Este árbol no tendrá una hoja u nodo a la izquierda ni a la derecha, sino solo abajo a la izquierda o la derecha. Esto es así porque este árbol no se arma ordenando frecuencias sino leyendo directamente como es el árbol. Por lo tanto tampoco tiene la variable que contiene la frecuencia de aparición del carácter, no es necesaria.
El constructor recibe como parámetro el puntero a la clase intermedia al archivo de entrada. El constructor es recursivo, según lo que encuentre en el archivo de entrada seguirá creando todas las hojas y nodos necesarios hasta terminar de construir el árbol. De esta forma es suficiente crear una hoja pasándole el puntero a la clase intermedia para que se construya todo el árbol automáticamente.
El método “Descomprimir” también es recursivo, y basta con llamarlo en la raíz del árbol para que descomprima todo el archivo.
Código del caracter.
Esta estructura guarda el código binario que representará a tal o cual caracter.
struct CODIGO { unsigned char *Cod; unsigned int Tam; };
Por ejemplo, si la letra ‘a’ (ASCII=97) ahora está ubicada dos nodos a la derecha, su código será 11 binario (3 decimal). Entonces en este ejemplo la variable Cod apuntaría a un array de un carácter que contendrá un 3 (decimal) y la variable Tam será igual a 2, ya que la longitud del código binario es igual a 2 (11, son dos unos).
Clase “CABECERA”.
Esta clase es utilizada por la clase “HOJA” para ir guardando el código de cómo fue armado el árbol para luego ser volcada al archivo. Esta información será necesaria cuando queramos descomprimir, ya que deberemos saber como es el árbol para este archivo.
class CABECERA { unsigned char Buf[322]; unsigned int nIndice; public: CABECERA(){nIndice=0;} bool Bit(); void Bit(bool); unsigned char Byte(); void Byte(unsigned char); unsigned int Tamano(){return nIndice;} unsigned char *Buffer(){return Buf;} void Reset(){nIndice=0;} void Adelante(unsigned int nBits){nIndice+=nBits;} void Atras(unsigned int nBits){nIndice-=nBits;} };
Los métodos sobrecargados “Bit” sirven para leer o escribir un bit en el buffer. Los métodos sobrecargados “Byte” sirven para leer o escribir un byte en el buffer. El método “Tamano” devuelve el tamaño en bits del buffer. El método “Buffer” devuelve un puntero al Buffer. Reset pone a cero el contador. “Adelante” se mueve un bit hacia delante y “Atrás” se mueve un bit hacia atrás.
Clase HUFFMAN.
La clase principal, “HUFFMAN”, es la única que debe ser definida en nuestro programa compresor. Ésta se encargará de definir todas las otras e inclusive creará y manejará los archivos con solo pasarle el nombre. Esta es la definición de la clase:
class HUFFMAN { unsigned int lFrec[257]; HOJA *pUltima; CODIGO Caracter[257]; void UnoMas(unsigned char Cual){lFrec[Cual]++;} void CrearHojas(); void OrdenarHojas(); void CrearArbol(); void CrearCodigos(); public: HUFFMAN(); ~HUFFMAN(); bool Comprimir(char*); bool Descomprimir(char*); unsigned int Procesar(char*); };
Las variables que contiene la clase son:
- lFrec. Es un array que contiene la frecuencia con la que se repite cada valor.
- pUltima. Un puntero a la última hoja de nuestra alfombra. También será la raíz del árbol cuando sea creado.
- Caracter. Es un puntero a las estructuras que contienen el código que ahora representará a cada carácter.
El método “UnoMas” “avisa” que apareció una vez más dicho caracter. Los métodos “CrearHojas”, “OrdenarHojas”, “CrearArbol”, son obvios. El método “CrearCódigos” es llamado luego de la creación del árbol y lo que hace es crear los códigos para cada caracter de acuerdo a su ubicación en el árbol.
El método “Comprimir” recibe como argumento el nombre del archivo a comprimir. El método “Descomprimir” recibe como argumento el nombre del archivo a descomprimir. Y el método “Procesar” recibe como argumento un nombre de archivo, y él se encarga de ver si está comprimido o no. Si está comprimido lo descomprime y viceversa.
Programa.
Para implementar la clase HUFFMAN hice un programita que se utiliza de la siguiente manera: Uno arrastra un archivo con el ratón sobre el programita y lo suelta. Si el archivo está comprimido lo descomprimirá, y viceversa.
Este es el código:
#include "huffman.h" void main(int argc, char* argv[]) { HUFFMAN *Compresor; Compresor = new HUFFMAN(); if(argc > 1) Compresor->Procesar(argv[1]); delete Compresor; }
El algoritmo de huffman.
(ver la implementación del algoritmo de huffman en c++)
El algoritmo de Huffman es un algoritmo de compresión de información. Este algoritmo está basado en la idea de que algunos caracteres aparecen muchas más veces que otros. Es especialmente eficaz en archivos de texto, donde más de la mitad de los caracteres difícilmente aparezcan alguna vez. Y entre los caracteres que aparecen, hay algunos que aparecen mucho más que otros.
Cada caracter se almacena en una secuencia de 8 bits. Este algoritmo se encarga de asignar códigos más cortos a los caracteres que más se repiten, y códigos más largos a los que menos se repiten. De esta manera a cada caracter se le asigna una longitud que puede variar entre 1 y 255 bits.
¿Cómo se hace esto?
Mediante un árbol binario. Veamos un ejemplo.
Supongamos que en un archivo tenemos el texto: “mi mama me mima”. Este texto ocupa 120 bits (15 bytes). Lo que propone el algoritmo de Huffman es lo siguiente:
-
Contemos cuantas veces aparece cada letra: m(6), i(2), “espacio”(3), a(3), e(1) (De ahora en adelante llamemos “~” al “espacio” para hacer las cosas más faciles).
-
Ordenamos las letras por su frecuencia, de mayor a menor:
m(6)~(3)a(3)i(2)e(1) -
Sumamos las últimas dos “hojas”, y en su lugar ponemos un “nodo” que tendrá la frecuencia de las dos hojas sumadas (y hagamos esto sucesivamente).
m(6) ~(3) a(3) (3)// Sumamos.
/ \
i(2) e(1)
m(6) ~(3) (6)// Sumamos.
/ \
a(3) (3)
/ \
i(2) e(1)
m(6) (6) ~(3)// Reordenamos por frecuencia.
/ \
a(3) (3)
/ \
i(2) e(1)
m(6) (9)// Sumamos.
/ \
(6) ~(3)
/ \
a(3) (3)
/ \
i(2) e(1)
(15)// Reordenamos y sumamos.
/ \
(9) m(6)
/ \
(6) ~(3)
/ \
a(3) (3)
/ \
i(2) e(1)
-
Ahora debemos crear una convención. En este ejemplo, convengamos: “0” a la izquierda y “1” a la derecha. De esta manera debemos recorrer el árbol hasta las hojas para crear los códigos de los caracteres. Por ejemplo, el carácter “i” está a: izquierda-izquierda-derecha-izquierda. Esto equivale a: 0010. Podemos hacer lo mismo con los otros, y obtendríamos estos códigos:
m = 1.
~ = 01.
a = 000.
i = 0010.
e = 0011.
-
Y ahora nos resta leer el archivo y por cada caracter leído escribir su correspondiente código en el archivo de salida. Para hacerlo más simple para nuestro análisis humano pondremos un punto entre cada código, pero en el archivo lo escribiremos todo junto. En el caso de “mi mama me mima”, tendríamos un archivo de salida así:
1.0010.01.1.000.1.000.01.1.0011.01.1.0010.1.000.
Esto suma un total de 33 bits. Mucho menos que el archivo original de 120 bits.
¿No habrá ambigüedades?
Ahora, como el lector sabe que en el archivo no escribiremos los puntos, se estará preguntando: ¿Y que pasa si al leer la información comprimida imagino los puntos en otras ubicaciones, que voy a interpretar?.
Hagamos la prueba, no le pongamos ningún punto: 100100110001000011001101100101000.
Pero recordemos seguir esta regla: Teniendo el árbol “a mano” situémonos en el nodo principal y vayamos leyendo la información. Cada vez que leamos un bit, movámonos al nodo inferior que esté a la derecha o a la izquierda según indique el bit. Cuando nos encontremos con que nos movimos a una hoja en vez de a un nodo, escribamos el carácter de la hoja, movámonos al principio del árbol y sigamos leyendo bit por bit desde donde nos habíamos quedado. Repitamos este proceso hasta el último bit.
Esto es lo que leeremos para nuestro ejemplo:
- Derecha (hoja). Ponemos la m. Volvemos arriba.
- Izquierda-izquierda-derecha-izquierda (hoja). Ponemos la i. Volvemos arriba.
- Izquierda-derecha (hoja). Ponemos ~. Volvemos arriba.
- Etc…
Al final habremos formado: mi mama me mima. Y no habrá posibilidades de formar otra frase con ese árbol y esa secuencia de bits. Haga algunos intentos y quedará convencido de que es así.
Debemos notar que para cada archivo habrá un árbol diferente de acuerdo a las frecuencias de los caracteres en ese archivo en particular, y una secuencia de bits diferente de acuerdo a la ubicación de los caracteres.
Ahora el lector habrá notado que el descompresor abre el archivo comprimido y “ve” la secuencia de bits, pero se estará preguntando ¿cómo sabe el descompresor cual es el árbol de ese archivo? ¡Claro, habíamos dicho que para cada archivo hay un árbol y una secuencia de bits diferentes! Así que el descompresor también deberá conocer el árbol.
Guardando el árbol.
Veamos una manera sencilla de guardar el árbol, aunque no es tan sencillo explicarlo.
Para guardar la secuencia de bits nosotros sabíamos si estábamos en un nodo o en una hoja, y lo que anotábamos era la dirección hacia la que nos movíamos.
Ahora hagamos justamente lo opuesto. Recorramos el árbol en una dirección (secuencia) conocida y anotemos si estamos en un nodo o en una hoja, y si estamos en una hoja anotemos su caracter.
Para eso convengamos esta regla: Cada nodo/hoja al ser llamado anotará un 1 si es una hoja y un 0 si es un nodo. Luego si es una hoja anotará los 8 bits que representan el caracter de esa hoja. Y si es un nodo, llamará al nodo/hoja de la izquierda y luego al de la derecha para que hagan lo mismo (recursivamente). Por último, después de hacer todo lo que tiene que hacer, devolverá “el mando” al nodo que lo llamó.
De esta forma nuestro árbol de ejemplo (más abajo) quedaría guardado así:
- (15) dice: Soy nodo, escribo 0. Llamo a nodo (9)
- (9) dice: Soy nodo, escribo 0. Llamo a nodo (6).
- (6) dice: Soy nodo, escribo 0. Llamo a hoja a(3).
- a(3) dice: Soy hoja, escribo 1. Escribo mi código: 01100001. Retorno a (6).
- (6) dice: Ahora llamo a nodo (3).
- (3) dice: Soy nodo, escribo 0. Llamo a hoja i(2).
- i(2) dice: Soy hoja, escribo 1. Escribo mi código: 01101001. Retorno a (3).
- (3) dice: Ahora llamo a hoja e(1).
- e(1) dice: Soy hoja, escribo 1. Escribo mi código: 01100101. Retorno a (3).
- (3) dice: Retorno a (6).
- (6) dice: Retorno a (9).
- (9) dice: Ahora llamo a hoja ~(3).
- ~(3) dice: Soy hoja, escribo 1. Escribo mi código: 00100000. Retorno a (9).
- (9) dice: Retorno a (15).
- (15) dice: Ahora llamo a hoja m(6).
- m(6) dice: Soy hoja, escribo 1. Escribo mi código: 01101101. Retorno a (15).
- (15) dice: Terminamos (retorno a quien sea que haya preguntado el código del árbol).
Árbol:
(15)
/ \
(9) m(6)
/ \
(6) ~(3)
/ \
a(3) (3)
/ \
i(2) e(1)
Tamaño de la descripción del árbol.
El código que se acaba de generar sería el siguiente:
0001011000010101101001101100101100100000101101101 (49 bits).
Éste código debe ir antes que la secuencia de bits del archivo para que el descompresor pueda armar el árbol antes de leer la secuencia de bits. En total el archivo generado tendrá 82 bits. Esto equivale a 10,25 bytes. Pero como no podemos guardar medio byte, tendremos que redondear a 11 bytes. Así un archivo de 15 bytes quedó reducido a 11 bytes.
Note el lector que casi el 60% del archivo comprimido está ocupado por la descripción del árbol. Ya que una descripción de árbol varía entre los 0 bits, en caso de un archivo vacío, y los 2559 bits (320 bytes), en caso de que un caracter se repita más que todos los otros juntos, y que el siguiente que más se repite se repita más que todos los otros que se repiten menos que él juntos y así sucesivamente, vemos que la descripción del árbol ocupará a lo sumo 320 bytes.
Esto es prácticamente insignificante para archivos de varios KB, por lo tanto el porcentaje de compresión va a ser mayor que para este ejemplo ya que aquí más del 59,75% del archivo es la pura descripción del árbol, (en este caso es muy significante).
Leyendo la descripción del árbol.
Para descomprimir el archivo basta armar el árbol a medida que vamos leyendo su descripción. Dejémoslo como tarea para el lector… Está bien, hagámoslo juntos. En la descripción leemos:
0: Dibujamos un nodo.
( )
/ \
0: Dibujamos otro nodo.
( )
/ \
( )
/ \
0: Dibujamos otro nodo.
( )
/ \
( )
/ \
( )
/ \
1: Dibujamos una hoja y leemos los 8 bits de su código (01100001=a).
( )
/ \
( )
/ \
( )
/ \
a( )
Nos movemos al próximo lugar vacío y leemos: 0: dibujamos un nodo.
( )
/ \
( )
/ \
( )
/ \
a( ) ( )
1: Dibujamos una hoja y leemos los 8 bits de su código (01101001=i).
( )
/ \
( )
/ \
( )
/ \
a( ) ( )
/ \
i( )
1: Dibujamos una hoja y leemos los 8 bits de su código (01100101=e).
( )
/ \
( )
/ \
( )
/ \
a( ) ( )
/ \
i( ) e( )
1: Dibujamos una hoja y leemos los 8 bits de su código (00100000=~).
( )
/ \
( )
/ \
( ) ~( )
/ \
a( ) ( )
/ \
i( ) e( )
1: Dibujamos una hoja y leemos los 8 bits de su código (01101101=m).
( )
/ \
( ) m( )
/ \
( ) ~( )
/ \
a( ) ( )
/ \
i( ) e( )
El nodo principal devuelve el control al que lo llamó. Y podemos ver que esto ocurre justamente cuando se terminan los bits. No hay ambigüedades.
Esto es todo.
Bueno, con esta información ya somos capaces de comprimir y descomprimir archivos mediante el algoritmo de Huffman. Ahora veremos como implementar el algoritmo de huffman en c++.
Método circuital o de las corrientes de mallas con matlab.
Comparto un script de matlab que hice para resolver circuitos en AC mediante el método de las corrientes de malla o método circuital (ver también método nodal).
Por ejemplo, para resolver el siguiente circuito:
Habría que ejecutar lo siguiente en matlab (muestro en negrita lo ingresado, el resto es generado por el script):
>> mallas
MÉTODO DE LAS MALLAS EN EL DOMINIO DE LAPLACE.
---------------------------------------------------------------------
¿Cuantas mallas tiene el circuito?: 3
¿Cuantos dígitos de precisión quiere ver en el resultado?: 3
---------------------------------------------------------------------
MATRIZ DE IMPEDANCIAS.
A continuación ingrese los elementos de la matriz de impedancias en el
dominio de Laplace utilizando "s" como variable generalizada de Laplace.
***Sepa que debe ingresar las coimpedancias con su SIGNO CORRESPONDIENTE**
Ingrese z[1,1]: 6
Ingrese z[1,2]: -2
Ingrese z[1,3]: -2
Ingrese z[2,2]: 6
Ingrese z[2,3]: -2
Ingrese z[3,3]: 6
Así quedó la matriz de impedancias:
[ 6, -2, -2]
[ -2, 6, -2]
[ -2, -2, 6]
¿Está bien?(S/N): s
---------------------------------------------------------------------
MATRIZ DE TENSIONES.
Ingrese V[1]: 10/s
Ingrese V[2]: 0
Ingrese V[3]: 0
Así quedó la matriz de Tensiones:
10/s
0
0
¿Está bien?(S/N): s
---------------------------------------------------------------------
DETERMINANTE PRINCIPAL
El determinante principal (Dp) es:
128
---------------------------------------------------------------------
PARA ENCONTRAR i1(t).
La matriz que origina el determinante sustituto 1 (Ds1) es:
[ 10/s, -2, -2]
[ 0, 6, -2]
[ 0, -2, 6]
El Ds1 es:
320
---
s
Ds1/Dp:
5
---
2 s
Expresado en fracciones parciales:
5
---
2 s
Antitransformando tenemos i1(t):
5/2
Expresado i1(t) con formato punto decimal:
2.5
---------------------------------------------------------------------
PARA ENCONTRAR i2(t).
La matriz que origina el determinante sustituto 2 (Ds2) es:
[ 6, 10/s, -2]
[ -2, 0, -2]
[ -2, 0, 6]
El Ds2 es:
160
---
s
Ds2/Dp:
5
---
4 s
Expresado en fracciones parciales:
5
---
4 s
Antitransformando tenemos i2(t):
5/4
Expresado i2(t) con formato punto decimal:
1.25
---------------------------------------------------------------------
PARA ENCONTRAR i3(t).
La matriz que origina el determinante sustituto 3 (Ds3) es:
[ 6, -2, 10/s]
[ -2, 6, 0]
[ -2, -2, 0]
El Ds3 es:
160
---
s
Ds3/Dp:
5
---
4 s
Expresado en fracciones parciales:
5
---
4 s
Antitransformando tenemos i3(t):
5/4
Expresado i3(t) con formato punto decimal:
1.25
Método nodal en matlab
Comparto un script de matlab que hice para resolver circuitos en AC mediante el método nodal (ver también método de mallas).
Por ejemplo, para resolver el siguiente circuito:
Habría que ejecutar lo siguiente en matlab (muestro en negrita lo ingresado, el resto es generado por el script):
>> nudos
MÉTODO DE LOS NUDOS EN EL DOMINIO DE LAPLACE.
---------------------------------------------------------------------
¿Cuantos nudos tiene el circuito?: 4
¿Cuantos dígitos de precisión quiere ver en el resultado?: 5
---------------------------------------------------------------------
MATRIZ DE ADMITANCIAS.
A continuación ingrese los elementos de la matriz de admitancias en el
dominio de Laplace utilizando "s" como variable generalizada de Laplace.
***Sepa que debe ingresar las coadmitancias con su SIGNO CORRESPONDIENTE**
Ingrese y[1,1]: 1/0.5+1+1/0.5
Ingrese y[1,2]: -1/0.5
Ingrese y[1,3]: 0
Ingrese y[1,4]: -1
Ingrese y[2,2]: 1/0.5+1+1/0.5
Ingrese y[2,3]: -1/0.5
Ingrese y[2,4]: -1
Ingrese y[3,3]: 1/0.5+1+1/0.5
Ingrese y[3,4]: -1
Ingrese y[4,4]: 1+1+1+1
Así quedó la matriz de admitancias:
[ 5, -2, 0, -1]
[ -2, 5, -2, -1]
[ 0, -2, 5, -1]
[ -1, -1, -1, 4]
¿Está bien?(S/N): s
---------------------------------------------------------------------
MATRIZ DE CORRIENTES.
Ingrese I[1]: -2/s
Ingrese I[2]: -1/s
Ingrese I[3]: 2/s+2/s
Ingrese I[4]: 1/s-2/s
Así quedó la matriz de Corrientes:
-2/s
-1/s
4/s
-1/s
¿Está bien?(S/N): s
---------------------------------------------------------------------
DETERMINANTE PRINCIPAL
El determinante principal (Dp) es:
225
---------------------------------------------------------------------
PARA ENCONTRAR v1(t).
La matriz que origina el determinante sustituto 1 (Ds1) es:
[ -2/s, -2, 0, -1]
[ -1/s, 5, -2, -1]
[ 4/s, -2, 5, -1]
[ -1/s, -1, -1, 4]
El Ds1 es:
120
- ---
s
Ds1/Dp:
8
- ----
15 s
Expresado en fracciones parciales:
8
- ----
15 s
Antitransformando tenemos v1(t):
-8/15
Expresado v1(t) con formato punto decimal:
-0.53333
---------------------------------------------------------------------
PARA ENCONTRAR v2(t).
La matriz que origina el determinante sustituto 2 (Ds2) es:
[ 5, -2/s, 0, -1]
[ -2, -1/s, -2, -1]
[ 0, 4/s, 5, -1]
[ -1, -1/s, -1, 4]
El Ds2 es:
45
- --
s
Ds2/Dp:
1
- ---
5 s
Expresado en fracciones parciales:
1
- ---
5 s
Antitransformando tenemos v2(t):
-1/5
Expresado v2(t) con formato punto decimal:
-0.2
---------------------------------------------------------------------
PARA ENCONTRAR v3(t).
La matriz que origina el determinante sustituto 3 (Ds3) es:
[ 5, -2, -2/s, -1]
[ -2, 5, -1/s, -1]
[ 0, -2, 4/s, -1]
[ -1, -1, -1/s, 4]
El Ds3 es:
150
---
s
Ds3/Dp:
2
---
3 s
Expresado en fracciones parciales:
2
---
3 s
Antitransformando tenemos v3(t):
2/3
Expresado v3(t) con formato punto decimal:
0.66667
---------------------------------------------------------------------
PARA ENCONTRAR v4(t).
La matriz que origina el determinante sustituto 4 (Ds4) es:
[ 5, -2, 0, -2/s]
[ -2, 5, -2, -1/s]
[ 0, -2, 5, 4/s]
[ -1, -1, -1, -1/s]
El Ds4 es:
60
- --
s
Ds4/Dp:
4
- ----
15 s
Expresado en fracciones parciales:
4
- ----
15 s
Antitransformando tenemos v4(t):
-4/15
Expresado v4(t) con formato punto decimal:
-0.26667
Función de Transferencia con Matlab
El siguiente script para matlab grafica los diagramas de Bode, Nyquist y Polar para una función de transferencia dada.
Por ejemplo, si ejecutamos el script y ponemos 1/(p^2+3*p+1) como función de transferencia:
>> diagramas
T(s)=1/(p^2+3*p+1)
Un nombre para el ejercicio: ejemplo
El script genera un archivo html que dice lo siguiente:
Informe de la Función de transferencia (ejemplo)
El script de matlab guarda una imagen, así que puede ser estudiado como ejemplo para hacer eso y otras cosas interesantes, como crear una función de transferencia a partir de una función simbólica en matlab.
Programación defensiva en C++.
post está basado en el libro "Thinking in C++ - Volume Two" de Bruce Eckel y Chuck Allison.
A medida que un programa va creciendo en tamaño y complejidad, se hace cada vez más difícil rastrear los errores a través del código. Peor todavía con los errores que no saltan a simple vista.
Una de las ventajas de la programación modular es que, al dividir un problema en muchos problemas mas pequeños, si cada parte funciona bien, todo funciona bien. Y es más fácil hacer que una pequeña parte funcione bien, cada vez que se diseña una, que diseñar todo un programa enorme y tratar de que funcione bien.
Entonces vamos a ver algunas técnicas para ir asegurándonos que cada parte de nuestro programa funcione bien a medida que lo vamos haciendo. Así, cuando unamos todas las partes, el programa entero va a funcionar bien.
Aserciones.
Un algoritmo es, entre otras cosas, una expresión de nuestro intento por resolver un problema. Éste debería dejar en claro al lector (inclusive el escritor mismo) exactamente qué se estaba pensando cuando se diseñó esa porción de código así. En ciertos puntos del programa, se deberían poder hacer ciertas aserciones o aseveraciones.
Algunas ventajas[1]:
- Hace que, lo que de otra forma hubieras puesto como comentario, sea verificado en tiempo de ejecución para ver si realmente es así.
- Te permite expresar en el código lo que vos considerás como verdadero en un cierto punto de ejecución.
- Si no se cumple inmediatamente termina el programa.
- Probablemente ya hayas escrito comentarios en tu código. ¿Porqué no convertirlo en aserciones y hacer tu código más robusto?
- Podés estar seguro de que, si el código llegó ahí, todo lo que habías asumido como verdadero hasta ese punto se cumplió.
- No hacen, en absoluto, el código más lento (una vez compilado en release). Sólo existen para compilaciones "debug". Para "release" desaparecen.
Un programa sin aserciones se vería así:
#include <iostream> #include <algorithm> int main() { int v[]={0,1,2,3,4,5,6,7,8,9}; int tam=sizeof v / sizeof *v; int min=*std::min_element(v,v+tam); int max=*std::max_element(v,v+tam); std::cout<<"Min: "<<min<<std::endl; std::cout<<"Max: "<<max; return 0; }
Uno con aserciones sería:
#include <iostream> #include <algorithm> #include <cassert> int main() { int v[]={0,1,2,3,4,5,6,7,8,9}; int tam=sizeof v / sizeof *v; assert(tam==10); int min=*std::min_element(v,v+tam); assert(min==0); int max=*std::max_element(v,v+tam); assert(max==9); std::cout<<"Min: "<<min<<std::endl; std::cout<<"Max: "<<max; return 0; }
Cuando escribí este ejemplo, me confundí en varias cosas. Por ejemplo, al principio supuse "sizeof v" como 10, cuando en realidad era 40 ya que cada int me ocupaba 4 bytes. Saltó el assert.
También puse "assert(max==10)". Otra vez saltó, porque distraído no me dí cuenta que aunque el tamaño era 10, el mayor elemento era 9.
Como verás, es muy útil para ayudar al programador. Llená tu código de aserciones. Por ejemplo antes de evaluar la raiz cuadrada de un número, verificá que sea >=0. O antes de dividir por x verificá que "assert(x!=0). Te va a ahorrar dolores de cabeza.
La sintaxis de assert es:
void assert (int expression);
Está definida en la cabecera "<cassert>".
Para la versión final de tu programa, luego de haber probado que anda todo bien, eliminá automáticamente todas aserciones definiendo, antes de la inclusión de <cassert>, lo siguiente:
#define NDEBUG
La definición de assert, en <cassert> es equivalente a esta:
#ifdef NDEBUG #define assert(cond) ((void)0) #else void assertImpl(const char*, const char*,long); #define assert(cond)\ ((cond)?(void)0:assertImpl(???)) #endif
Estructura Automatizada de pruebas (Automated Test Framework).
Muchas veces los programadores, luego de haber construido una función, la probamos llamándola con algunos valores y fijándonos que nos retorna.
Esto es tedioso y muy propenso a errores. Las máquinas lo hacen mejor que los humanos. Entonces ¿porqué no automatizar el proceso?
El libro Thinking In C++ - Volume 2: Practical Programming presenta "la unidad de test automatizado más simple que pueda funcionar".
El código lo podés descargar de acá o copiarlo del final del post.
Uso[2]:
A continuación pongo como un ejemplo un programa que pasa de numeros decimales a romanos (El framwork está en el espacio de nombres "TestSuite").
#include <iostream> #include <string> #include "Test.h" std::string ARomano(int Decimal ) { static char *unidades[] = // Unidades de 0 a 9 { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" }; static char *decenas[] = // Decenas de 0 a 90 { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }; static char *centenas[] = // Centenas de 0 a 900 { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }; static char *millares[] = // Millares de 0 a 3000 { "", "M", "MM", "MMM" }; return std::string(millares[ (Decimal / 1000) ]) + std::string(centenas[ (Decimal / 100) % 10 ]) + std::string(decenas[ (Decimal / 10) % 10 ]) + std::string(unidades[ (Decimal) % 10 ]); } // Para probar la función de arriba creamos una clase, derivada de Test, que pruebe algunos valores. class TestARomano : public TestSuite::Test { public: void run() { test_(ARomano(1)=="I"); test_(ARomano(5)=="V"); test_(ARomano(13)=="XIII"); test_(ARomano(99)=="XCIX"); test_(ARomano(444)=="CDXLIV"); test_(ARomano(720)=="DCCXX"); test_(ARomano(2803)=="MMDCCCIII"); test_(ARomano(3888)=="MMMDCCCLXXXVIII"); test_(ARomano(3999)=="MMMCMXCIX"); } }; int main() { int n; TestARomano mitest; // Instancio la clase. mitest.run(); // Pruebo si hubieron errors. assert(mitest.report()==0); // Muestro los resultados. No tienen que haber habido errores. std::cout<<std::endl<<"Ingrese numeros en decimal entre 1 y 3999 para transformarlos en romanos. Ingrese <1 o >3999 para salir."<<std::endl; do { std::cout<<"Decimal: "; std::cin>>n; if((n<=0)||(n>3999)) break; std::cout<<"Romano: "<<ARomano(n)<<std::endl; }while(1); return 0; }
La salida del programa es la siguiente:
Test "class TestARomano":
Passed: 9 Failed: 0
Ingrese numeros en decimal entre 1 y 3999 para transformarlos en romanos. Ingres
e <1 o >3999 para salir.
Decimal: 453
Romano: CDLIII
Decimal: 43
Romano: XLIII
Decimal: 0
Un ejemplo donde probamos más de una función se muestra a continuación. Para eso utilizamos el framework, para integrar los diferentes tests.
#include <iostream> #include <string> #include "Test.h" #include "Suite.h" // Funciones "tontas" para mostrar el uso del framework. int suma(int a,int b){return a+b;} int resta(int a,int b){return a-b;} int multiplicacion(int a,int b){return a*b;} int division(int a,int b){return a/b;} // Probamos. class TestSuma : public TestSuite::Test { public: void run() { test_(suma(1,1)==2); test_(suma(2,1)==3); test_(suma(1,2)==3); test_(suma(2,5)==7); test_(suma(100,29)==129); test_(suma(5,1)>5); test_(suma(1,3)<5); } }; class TestResta : public TestSuite::Test { public: void run() { test_(resta(1,1)==0); test_(resta(2,1)==1); test_(resta(1,2)==-1); test_(resta(2,5)==-3); test_(resta(100,29)==71); test_(resta(5,1)>3); test_(resta(1,3)<1); } }; class TestMultiplicacion : public TestSuite::Test { public: void run() { test_(multiplicacion(1,1)==1); test_(multiplicacion(2,1)==2); test_(multiplicacion(1,2)==2); test_(multiplicacion(2,5)==10); test_(multiplicacion(100,29)==2900); test_(multiplicacion(5,1)>4); test_(multiplicacion(1,3)<4); } }; class TestDivision : public TestSuite::Test { public: void run() { test_(multiplicacion(1,1)==1); test_(multiplicacion(2,1)==2); test_(multiplicacion(1,2)==0); test_(multiplicacion(2,5)==0); test_(multiplicacion(100,29)==3); test_(multiplicacion(5,1)>4); test_(multiplicacion(1,3)<1); } }; int main() { TestSuite::Suite basicas("Operaciones basicas"); basicas.addTest(new TestSuma); basicas.addTest(new TestResta); basicas.addTest(new TestMultiplicacion); basicas.addTest(new TestDivision); basicas.run(); std::cout<<std::endl<<"Fallos: "<<basicas.report(); basicas.free(); // Le digo que los punteros estaban en el heap y que los borre. return 0; }
La salida del ejemplo anterior es:
class TestDivisionfailure: (multiplicacion(1,2)==0) , c:\documents and settings\
daniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (lin
e 65)
class TestDivisionfailure: (multiplicacion(2,5)==0) , c:\documents and settings\
daniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (lin
e 66)
class TestDivisionfailure: (multiplicacion(100,29)==3) , c:\documents and settin
gs\daniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (
line 67)
class TestDivisionfailure: (multiplicacion(1,3)<1) , c:\documents and settings\d
aniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (line
69)
Suite "Operaciones basicas"
===========================
Test "class TestSuma":
Passed: 7 Failed: 0
Test "class TestResta":
Passed: 7 Failed: 0
Test "class TestMultiplicacion":
Passed: 7 Failed: 0
Test "class TestDivision":
Passed: 3 Failed: 4
===========================
Fallos: 4
Claramente se puede ver cuales fueron los fallos. Me olvidé de cambiar "multiplicación" por " división en el test de división (porque copié y pegué el código.
El siguiente código ya funciona bien:
#include <iostream> #include <string> #include "Test.h" #include "Suite.h" // Funciones "tontas" para mostrar el uso del framework. int suma(int a,int b){return a+b;} int resta(int a,int b){return a-b;} int multiplicacion(int a,int b){return a*b;} int division(int a,int b){return a/b;} // Probamos. class TestSuma : public TestSuite::Test { public: void run() { test_(suma(1,1)==2); test_(suma(2,1)==3); test_(suma(1,2)==3); test_(suma(2,5)==7); test_(suma(100,29)==129); test_(suma(5,1)>5); test_(suma(1,3)<5); } }; class TestResta : public TestSuite::Test { public: void run() { test_(resta(1,1)==0); test_(resta(2,1)==1); test_(resta(1,2)==-1); test_(resta(2,5)==-3); test_(resta(100,29)==71); test_(resta(5,1)>3); test_(resta(1,3)<1); } }; class TestMultiplicacion : public TestSuite::Test { public: void run() { test_(multiplicacion(1,1)==1); test_(multiplicacion(2,1)==2); test_(multiplicacion(1,2)==2); test_(multiplicacion(2,5)==10); test_(multiplicacion(100,29)==2900); test_(multiplicacion(5,1)>4); test_(multiplicacion(1,3)<4); } }; class TestDivision : public TestSuite::Test { public: void run() { test_(division(1,1)==1); test_(division(2,1)==2); test_(division(1,2)==0); test_(division(2,5)==0); test_(division(100,29)==3); test_(division(5,1)>4); test_(division(1,3)<1); } }; int main() { TestSuite::Suite basicas("Operaciones basicas"); basicas.addTest(new TestSuma); basicas.addTest(new TestResta); basicas.addTest(new TestMultiplicacion); basicas.addTest(new TestDivision); basicas.run(); std::cout<<std::endl<<"Fallos: "<<basicas.report(); basicas.free(); // Le digo que los punteros estaban en el heap y que los borre. return 0; }
La salida es:
Suite "Operaciones basicas"
===========================
Test "class TestSuma":
Passed: 7 Failed: 0
Test "class TestResta":
Passed: 7 Failed: 0
Test "class TestMultiplicacion":
Passed: 7 Failed: 0
Test "class TestDivision":
Passed: 7 Failed: 0
===========================
Fallos: 0
En el libro online hay un ejemplo más completo[2]. Pero esto ya nos sirve para empezar a trabajar con pruebas automáticas.
A continuación el código del framework:
Test.h:
//: TestSuite:Test.h // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #ifndef TEST_H #define TEST_H #include <string> #include <iostream> #include <cassert> using std::string; using std::ostream; using std::cout; // fail_() has an underscore to prevent collision with // ios::fail(). For consistency, test_() and succeed_() // also have underscores. #define test_(cond) \ do_test(cond, #cond, __FILE__, __LINE__) #define fail_(str) \ do_fail(str, __FILE__, __LINE__) namespace TestSuite { class Test { ostream* osptr; long nPass; long nFail; // Disallowed: Test(const Test&); Test& operator=(const Test&); protected: void do_test(bool cond, const string& lbl, const char* fname, long lineno); void do_fail(const string& lbl, const char* fname, long lineno); public: Test(ostream* osptr = &cout) { this->osptr = osptr; nPass = nFail = 0; } virtual ~Test() {} virtual void run() = 0; long getNumPassed() const { return nPass; } long getNumFailed() const { return nFail; } const ostream* getStream() const { return osptr; } void setStream(ostream* osptr) { this->osptr = osptr; } void succeed_() { ++nPass; } long report() const; virtual void reset() { nPass = nFail = 0; } }; } // namespace TestSuite #endif // TEST_H ///:~
Test.cpp:
//: TestSuite:Test.cpp {O} // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #include "Test.h" #include <iostream> #include <typeinfo> using namespace std; using namespace TestSuite; void Test::do_test(bool cond, const std::string& lbl, const char* fname, long lineno) { if(!cond) do_fail(lbl, fname, lineno); else succeed_(); } void Test::do_fail(const std::string& lbl, const char* fname, long lineno) { ++nFail; if(osptr) { *osptr << typeid(*this).name() << "failure: (" << lbl << ") , " << fname << " (line " << lineno << ")" << endl; } } long Test::report() const { if(osptr) { *osptr << "Test \"" << typeid(*this).name() << "\":\n\tPassed: " << nPass << "\tFailed: " << nFail << endl; } return nFail; } ///:~
Suite.h:
//: TestSuite:Suite.h // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #ifndef SUITE_H #define SUITE_H #include <vector> #include <stdexcept> #include "Test.h" using std::vector; using std::logic_error; namespace TestSuite { class TestSuiteError : public logic_error { public: TestSuiteError(const string& s = "") : logic_error(s) {} }; class Suite { string name; ostream* osptr; vector<Test*> tests; void reset(); // Disallowed ops: Suite(const Suite&); Suite& operator=(const Suite&); public: Suite(const string& name, ostream* osptr = &cout) : name(name) { this->osptr = osptr; } string getName() const { return name; } long getNumPassed() const; long getNumFailed() const; const ostream* getStream() const { return osptr; } void setStream(ostream* osptr) { this->osptr = osptr; } void addTest(Test* t) throw(TestSuiteError); void addSuite(const Suite&); void run(); // Calls Test::run() repeatedly long report() const; void free(); // Deletes tests }; } // namespace TestSuite #endif // SUITE_H ///:~
Suite.cpp:
//: TestSuite:Suite.cpp {O} // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #include "Suite.h" #include <iostream> #include <cassert> #include <cstddef> using namespace std; using namespace TestSuite; void Suite::addTest(Test* t) throw(TestSuiteError) { // Verify test is valid and has a stream: if(t == 0) throw TestSuiteError("Null test in Suite::addTest"); else if(osptr && !t->getStream()) t->setStream(osptr); tests.push_back(t); t->reset(); } void Suite::addSuite(const Suite& s) { for(size_t i = 0; i < s.tests.size(); ++i) { assert(tests[i]); addTest(s.tests[i]); } } void Suite::free() { for(size_t i = 0; i < tests.size(); ++i) { delete tests[i]; tests[i] = 0; } } void Suite::run() { reset(); for(size_t i = 0; i < tests.size(); ++i) { assert(tests[i]); tests[i]->run(); } } long Suite::report() const { if(osptr) { long totFail = 0; *osptr << "Suite \"" << name << "\"\n======="; size_t i; for(i = 0; i < name.size(); ++i) *osptr << '='; *osptr << "=" << endl; for(i = 0; i < tests.size(); ++i) { assert(tests[i]); totFail += tests[i]->report(); } *osptr << "======="; for(i = 0; i < name.size(); ++i) *osptr << '='; *osptr << "=" << endl; return totFail; } else return getNumFailed(); } long Suite::getNumPassed() const { long totPass = 0; for(size_t i = 0; i < tests.size(); ++i) { assert(tests[i]); totPass += tests[i]->getNumPassed(); } return totPass; } long Suite::getNumFailed() const { long totFail = 0; for(size_t i = 0; i < tests.size(); ++i) { assert(tests[i]); totFail += tests[i]->getNumFailed(); } return totFail; } void Suite::reset() { for(size_t i = 0; i < tests.size(); ++i) { assert(tests[i]); tests[i]->reset(); } } ///:~
FOOTNOTES
1. The benefits of programming with assertions.↑
2. Para más detalles consultar el título "A simple unit test framework", en el libro online. (en inglés)↑
2. post está basado en el libro "Thinking in C++ - Volume Two" de Bruce Eckel y Chuck Allison.
A medida que un programa va creciendo en tamaño y complejidad, se hace cada vez más difícil rastrear los errores a través del código. Peor todavía con los errores que no saltan a simple vista.
Una de las ventajas de la programación modular es que, al dividir un problema en muchos problemas mas pequeños, si cada parte funciona bien, todo funciona bien. Y es más fácil hacer que una pequeña parte funcione bien, cada vez que se diseña una, que diseñar todo un programa enorme y tratar de que funcione bien.
Entonces vamos a ver algunas técnicas para ir asegurándonos que cada parte de nuestro programa funcione bien a medida que lo vamos haciendo. Así, cuando unamos todas las partes, el programa entero va a funcionar bien.
Aserciones.
Un algoritmo es, entre otras cosas, una expresión de nuestro intento por resolver un problema. Éste debería dejar en claro al lector (inclusive el escritor mismo) exactamente qué se estaba pensando cuando se diseñó esa porción de código así. En ciertos puntos del programa, se deberían poder hacer ciertas aserciones o aseveraciones.
Algunas ventajas[1]:
- Hace que, lo que de otra forma hubieras puesto como comentario, sea verificado en tiempo de ejecución para ver si realmente es así.
- Te permite expresar en el código lo que vos considerás como verdadero en un cierto punto de ejecución.
- Si no se cumple inmediatamente termina el programa.
- Probablemente ya hayas escrito comentarios en tu código. ¿Porqué no convertirlo en aserciones y hacer tu código más robusto?
- Podés estar seguro de que, si el código llegó ahí, todo lo que habías asumido como verdadero hasta ese punto se cumplió.
- No hacen, en absoluto, el código más lento (una vez compilado en release). Sólo existen para compilaciones "debug". Para "release" desaparecen.
Un programa sin aserciones se vería así:
#include <iostream> #include <algorithm> int main() { int v[]={0,1,2,3,4,5,6,7,8,9}; int tam=sizeof v / sizeof *v; int min=*std::min_element(v,v+tam); int max=*std::max_element(v,v+tam); std::cout<<"Min: "<<min<<std::endl; std::cout<<"Max: "<<max; return 0; }
Uno con aserciones sería:
#include <iostream> #include <algorithm> #include <cassert> int main() { int v[]={0,1,2,3,4,5,6,7,8,9}; int tam=sizeof v / sizeof *v; assert(tam==10); int min=*std::min_element(v,v+tam); assert(min==0); int max=*std::max_element(v,v+tam); assert(max==9); std::cout<<"Min: "<<min<<std::endl; std::cout<<"Max: "<<max; return 0; }
Cuando escribí este ejemplo, me confundí en varias cosas. Por ejemplo, al principio supuse "sizeof v" como 10, cuando en realidad era 40 ya que cada int me ocupaba 4 bytes. Saltó el assert.
También puse "assert(max==10)". Otra vez saltó, porque distraído no me dí cuenta que aunque el tamaño era 10, el mayor elemento era 9.
Como verás, es muy útil para ayudar al programador. Llená tu código de aserciones. Por ejemplo antes de evaluar la raiz cuadrada de un número, verificá que sea >=0. O antes de dividir por x verificá que "assert(x!=0). Te va a ahorrar dolores de cabeza.
La sintaxis de assert es:
void assert (int expression);
Está definida en la cabecera "<cassert>".
Para la versión final de tu programa, luego de haber probado que anda todo bien, eliminá automáticamente todas aserciones definiendo, antes de la inclusión de <cassert>, lo siguiente:
#define NDEBUG
La definición de assert, en <cassert> es equivalente a esta:
#ifdef NDEBUG #define assert(cond) ((void)0) #else void assertImpl(const char*, const char*,long); #define assert(cond)\ ((cond)?(void)0:assertImpl(???)) #endif
Estructura Automatizada de pruebas (Automated Test Framework).
Muchas veces los programadores, luego de haber construido una función, la probamos llamándola con algunos valores y fijándonos que nos retorna.
Esto es tedioso y muy propenso a errores. Las máquinas lo hacen mejor que los humanos. Entonces ¿porqué no automatizar el proceso?
El libro Thinking In C++ - Volume 2: Practical Programming presenta "la unidad de test automatizado más simple que pueda funcionar".
El código lo podés descargar de acá o copiarlo del final del post.
Uso[2]:
A continuación pongo como un ejemplo un programa que pasa de numeros decimales a romanos (El framwork está en el espacio de nombres "TestSuite").
#include <iostream> #include <string> #include "Test.h" std::string ARomano(int Decimal ) { static char *unidades[] = // Unidades de 0 a 9 { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" }; static char *decenas[] = // Decenas de 0 a 90 { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }; static char *centenas[] = // Centenas de 0 a 900 { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }; static char *millares[] = // Millares de 0 a 3000 { "", "M", "MM", "MMM" }; return std::string(millares[ (Decimal / 1000) ]) + std::string(centenas[ (Decimal / 100) % 10 ]) + std::string(decenas[ (Decimal / 10) % 10 ]) + std::string(unidades[ (Decimal) % 10 ]); } // Para probar la función de arriba creamos una clase, derivada de Test, que pruebe algunos valores. class TestARomano : public TestSuite::Test { public: void run() { test_(ARomano(1)=="I"); test_(ARomano(5)=="V"); test_(ARomano(13)=="XIII"); test_(ARomano(99)=="XCIX"); test_(ARomano(444)=="CDXLIV"); test_(ARomano(720)=="DCCXX"); test_(ARomano(2803)=="MMDCCCIII"); test_(ARomano(3888)=="MMMDCCCLXXXVIII"); test_(ARomano(3999)=="MMMCMXCIX"); } }; int main() { int n; TestARomano mitest; // Instancio la clase. mitest.run(); // Pruebo si hubieron errors. assert(mitest.report()==0); // Muestro los resultados. No tienen que haber habido errores. std::cout<<std::endl<<"Ingrese numeros en decimal entre 1 y 3999 para transformarlos en romanos. Ingrese <1 o >3999 para salir."<<std::endl; do { std::cout<<"Decimal: "; std::cin>>n; if((n<=0)||(n>3999)) break; std::cout<<"Romano: "<<ARomano(n)<<std::endl; }while(1); return 0; }
La salida del programa es la siguiente:
Test "class TestARomano":
Passed: 9 Failed: 0
Ingrese numeros en decimal entre 1 y 3999 para transformarlos en romanos. Ingres
e <1 o >3999 para salir.
Decimal: 453
Romano: CDLIII
Decimal: 43
Romano: XLIII
Decimal: 0
Un ejemplo donde probamos más de una función se muestra a continuación. Para eso utilizamos el framework, para integrar los diferentes tests.
#include <iostream> #include <string> #include "Test.h" #include "Suite.h" // Funciones "tontas" para mostrar el uso del framework. int suma(int a,int b){return a+b;} int resta(int a,int b){return a-b;} int multiplicacion(int a,int b){return a*b;} int division(int a,int b){return a/b;} // Probamos. class TestSuma : public TestSuite::Test { public: void run() { test_(suma(1,1)==2); test_(suma(2,1)==3); test_(suma(1,2)==3); test_(suma(2,5)==7); test_(suma(100,29)==129); test_(suma(5,1)>5); test_(suma(1,3)<5); } }; class TestResta : public TestSuite::Test { public: void run() { test_(resta(1,1)==0); test_(resta(2,1)==1); test_(resta(1,2)==-1); test_(resta(2,5)==-3); test_(resta(100,29)==71); test_(resta(5,1)>3); test_(resta(1,3)<1); } }; class TestMultiplicacion : public TestSuite::Test { public: void run() { test_(multiplicacion(1,1)==1); test_(multiplicacion(2,1)==2); test_(multiplicacion(1,2)==2); test_(multiplicacion(2,5)==10); test_(multiplicacion(100,29)==2900); test_(multiplicacion(5,1)>4); test_(multiplicacion(1,3)<4); } }; class TestDivision : public TestSuite::Test { public: void run() { test_(multiplicacion(1,1)==1); test_(multiplicacion(2,1)==2); test_(multiplicacion(1,2)==0); test_(multiplicacion(2,5)==0); test_(multiplicacion(100,29)==3); test_(multiplicacion(5,1)>4); test_(multiplicacion(1,3)<1); } }; int main() { TestSuite::Suite basicas("Operaciones basicas"); basicas.addTest(new TestSuma); basicas.addTest(new TestResta); basicas.addTest(new TestMultiplicacion); basicas.addTest(new TestDivision); basicas.run(); std::cout<<std::endl<<"Fallos: "<<basicas.report(); basicas.free(); // Le digo que los punteros estaban en el heap y que los borre. return 0; }
La salida del ejemplo anterior es:
class TestDivisionfailure: (multiplicacion(1,2)==0) , c:\documents and settings\
daniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (lin
e 65)
class TestDivisionfailure: (multiplicacion(2,5)==0) , c:\documents and settings\
daniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (lin
e 66)
class TestDivisionfailure: (multiplicacion(100,29)==3) , c:\documents and settin
gs\daniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (
line 67)
class TestDivisionfailure: (multiplicacion(1,3)<1) , c:\documents and settings\d
aniel\mis documentos\visual studio 2008\projects\romano\romano\romanos.cpp (line
69)
Suite "Operaciones basicas"
===========================
Test "class TestSuma":
Passed: 7 Failed: 0
Test "class TestResta":
Passed: 7 Failed: 0
Test "class TestMultiplicacion":
Passed: 7 Failed: 0
Test "class TestDivision":
Passed: 3 Failed: 4
===========================
Fallos: 4
Claramente se puede ver cuales fueron los fallos. Me olvidé de cambiar "multiplicación" por " división en el test de división (porque copié y pegué el código.
El siguiente código ya funciona bien:
#include <iostream> #include <string> #include "Test.h" #include "Suite.h" // Funciones "tontas" para mostrar el uso del framework. int suma(int a,int b){return a+b;} int resta(int a,int b){return a-b;} int multiplicacion(int a,int b){return a*b;} int division(int a,int b){return a/b;} // Probamos. class TestSuma : public TestSuite::Test { public: void run() { test_(suma(1,1)==2); test_(suma(2,1)==3); test_(suma(1,2)==3); test_(suma(2,5)==7); test_(suma(100,29)==129); test_(suma(5,1)>5); test_(suma(1,3)<5); } }; class TestResta : public TestSuite::Test { public: void run() { test_(resta(1,1)==0); test_(resta(2,1)==1); test_(resta(1,2)==-1); test_(resta(2,5)==-3); test_(resta(100,29)==71); test_(resta(5,1)>3); test_(resta(1,3)<1); } }; class TestMultiplicacion : public TestSuite::Test { public: void run() { test_(multiplicacion(1,1)==1); test_(multiplicacion(2,1)==2); test_(multiplicacion(1,2)==2); test_(multiplicacion(2,5)==10); test_(multiplicacion(100,29)==2900); test_(multiplicacion(5,1)>4); test_(multiplicacion(1,3)<4); } }; class TestDivision : public TestSuite::Test { public: void run() { test_(division(1,1)==1); test_(division(2,1)==2); test_(division(1,2)==0); test_(division(2,5)==0); test_(division(100,29)==3); test_(division(5,1)>4); test_(division(1,3)<1); } }; int main() { TestSuite::Suite basicas("Operaciones basicas"); basicas.addTest(new TestSuma); basicas.addTest(new TestResta); basicas.addTest(new TestMultiplicacion); basicas.addTest(new TestDivision); basicas.run(); std::cout<<std::endl<<"Fallos: "<<basicas.report(); basicas.free(); // Le digo que los punteros estaban en el heap y que los borre. return 0; }
La salida es:
Suite "Operaciones basicas"
===========================
Test "class TestSuma":
Passed: 7 Failed: 0
Test "class TestResta":
Passed: 7 Failed: 0
Test "class TestMultiplicacion":
Passed: 7 Failed: 0
Test "class TestDivision":
Passed: 7 Failed: 0
===========================
Fallos: 0
En el libro online hay un ejemplo más completo[2]. Pero esto ya nos sirve para empezar a trabajar con pruebas automáticas.
A continuación el código del framework:
Test.h:
//: TestSuite:Test.h // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #ifndef TEST_H #define TEST_H #include <string> #include <iostream> #include <cassert> using std::string; using std::ostream; using std::cout; // fail_() has an underscore to prevent collision with // ios::fail(). For consistency, test_() and succeed_() // also have underscores. #define test_(cond) \ do_test(cond, #cond, __FILE__, __LINE__) #define fail_(str) \ do_fail(str, __FILE__, __LINE__) namespace TestSuite { class Test { ostream* osptr; long nPass; long nFail; // Disallowed: Test(const Test&); Test& operator=(const Test&); protected: void do_test(bool cond, const string& lbl, const char* fname, long lineno); void do_fail(const string& lbl, const char* fname, long lineno); public: Test(ostream* osptr = &cout) { this->osptr = osptr; nPass = nFail = 0; } virtual ~Test() {} virtual void run() = 0; long getNumPassed() const { return nPass; } long getNumFailed() const { return nFail; } const ostream* getStream() const { return osptr; } void setStream(ostream* osptr) { this->osptr = osptr; } void succeed_() { ++nPass; } long report() const; virtual void reset() { nPass = nFail = 0; } }; } // namespace TestSuite #endif // TEST_H ///:~
Test.cpp:
//: TestSuite:Test.cpp {O} // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #include "Test.h" #include <iostream> #include <typeinfo> using namespace std; using namespace TestSuite; void Test::do_test(bool cond, const std::string& lbl, const char* fname, long lineno) { if(!cond) do_fail(lbl, fname, lineno); else succeed_(); } void Test::do_fail(const std::string& lbl, const char* fname, long lineno) { ++nFail; if(osptr) { *osptr << typeid(*this).name() << "failure: (" << lbl << ") , " << fname << " (line " << lineno << ")" << endl; } } long Test::report() const { if(osptr) { *osptr << "Test \"" << typeid(*this).name() << "\":\n\tPassed: " << nPass << "\tFailed: " << nFail << endl; } return nFail; } ///:~
Suite.h:
//: TestSuite:Suite.h // From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison. // (c) 1995-2004 MindView, Inc. All Rights Reserved. // See source code use permissions stated in the file 'License.txt', // distributed with the code package available at www.MindView.net. #ifndef SUITE_H #define SUITE_H #include <vector> #include <stdexcept> #include "Test.h" using std::vector; using std::logic_error; namespace TestSuite { class TestSuiteError : public logic_error { public: TestSuiteError(const string& s = "") : logic_error(s) {} }; class Suite { string name; ostream* osptr; vector<Test*> tests; void reset(); // Disallowed ops: Suite(const Suite&); Suite& operator=(const Suite&); public: Suite(const string& name, ostream* osptr = &cout) : name(name) { this->osptr = osptr; } string getName() const { return name; } long getNumPassed() const; long getNumFailed() const; const ostream* getStream() const { return osptr; } void setStream(ostream* osptr) { this->osptr = osptr; } void addTest(Test* t) throw(TestSuiteError); void addSuite(const Suite&); void run(); // Calls Test::run() repeatedly long report() const; void free(); // Deletes tests }; } // namespace TestSuite #endif // SUITE_H ///:~
Suite.cpp:
//: TestSuite:Suite.cpp {O}
// From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison.
// (c) 1995-2004 MindView, Inc. All Rights Reserved.
// See source code use permissions stated in the file 'License.txt',
// distributed with the code package available at www.MindView.net.
#include "Suite.h"
#include <iostream>
#include <cassert>
#include <cstddef>
using namespace std;
using namespace TestSuite;void Suite::addTest(Test* t) throw(TestSuiteError) {
// Verify test is valid and has a stream:
if(t == 0)
throw TestSuiteError("Null test in Suite::addTest");
else if(osptr && !t->getStream())
t->setStream(osptr);
tests.push_back(t);
t->reset();
}void Suite::addSuite(const Suite& s) {
for(size_t i = 0; i < s.tests.size(); ++i) {
assert(tests[i]);
addTest(s.tests[i]);
}
}void Suite::free() {
for(size_t i = 0; i < tests.size(); ++i) {
delete tests[i];
tests[i] = 0;
}
}void Suite::run() {
reset();
for(size_t i = 0; i < tests.size(); ++i) {
assert(tests[i]);
tests[i]->run();
}
}long Suite::report() const {
if(osptr) {
long totFail = 0;
*osptr << "Suite \"" << name
<< "\"\n=======";
size_t i;
for(i = 0; i < name.size(); ++i)
*osptr << '=';
*osptr << "=" << endl;
for(i = 0; i < tests.size(); ++i) {
assert(tests[i]);
totFail += tests[i]->report();
}
*osptr << "=======";
for(i = 0; i < name.size(); ++i)
*osptr << '=';
*osptr << "=" << endl;
return totFail;
}
else
return getNumFailed();
}long Suite::getNumPassed() const {
long totPass = 0;
for(size_t i = 0; i < tests.size(); ++i) {
assert(tests[i]);
totPass += tests[i]->getNumPassed();
}
return totPass;
}long Suite::getNumFailed() const {
long totFail = 0;
for(size_t i = 0; i < tests.size(); ++i) {
assert(tests[i]);
totFail += tests[i]->getNumFailed();
}
return totFail;
}void Suite::reset() {
for(size_t i = 0; i < tests.size(); ++i) {
assert(tests[i]);
tests[i]->reset();
}
} ///:~<↑
Compresión de datos mediante algoritmo de Huffman.
Hace unos años hice como trabajo para la materia de informática II un programita en lenguaje c++ que comprime archivos mediante el algoritmo de huffman.
Para compartirlo, a modo de tutorial, lo dividí en dos partes:
- La explicación del algoritmo de Huffman.
- La implementación del algoritmo de Huffman en c++.
El programa no está optimizado para ejecutarse rápido, sino para que sea fácil de entender el concepto del algoritmo.
Para utilizarlo, una vez compilado, se debe arrastrar un archivo a comprimir y soltarlo sobre el ejecutable. Por ejemplo, si arrastramos uno de los archivos fuentes: "huffman.cpp" (8.702 bytes), se crea un nuevo archivo llamado "huffman.cpp.hfm" (6.191 bytes).
Si en cambio se arrastra y se suelta sobre el ejecutable un archivo con extensión ".hfm", el programa entiende que debe descomprimirlo. Por ejemplo arrastrando el archivo "huffman.cpp.hfm" sobre el ejecutable, éste vuelve a crear el archivo "huffman.cpp" original.
Buscar en el sitio.
Buscar en la web.
Suscribirme a nuevos posts.
Categorías
- Economía (2)
- Filosofía (1)
- HP 50g (4)
- Ingeniería en Electrónica (1)
- Internet (5)
- LabView (20)
- Problemas y soluciones (10)
- Programación (7)
- Teología (2)
- Uncategorized (1)
Entradas recientes
- Nokia X3: WiFi dice “enlace no disponible” (Solución)
- Cómo migrar contactos de Nokia a Android (en Windows 7)
- Error 80070003 en Windows Update al tratar de instalar KB2539636 KB2533523 KB2468871
- Arreglé el aire acondicionado split
- Rayas verticales en el LCD de la Notebook
- Cartel de Texto Pasante en LabVIEW – Matriz de LEDs
- LabVIEW: InPort.vi y OutPort.vi en Windows Vista y Windows 7
- Consultas y trabajos en LabVIEW
- Huffman en c++.
- El algoritmo de huffman.
- Cambiar nivel crítico de bateria en Windows 7
- Método circuital o de las corrientes de mallas con matlab.
- Método nodal en matlab
- Función de Transferencia con Matlab
- HyperTerminal en Windows 7 o Windows Vista.