La mayoria de los lenguajes de programacion implementan tablas de hash en alguna de sus variantes (Hashtable, HashMap en Java o Hastable en C#). Un problema asociado a esta funcionalidad, es la correcta implementacion de las funciones para generar el codigo el codigo de hash de la llave, que sirve para obtener el valor asociado a la misma dentro de la tabla de hash.
Como se vio en el post hashCode y equals funcion en Java o GetHashCode y Equals en C#, una tabla de hash, se puede comparar con un diccionario. Dado que la funcion que obtiene el codigo hash de un objeto (GetHashCode para C# y hashCode para Java) puede obtener el valor entre -231 y +231 y si el codigo de hash, es unico, entonces, este codigo puede fungir como una "llave" adicional, sobre todo, si se define correctamente y se implementa una funcion que genere este codigo lo mas rapido posible.
Los tiempos de respuesta y uso de memoria de una tabla de hash, dependen de como se implemente, asi como de una correcta definicion de la funcion que genere el codigo de hash. El secreto del desempeño de la tabla de hash, esta el uso de la aritmetica modular, utilizada para determinar que codigos de hash son similares.
Tanto en Java, como en C# el codigo de hash, esta representado por un numero entero de 32 bits (4 bytes), esto da la posibilidad de tener 232 (poco mas de 4 mil millones o millardos) posibles codigos de hash distintos. Como se vio en otro post, el codigo de hash, se emplea para "indexar" la informacion y realizar una busqueda ejecutando el menor numero de comparaciones posibles.
Para ver como funciona comparemos ahora la tabla de hash con un hospital, el cual tiene un archivo, donde por cuestiones de orden, se colocan los expedientes en cajones. Existen 27 cajones (utilizaremos el alfabeto ingles, el cual no tiene ñ, ch, ni acentos, dieresis u otras letras, simbolos, acentos, etc) cada cajon almacena los expedientes correspondientes a la letra inicial del nombre de la persona.
Suponiendo que el hospital es nuevo (new Hospital()), los 27 cajones estan vacios. cuando llega el primer paciente, se le genera un nuevo expediente y cuando se da de alta, se almacena su expediente en el archivo, si el paciente se llama Ricardo, el cajon que tiene una letra R al frente tendra un unico expediente y los otros 26 expedientes, seguiran vacios.
Si llega un nuevo paciente, llamado Juan, lo ideal, es que se busque si no tiene un expediente, entonces, buscando en el cajon donde se almacenan los expedientes que inician con J, nos damos cuenta de que no tiene expediente y creamos uno nuevo, para posteriormente almacenarlo.
Pero, este hospital es un poco desordenado al momento de almacenar los archivos, pues cuando llega otra persona con cuyo nombre es Ramon, el nuevo expediente, simplemente se pone encima del anterior y cuando llega Rosa, ocurre lo mismo, es decir, dentro del cada cajon, los expedientes, no se ordenan. Esto provoca que cuando llega una persona llamada Romario, se deba buscar el nombre en 3 expedientes distintos, puesto que al no estar ordenados alfabeticamente, hay que comparar el nombre para verificar que no es el expediente buscado. Por lo que es ligeramente mas tardado el proceso de busqueda del expediente de una persona cuyo nombre inicia con R que si inicia con J o si inicia con cualquier otra letra del abecedario. Ya se atendio Romario y se le genero un expediente. Extrañamente, viene una persona que se llama Ruperto (si, ya se, muchas R), esto provoca que el cajon donde estan estos expedientes, comienze a desbordarse y la busqueda cada vez tarde mas.
Esto que estoy describiendo, ocurre, cuando la funcion que genera el codigo de hash (la letra inicial del nombre, en este caso) esta incorrectamente definida y todos o la mayoria de los elementos que estamos almacenando tengan el mismo codigo de hash.
Para evitar esta situacion, se suelen definir funciones, en ocasiones extrañamente complejas, imaginemos por un momento, que cambiase las reglas para almacenar la informacion, ahora tendre las mismas 27 cajas, pero para determinar el cajon donde se almacenara el expediente, se sumara el valor ASCII de cada letra del nombre de la persona, el resultado se multiplicara por 13 (un numero primo por cierto) y se realizara la operacion modulo 27, al resultado de este, se le sumara 1, el resultado de esto, se convertira a una letra, 1 por A, 2 por B ... y 27 por Z ... Despues de realizar todas estas operaciones , no duden que probablemente haya uno y solo un expediente por cajon, pero ahora la generacion del codigo de hash se volvio costosa en tiempo.
Ahora, que ocurre cuando se agregan mas letras al abecedario, por ejemplo acentos y dieresis, asi como la letra ñ, pero sin agregar cajones a nuestro sistema de almacenamiento. La solucion es buscar similitudes o equivalencias, por ejemplo n es parecida a la letra ñ y las letras acentuadas o con dieresis a las mismas sin el acento o la dieresis. Esto es buscar similitudes o equivalencias. Para realizar estas operaciones de "equivalencias" las tablas de hash, utilizan aritmetica modular, es decir, dado que el universo para la generacion del codigo de hash, es basto, se emplea este tipo de aritmetica, para determinar que codigos de hash son similares y almacenarlos conjuntamente.
jueves, 1 de julio de 2010
jueves, 3 de junio de 2010
operador +, cadenas, cadenas constante y el compilador en C#
Al igual que en java, el compilador de C# es capaz de realizar optimizaciones al momento de compilar el codigo y convertir una instruccion en otra, utilizando las funciones definidas en la clase String.
Como se vio en el post dedicado a java, es posible utilizar el compilador a nuestro favor, cuando se conoce como funciona.
En el siguiente ejemplo, se muestra una concatenacion, utilizando el operador +.
Al decompilar el codigo, empleando el comando ildasm, se obtiene el siguiente codigo:
El codigo que genera codigo similar es el siguiente:
Como es posible observar, el codigo generado ejecuta una funcion propia de la clase String, la cual sabe concatenar cadenas, generando una nueva cadena del tamaño necesario. Sin embargo, este comportamiento solo se presenta cuando se emplean 2, 3 y hasta 4 cadenas, ya cuando se trata de 5 o mas cadenas, primero construye un arreglo de cadenas, con las cadenas a concatenar y posteriormente emplea el metodo Concat(String[]). Por ejemplo:
Produciendo el siguiente codigo:
En cambio, el compilador de C# al igua que el de java, es capaz de detectar cadenas constantes "inline" y generar una cadena con el resultado en tiempo de compilacion, evitando el procesamiento en tiempo de ejecucion
Generando el siguiente codigo:
El compilador puede ayudar en el desempeño del sistema, al generar algunas de estas operaciones previamente.
Como se vio en el post dedicado a java, es posible utilizar el compilador a nuestro favor, cuando se conoce como funciona.
En el siguiente ejemplo, se muestra una concatenacion, utilizando el operador +.
01: using System; 02: using System.Collections.Generic; 03: using System.Linq; 04: using System.Text; 05: 06: namespace ClassLibrary1 07: { 08: public class Class1 09: { 10: void Test() 11: { 12: string a = "cadena1"; 13: string b = "cadena2"; 14: string x = a + b; 15: Console.WriteLine(x); 16: } 17: } 18: } 19:
Al decompilar el codigo, empleando el comando ildasm, se obtiene el siguiente codigo:
.method private hidebysig instance void Test() cil managed
{
// Code size 29 (0x1d)
.maxstack 2
.locals init ([0] string a,
[1] string b,
[2] string x)
IL_0000: nop
IL_0001: ldstr "cadena1"
IL_0006: stloc.0
IL_0007: ldstr "cadena2"
IL_000c: stloc.1
IL_000d: ldloc.0
IL_000e: ldloc.1
IL_000f: call string [mscorlib]System.String::Concat(string,
string)
IL_0014: stloc.2
IL_0015: ldloc.2
IL_0016: call void [mscorlib]System.Console::WriteLine(string)
IL_001b: nop
IL_001c: ret
} // end of method Class1::Test
El codigo que genera codigo similar es el siguiente:
01: using System; 02: using System.Collections.Generic; 03: using System.Linq; 04: using System.Text; 05: 06: namespace ClassLibrary1 07: { 08: public class Class2 09: { 10: void Test() 11: { 12: string x = String.Concat("cadena1","cadena2"); 13: Console.WriteLine(x); 14: } 15: } 16: } 17:
Como es posible observar, el codigo generado ejecuta una funcion propia de la clase String, la cual sabe concatenar cadenas, generando una nueva cadena del tamaño necesario. Sin embargo, este comportamiento solo se presenta cuando se emplean 2, 3 y hasta 4 cadenas, ya cuando se trata de 5 o mas cadenas, primero construye un arreglo de cadenas, con las cadenas a concatenar y posteriormente emplea el metodo Concat(String[]). Por ejemplo:
01: using System; 02: using System.Collections.Generic; 03: using System.Linq; 04: using System.Text; 05: 06: namespace ClassLibrary1 07: { 08: class Class3 09: { 10: void Test() 11: { 12: string a = "cadena1"; 13: string b = "cadena2"; 14: string c = "cadena3"; 15: string d = "cadena4"; 16: string e = "cadena5"; 17: string x = a + b + c + d + e; 18: Console.WriteLine(x); 19: } 20: } 21: } 22:
Produciendo el siguiente codigo:
.method private hidebysig instance void Test() cil managed
{
// Code size 84 (0x54)
.maxstack 3
.locals init ([0] string a,
[1] string b,
[2] string c,
[3] string d,
[4] string e,
[5] string x,
[6] string[] CS$0$0000)
IL_0000: nop
IL_0001: ldstr "cadena1"
IL_0006: stloc.0
IL_0007: ldstr "cadena2"
IL_000c: stloc.1
IL_000d: ldstr "cadena3"
IL_0012: stloc.2
IL_0013: ldstr "cadena4"
IL_0018: stloc.3
IL_0019: ldstr "cadena5"
IL_001e: stloc.s e
IL_0020: ldc.i4.5
IL_0021: newarr [mscorlib]System.String
IL_0026: stloc.s CS$0$0000
IL_0028: ldloc.s CS$0$0000
IL_002a: ldc.i4.0
IL_002b: ldloc.0
IL_002c: stelem.ref
IL_002d: ldloc.s CS$0$0000
IL_002f: ldc.i4.1
IL_0030: ldloc.1
IL_0031: stelem.ref
IL_0032: ldloc.s CS$0$0000
IL_0034: ldc.i4.2
IL_0035: ldloc.2
IL_0036: stelem.ref
IL_0037: ldloc.s CS$0$0000
IL_0039: ldc.i4.3
IL_003a: ldloc.3
IL_003b: stelem.ref
IL_003c: ldloc.s CS$0$0000
IL_003e: ldc.i4.4
IL_003f: ldloc.s e
IL_0041: stelem.ref
IL_0042: ldloc.s CS$0$0000
IL_0044: call string [mscorlib]System.String::Concat(string[])
IL_0049: stloc.s x
IL_004b: ldloc.s x
IL_004d: call void [mscorlib]System.Console::WriteLine(string)
IL_0052: nop
IL_0053: ret
} // end of method Class3::Test
En cambio, el compilador de C# al igua que el de java, es capaz de detectar cadenas constantes "inline" y generar una cadena con el resultado en tiempo de compilacion, evitando el procesamiento en tiempo de ejecucion
01: using System; 02: using System.Collections.Generic; 03: using System.Linq; 04: using System.Text; 05: 06: namespace ClassLibrary1 07: { 08: public class Class4 09: { 10: void Test() 11: { 12: string x = "cadena1" + "cadena2"; 13: Console.WriteLine(x); 14: } 15: } 16: } 17:
Generando el siguiente codigo:
.method private hidebysig instance void Test() cil managed
{
// Code size 15 (0xf)
.maxstack 1
.locals init ([0] string x)
IL_0000: nop
IL_0001: ldstr "cadena1cadena2"
IL_0006: stloc.0
IL_0007: ldloc.0
IL_0008: call void [mscorlib]System.Console::WriteLine(string)
IL_000d: nop
IL_000e: ret
} // end of method Class4::Test
El compilador puede ayudar en el desempeño del sistema, al generar algunas de estas operaciones previamente.
miércoles, 2 de junio de 2010
cadenas en java (strings)
En java, como en muchos lenguajes de programacion modernos, existe una clase que define la representacion interna de una cadena durante la ejecucion del programa. En java esta clase es String. Internamente, la clase String, esta representada por un arreglo del tipo nativo char. Derivado de esto, la maquina virtual de java, maneja las cadenas como un conjunto de caracteres codificados en Unicode en formato UTF-16 (No UTF-8, no ASCII). Una consecuencia es que cada caracter que conforma la cadena, utiliza 2 bytes.
Una situacion que se da debido a la restriccion de inmutabilidad, es que los constructores que reciben un arreglo de caracteres (char[]) deben generar un arreglo interno nuevo y copiar el original (total o parcialmente, segun sea el caso), dependiendo del constructor que se emplee.
En cambio, cuando se genera una cadena utilizando otra cadena como base, es posible compartir el arreglo internamente, pues la fuente inmutable por definicion. En algunas situaciones, se puede generar un nuevo arreglo interno, para evitar el uso de memoria.
Cuando se necesita extraer un caracter de una cadena, es preferible utilizar la funcion charAt, en vez de un substring. Dado que esta funcion regresa un valor directamente (el iesimo caracter en el arreglo) sin necesidad de crear objetos y utilizando exclusivamente el stack, en cambio substring crea un nuevo objeto String, que puede compartir la memoria empleada por la cadena original. Una prueba de esto, es ejecutar el siguiente codigo:
String s = "test";
long start = System.currentTimeMillis();
for (int i = 0; i < Integer.MAX_VALUE; i++) {
s.substring(0,1);
}
System.out.println(System.currentTimeMillis() - start);
Contra este codigo
String s = "test";
long start = System.currentTimeMillis();
for (int i = 0; i < Integer.MAX_VALUE; i++) {
s.charAt(0);
}
System.out.println(System.currentTimeMillis() - start);
El primer codigo, puede llegar a ejecutarse en unos cuantos milisegundos (30 aprox en un Centrino Duo a 1.83GHz), mientras que el segundo codigo se tarda mas de 200 veces mas tiempo (casi 1 minuto en el mismo procesador), particularmente, cuando se ejecuta la maquina virtual con la opcion -server, cuando se ejecuta con la opcion -client, los tiempos de ejecucion del primer ejemplo es de 1/3 con respecto al segundo ejemplo. Este codigo optimizado esta empleado en el post "Extraccion del nombre de una propiedad del getter respectivo en java".
La funcion concat, es optima cuando se emplea exclusivamene con 2 cadenas, pues se aloja exactamente la memoria necesaria para construir la nueva cadena, cuya longitud es la suma de ambas longitudes.
Una situacion que se da debido a la restriccion de inmutabilidad, es que los constructores que reciben un arreglo de caracteres (char[]) deben generar un arreglo interno nuevo y copiar el original (total o parcialmente, segun sea el caso), dependiendo del constructor que se emplee.
En cambio, cuando se genera una cadena utilizando otra cadena como base, es posible compartir el arreglo internamente, pues la fuente inmutable por definicion. En algunas situaciones, se puede generar un nuevo arreglo interno, para evitar el uso de memoria.
Cuando se necesita extraer un caracter de una cadena, es preferible utilizar la funcion charAt, en vez de un substring. Dado que esta funcion regresa un valor directamente (el iesimo caracter en el arreglo) sin necesidad de crear objetos y utilizando exclusivamente el stack, en cambio substring crea un nuevo objeto String, que puede compartir la memoria empleada por la cadena original. Una prueba de esto, es ejecutar el siguiente codigo:
String s = "test";
long start = System.currentTimeMillis();
for (int i = 0; i < Integer.MAX_VALUE; i++) {
s.substring(0,1);
}
System.out.println(System.currentTimeMillis() - start);
Contra este codigo
String s = "test";
long start = System.currentTimeMillis();
for (int i = 0; i < Integer.MAX_VALUE; i++) {
s.charAt(0);
}
System.out.println(System.currentTimeMillis() - start);
El primer codigo, puede llegar a ejecutarse en unos cuantos milisegundos (30 aprox en un Centrino Duo a 1.83GHz), mientras que el segundo codigo se tarda mas de 200 veces mas tiempo (casi 1 minuto en el mismo procesador), particularmente, cuando se ejecuta la maquina virtual con la opcion -server, cuando se ejecuta con la opcion -client, los tiempos de ejecucion del primer ejemplo es de 1/3 con respecto al segundo ejemplo. Este codigo optimizado esta empleado en el post "Extraccion del nombre de una propiedad del getter respectivo en java".
La funcion concat, es optima cuando se emplea exclusivamene con 2 cadenas, pues se aloja exactamente la memoria necesaria para construir la nueva cadena, cuya longitud es la suma de ambas longitudes.
viernes, 28 de mayo de 2010
numeros constantes y el operador + en java
Al igual que ocurre con las cadenas, el compilador, puede realizar calculos y utilizar el resultado, reemplazando una complicada operacion y minimizando el trabajo en tiempo de ejecucion. Esto resultando en menor uso de memoria y procesador. El ejemplo acontinuacion:
Explicacion
05-07: Un ejemplo de como definir el numero de segundos en una hora (60000), teniendo la posibilidad de definir el numero de horas, cuando sea necesario.
08-08: Realizando una operacion con punto flotante.
09-09: Ejemplo de una combinacion de constantes, con variables.
Explicacion
01: package test; 02: 03: public class NumberConstantTest { 04: public static void main(String[] args) { 05: int a = 1 // number or hours 06: * 60 // mins per hour 07: * 1000; // milliseconds per second 08: float b = (3.5f + 1.2f) / 2f; 09: double c = a * (1d / 3d); 10: System.out.println(a); 11: System.out.println(b); 12: System.out.println(c); 13: } 14: } 15:
Explicacion
05-07: Un ejemplo de como definir el numero de segundos en una hora (60000), teniendo la posibilidad de definir el numero de horas, cuando sea necesario.
08-08: Realizando una operacion con punto flotante.
09-09: Ejemplo de una combinacion de constantes, con variables.
Compiled from "NumberConstantTest.java"
public class test.NumberConstantTest extends java.lang.Object{
public test.NumberConstantTest();
Code:
0: aload_0
1: invokespecial #8; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: ldc #16; //int 60000
2: istore_1
3: ldc #17; //float 2.35f
5: fstore_2
6: iload_1
7: i2d
8: ldc2_w #18; //double 0.3333333333333333d
11: dmul
12: dstore_3
13: getstatic #20; //Field java/lang/System.out:Ljava/io/PrintStream;
16: iload_1
17: invokevirtual #26; //Method java/io/PrintStream.println:(I)V
20: getstatic #20; //Field java/lang/System.out:Ljava/io/PrintStream;
23: fload_2
24: invokevirtual #32; //Method java/io/PrintStream.println:(F)V
27: getstatic #20; //Field java/lang/System.out:Ljava/io/PrintStream;
30: dload_3
31: invokevirtual #35; //Method java/io/PrintStream.println:(D)V
34: return
}Explicacion
- En codigo resultante, despues de ejecutar la decompilacion, utilizando el comando "javap -c" se puede apreciar que el compilador calculo los valores y coloco los resultados donde aplica, sin embargo, cuando se trata de combinaciones de constantes, con variables (incluso siendo constantes), no se optimizas y se realiza la operacion.
miércoles, 26 de mayo de 2010
generics en C#, implementando GetHashCode, Equals y Comparable
A continuacion, la manera de utilizar generics en C#, para implementar las funciones GetHashCode y Equals, asi como la implementacion de IComparable. Este ejemplo es equivalente al ejemplo de java
Explicacion:
06-06: Declaracion de utilizacion del uso de generics
08-08: Declaracion del id.
10-20: Declaracion de los accesors para el id.
21-24: Definicion de la funcion GetHashCode, empleando las funciones propias del atributo id.
25-38: Definicion de multiples funciones Equals.
41-42: Declaracion del uso de IComparable
44-47: Definicion de la funcion CompareTo
Optimizacion:
01: using System; 02: using System.Collections.Generic; 03: 04: namespace Test 05: { 06: public abstract class GenericClass<T> 07: { 08: internal T id; 09: 10: public T Id 11: { 12: get 13: { 14: return id; 15: } 16: set 17: { 18: id = value; 19: } 20: } 21: public override int GetHashCode() 22: { 23: return id.GetHashCode(); 24: } 25: public override bool Equals(object obj) 26: { 27: return this == obj 28: || (((object)(id as GenericClass<T>) == null) 29: && Equals0((GenericClass<T>)obj)); 30: } 31: public bool Equals(GenericClass<T> obj) 32: { 33: return this == obj || Equals0(obj); 34: } 35: private bool Equals0(GenericClass<T> obj) 36: { 37: return id.Equals(obj.id); 38: } 39: } 40: 41: public abstract class GenericClassComparable<T> : GenericClass<T>, 42: IComparable<GenericClassComparable<T>> where T : IComparable<T> 43: { 44: public int CompareTo(GenericClassComparable<T> o) 45: { 46: return id.CompareTo(o.id); 47: } 48: } 49: } 50:
Explicacion:
06-06: Declaracion de utilizacion del uso de generics
08-08: Declaracion del id.
10-20: Declaracion de los accesors para el id.
21-24: Definicion de la funcion GetHashCode, empleando las funciones propias del atributo id.
25-38: Definicion de multiples funciones Equals.
41-42: Declaracion del uso de IComparable
44-47: Definicion de la funcion CompareTo
Optimizacion:
- El uso de esta clase, permite utilizar automaticamente las funciones Sort y BinarySearch, de la clase Array, asi como la clase Hashtable
viernes, 21 de mayo de 2010
hashCode y equals funcion en Java o GetHashCode y Equals en C#
¿Cual es la relacion de las funciones que obtienen el codigo hash de un objeto, la funcion que determina la igualdad entre 2 objetos?
La respuesta, la dan las tablas de hash o hashtables en ingles. Para explicar el funcionamiento de estas empleare una analogia con los diccionarios (los libros). Un diccionario es un conjunto de palabras con su respectivo significado y las tablas de hash, son un conjunto de llaves asociadas con un valor. Comparando el diccionario con la tabla de hash, las llaves son las palabras y los significados, son los valores.
Para explicar el funcionamiento de la tabla de hash en terminos del diccionario, explicare primero la organizacion de este ultimo.
Comparado con una tabla de hash, el codigo hash se emplea de la misma manera que nosotros empleamos la primer letra de la palabra a buscar en el diccionario, es decir, se emplea, para determinar un rango de busqueda y posteriormente se emplea la funcion que determina igualdad, para determinar la misma. Cabe aclarar que es importante, tanto para la busqueda en el diccionario, como la busqueda en la tabla de hash, que el algoritmo para generar el codigo hash debe ser eficiente (minimizar el tiempo de respuesta), ademas de que dado un valor, siempre debe regresar el mismo codigo.
Con respecto a la funcion equals, se utiliza para saber cual llave del conjunto (o palabra en caso del diccionario) tiene el valor (definicion en el diccionario) que estamos buscando.
Derivado de esto, se observa, que como en la vida real, tanto la funcion para obtener el codigo hash como la funcion para validad la igualdad, deben tener tiempos de respuesta minimos, particularmente la de igualdad, dado que es la que mas se emplea cuando se busca.
Nota: No es mi intencion ahondar en el funcionamiento de las tablas de hash, dado que existen multiples referencias a su funcionamiento en internet e implica conocimiento sobre teoria de colisiones, algunas formulas y conceptos matematicos, estructuras de datos y por supuesto las variantes de cada lenguaje de programacion. En la wikipedia, asi como en las materias relacionadas con estructuras de datos de muchas carreras relacionadas a sistemas se explica ampliamente su funcionamiento e implementacion.
Si lo muesto en este blog, es precisamente por la importancia que tiene definir correctamente las funciones y que ademas, sean eficazes y eficientes (optimas), pues el uso de tablas de hash esta amplamente extendido.
En java existen 2 clases que se emplean ampliamente Hashtable y HashMap. En C# la clase que se emplea normalmente es Hashtable.
Actualmente solo he implementado esta funcionalidad en java, en estas entradas:
La respuesta, la dan las tablas de hash o hashtables en ingles. Para explicar el funcionamiento de estas empleare una analogia con los diccionarios (los libros). Un diccionario es un conjunto de palabras con su respectivo significado y las tablas de hash, son un conjunto de llaves asociadas con un valor. Comparando el diccionario con la tabla de hash, las llaves son las palabras y los significados, son los valores.
Para explicar el funcionamiento de la tabla de hash en terminos del diccionario, explicare primero la organizacion de este ultimo.
- Las palabras estan ordenadas en orden alfabetico estricto
- Las palabras que inician con la misma letra, estan agrupadas bajo esa letra, existiendo un indice de letras (este puede ser un indice o una serie de marcas en la orilla del mismo)
Comparado con una tabla de hash, el codigo hash se emplea de la misma manera que nosotros empleamos la primer letra de la palabra a buscar en el diccionario, es decir, se emplea, para determinar un rango de busqueda y posteriormente se emplea la funcion que determina igualdad, para determinar la misma. Cabe aclarar que es importante, tanto para la busqueda en el diccionario, como la busqueda en la tabla de hash, que el algoritmo para generar el codigo hash debe ser eficiente (minimizar el tiempo de respuesta), ademas de que dado un valor, siempre debe regresar el mismo codigo.
Con respecto a la funcion equals, se utiliza para saber cual llave del conjunto (o palabra en caso del diccionario) tiene el valor (definicion en el diccionario) que estamos buscando.
Derivado de esto, se observa, que como en la vida real, tanto la funcion para obtener el codigo hash como la funcion para validad la igualdad, deben tener tiempos de respuesta minimos, particularmente la de igualdad, dado que es la que mas se emplea cuando se busca.
Nota: No es mi intencion ahondar en el funcionamiento de las tablas de hash, dado que existen multiples referencias a su funcionamiento en internet e implica conocimiento sobre teoria de colisiones, algunas formulas y conceptos matematicos, estructuras de datos y por supuesto las variantes de cada lenguaje de programacion. En la wikipedia, asi como en las materias relacionadas con estructuras de datos de muchas carreras relacionadas a sistemas se explica ampliamente su funcionamiento e implementacion.
Si lo muesto en este blog, es precisamente por la importancia que tiene definir correctamente las funciones y que ademas, sean eficazes y eficientes (optimas), pues el uso de tablas de hash esta amplamente extendido.
En java existen 2 clases que se emplean ampliamente Hashtable y HashMap. En C# la clase que se emplea normalmente es Hashtable.
Actualmente solo he implementado esta funcionalidad en java, en estas entradas:
- implementando las funciones hashCode y equals en java
- implementando las funciones hashCode y equals con generics en java
operador +=, cadenas, cadenas constante y el compilador en Java
Como se vio en la entrada anterior, el utilizar incorrectamente un operador, puede ser optimizado por el compilador o en su defecto, una instruccion (en apariencia) se puede convertir en un conjunto de instrucciones, que impacta negarivamente en el desempeño del sistema.
El operador += es un ejemplo de operador que nunca se debe utilizar, debido a como esta implementado, veamos este codigo.
Si de compilamos el codigo java resultante (el archivo .class) con el comando "javap -c", obtenemos lo siguiente:
El codigo equivalente, para generar el mismo resultado, pero utilizando explicitamente la clase StringBuilder y la funcion valueOf, es el siguiente:
Pero que ocurre cuando se mete la operacion += dentro de un loop? Como en el siguiente codigo:
Al decompilar, se genera el siguiente codigo:
Es decir, el codigo equivalente es el siguiente:
Como se puede observar, en cada iteracion, se construye un nuevo objeto StringBuilder, con el resultado de ejecutar la funcion valueOf, que recibe como parametro la variable x, posterior mente, se agrega la cadena que "cadena2" y finalmente, se convierte en una cadena nueva, la cual se asigna a la variable x.
Derivado de esto es destacable notar que este codigo es ineficiente, en la mayoria de las situaciones, particularmente cuando se emplea dentro de loops.
Sin embargo, cuando se emplea en conjunto con el operador +, puede eficiente, pero solo si se conoce exactamente la cantidad de elemenos implicados en la operacion. Como en el siguiente ejemplo:
Al de compilar se obtiene lo siguiente:
El codigo equivalente, es el siguiente:
Lo cual es eficiente para en terminos de uso de los objetos creados.
El operador += es un ejemplo de operador que nunca se debe utilizar, debido a como esta implementado, veamos este codigo.
1: package test; 2: 3: public class StringTest { 4: public static void main(String[] args) { 5: String x = "cadena1"; 6: x += "cadena2"; 7: System.out.println(x); 8: } 9: } 10:
Si de compilamos el codigo java resultante (el archivo .class) con el comando "javap -c", obtenemos lo siguiente:
Compiled from "StringTest.java"
public class test.StringTest extends java.lang.Object{
public test.StringTest();
Code:
0: aload_0
1: invokespecial #8; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: ldc #16; //String cadena1
2: astore_1
3: new #18; //class java/lang/StringBuilder
6: dup
7: aload_1
8: invokestatic #20; //Method java/lang/String.valueOf:(Ljava/lang/Object;)Ljava/lang/String;
11: invokespecial #26; //Method java/lang/StringBuilder."<init>":(Ljava/lang/String;)V
14: ldc #29; //String cadena2
16: invokevirtual #31; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
19: invokevirtual #35; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
22: astore_1
23: getstatic #39; //Field java/lang/System.out:Ljava/io/PrintStream;
26: aload_1
27: invokevirtual #45; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
30: return
}
El codigo equivalente, para generar el mismo resultado, pero utilizando explicitamente la clase StringBuilder y la funcion valueOf, es el siguiente:
1: package test; 2: 3: public class StringTest2 { 4: public static void main(String[] args) { 5: String x = "cadena1"; 6: x = new StringBuilder(String.valueOf(x)).append("cadena2").toString(); 7: System.out.println(x); 8: } 9: } 10:
Pero que ocurre cuando se mete la operacion += dentro de un loop? Como en el siguiente codigo:
01: package test; 02: 03: public class StringTest3 { 04: public static void main(String[] args) { 05: String x = "cadena1"; 06: for (int i = 0; i < 10; i++) { 07: x += "cadena2"; 08: } 09: } 10: } 11:
Al decompilar, se genera el siguiente codigo:
Compiled from "StringTest3.java"
public class test.StringTest3 extends java.lang.Object{
public test.StringTest3();
Code:
0: aload_0
1: invokespecial #8; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: ldc #16; //String cadena1
2: astore_1
3: iconst_0
4: istore_2
5: goto 31
8: new #18; //class java/lang/StringBuilder
11: dup
12: aload_1
13: invokestatic #20; //Method java/lang/String.valueOf:(Ljava/lang/Object;)Ljava/lang/String;
16: invokespecial #26; //Method java/lang/StringBuilder."<init>":(Ljava/lang/String;)V
19: ldc #29; //String cadena2
21: invokevirtual #31; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
24: invokevirtual #35; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
27: astore_1
28: iinc 2, 1
31: iload_2
32: bipush 10
34: if_icmplt 8
37: return
}
Es decir, el codigo equivalente es el siguiente:
01: package test; 02: 03: public class StringTest4 { 04: public static void main(String[] args) { 05: String x = "cadena1"; 06: for (int i = 0; i < 10; i++) { 07: x = new StringBuilder(String.valueOf(x)).append("cadena2").toString(); 08: } 09: } 10: } 11:
Como se puede observar, en cada iteracion, se construye un nuevo objeto StringBuilder, con el resultado de ejecutar la funcion valueOf, que recibe como parametro la variable x, posterior mente, se agrega la cadena que "cadena2" y finalmente, se convierte en una cadena nueva, la cual se asigna a la variable x.
Derivado de esto es destacable notar que este codigo es ineficiente, en la mayoria de las situaciones, particularmente cuando se emplea dentro de loops.
Sin embargo, cuando se emplea en conjunto con el operador +, puede eficiente, pero solo si se conoce exactamente la cantidad de elemenos implicados en la operacion. Como en el siguiente ejemplo:
01: package test; 02: 03: public class StringTest5 { 04: public static void main(String[] args) { 05: String x = "cadena1"; 06: String y = "auxiliar"; 07: x += "cadena2" + y; 08: System.out.println(x); 09: } 10: } 11:
Al de compilar se obtiene lo siguiente:
Compiled from "StringTest5.java"
public class test.StringTest5 extends java.lang.Object{
public test.StringTest5();
Code:
0: aload_0
1: invokespecial #8; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: ldc #16; //String cadena1
2: astore_1
3: ldc #18; //String auxiliar
5: astore_2
6: new #20; //class java/lang/StringBuilder
9: dup
10: aload_1
11: invokestatic #22; //Method java/lang/String.valueOf:(Ljava/lang/Object;)Ljava/lang/String;
14: invokespecial #28; //Method java/lang/StringBuilder."<init>":(Ljava/lang/String;)V
17: ldc #31; //String cadena2
19: invokevirtual #33; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
22: aload_2
23: invokevirtual #33; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
26: invokevirtual #37; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
29: astore_1
30: getstatic #41; //Field java/lang/System.out:Ljava/io/PrintStream;
33: aload_1
34: invokevirtual #47; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
37: return
}
El codigo equivalente, es el siguiente:
01: package test; 02: 03: public class StringTest6 { 04: public static void main(String[] args) { 05: String x = "cadena1"; 06: String y = "auxiliar"; 07: x = new StringBuilder(String.valueOf(x)).append("cadena2").append(y) 08: .toString(); 09: System.out.println(x); 10: } 11: } 12:
Lo cual es eficiente para en terminos de uso de los objetos creados.
martes, 18 de mayo de 2010
operador +, cadenas, cadenas constante y el compilador en Java
"Mucho ayuda el que no estorba"
El uso de cadenas, en un sistema es casi inevitable, pues las personas en general leen y escriben cadenas, independientemente de que estas representen fechas, numeros, palabras, etc.
La generacion de estas cadenas, repercute negativamente en el desempeño de una aplicacion o sistema, sobre todo, cuando se generan y utilizan de manera incorrecta o excesiva.
Un ejemplo es el operador + en el lenguaje de programacion, que cuando es correctamente empleado, puede no ser una carga excesiva, pero cuando se emplea incorrectamete o se mal interpreta su utilizacion, puede provocar que se trabaje de manera excesiva, consumiendo tiempo de procesamiento y memoria indiscriminadamente.
La mayoria de los lenguajes compilados, como Java, particularmente, los que no soportan sobrecarga de operadores por programacion, convierten las instrucciones que tienen el operador + cuando estan operando con cadenas, en objetos y/o funciones. Sin embargo, el compilador, puede tener la capacidad de manipular el codigo resultante, para minimizar el uso de los recursos (memoria y procesador)
En el siguiente codigo, se hace uso del operador +.
Posteriormente ejecutamos los siguientes comandos:
Obteniendo el siguiente codigo:
Como se puede observar, el compilador, tradujo la sentencia con el operador + en el uso de la funcion valueOf, la creacion de un objeto StringBuilder, el uso de la funcion append y finalmente toString, es decir algo como esto:
Nosotros conocemos que se estan empleando constantes, por lo que podemos substituir la variable por el valor.
Ejecutamos la compilacion (javac) y de compilacion (javap), obteniendo lo siguiente:
Este es el codigo equivalente, el cual genera el mismo codigo compilado, que el codigo anterior.
Como se puede notar, cuando se utilizan constantes, el operador + y el compilador, pueden optimizar el codigo, siempre y cuando la constante este "inline". De ahi, la frase inicial "mucho ayuda el que no estorba", en ocasiones hay que dejar que el compilador haga su trabajo.
El uso de cadenas, en un sistema es casi inevitable, pues las personas en general leen y escriben cadenas, independientemente de que estas representen fechas, numeros, palabras, etc.
La generacion de estas cadenas, repercute negativamente en el desempeño de una aplicacion o sistema, sobre todo, cuando se generan y utilizan de manera incorrecta o excesiva.
Un ejemplo es el operador + en el lenguaje de programacion, que cuando es correctamente empleado, puede no ser una carga excesiva, pero cuando se emplea incorrectamete o se mal interpreta su utilizacion, puede provocar que se trabaje de manera excesiva, consumiendo tiempo de procesamiento y memoria indiscriminadamente.
La mayoria de los lenguajes compilados, como Java, particularmente, los que no soportan sobrecarga de operadores por programacion, convierten las instrucciones que tienen el operador + cuando estan operando con cadenas, en objetos y/o funciones. Sin embargo, el compilador, puede tener la capacidad de manipular el codigo resultante, para minimizar el uso de los recursos (memoria y procesador)
En el siguiente codigo, se hace uso del operador +.
01: package test; 02: 03: public class StringTest { 04: public static void main(String[] args) { 05: String a = "cadena1"; 06: String b = "cadena2"; 07: String c = a + b; 08: System.out.println(c); 09: } 10: } 11:
Posteriormente ejecutamos los siguientes comandos:
javac test\StringBuilderTest.java
javap -c -classpath . test.StringTest
Obteniendo el siguiente codigo:
Compiled from "StringTest.java"
public class test.StringTest extends java.lang.Object{
public test.StringTest();
Code:
0: aload_0
1: invokespecial #8; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: ldc #16; //String cadena1
2: astore_1
3: ldc #18; //String cadena2
5: astore_2
6: new #20; //class java/lang/StringBuilder
9: dup
10: aload_1
11: invokestatic #22; //Method java/lang/String.valueOf:(Ljava/lang/Object;)Ljava/lang/String;
14: invokespecial #28; //Method java/lang/StringBuilder."<init>":(Ljava/lang/String;)V
17: aload_2
18: invokevirtual #31; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
21: invokevirtual #35; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
24: astore_3
25: getstatic #39; //Field java/lang/System.out:Ljava/io/PrintStream;
28: aload_3
29: invokevirtual #45; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
32: return
}
Como se puede observar, el compilador, tradujo la sentencia con el operador + en el uso de la funcion valueOf, la creacion de un objeto StringBuilder, el uso de la funcion append y finalmente toString, es decir algo como esto:
01: package test; 02: 03: public class StringTest2 { 04: public static void main(String[] args) { 05: String a = "cadena1"; 06: String b = "cadena2"; 07: String c = new StringBuilder(String.valueOf(a)).append(b).toString(); 08: System.out.println(c); 09: } 10: } 11:
Nosotros conocemos que se estan empleando constantes, por lo que podemos substituir la variable por el valor.
1: package test; 2: 3: public class StringTest3 { 4: public static void main(String[] args) { 5: String c = "cadena1" + "cadena2"; 6: System.out.println(c); 7: } 8: } 9:
Ejecutamos la compilacion (javac) y de compilacion (javap), obteniendo lo siguiente:
Compiled from "StringTest3.java"
public class test.StringTest3 extends java.lang.Object{
public test.StringTest3();
Code:
0: aload_0
1: invokespecial #8; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: ldc #16; //String cadena1cadena2
2: astore_1
3: getstatic #18; //Field java/lang/System.out:Ljava/io/PrintStream;
6: aload_1
7: invokevirtual #24; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
10: return
}
Este es el codigo equivalente, el cual genera el mismo codigo compilado, que el codigo anterior.
1: package test; 2: 3: public class StringTest4 { 4: public static void main(String[] args) { 5: String c = "cadena1cadena2"; 6: System.out.println(c); 7: } 8: } 9:
Como se puede notar, cuando se utilizan constantes, el operador + y el compilador, pueden optimizar el codigo, siempre y cuando la constante este "inline". De ahi, la frase inicial "mucho ayuda el que no estorba", en ocasiones hay que dejar que el compilador haga su trabajo.
viernes, 14 de mayo de 2010
binario a hexadecimal en C
Funcion que genera una cadena hexadecimal en base a una cadena binaria. Esta funcionalidad es util, para tranportar o almacenar informacion binaria y posteriormente recuperarla
Explicacion:
04-04: Caracteres validos en hexadecimal, ordenados convenientemente
06-17: Arreglo que sirve para invertir el proceso, convirtiendo un caracter hexadeximal en binario
19-39: Funcion que codifica la informacion binaria en una cadena hexadecimal, la longitud de la informacion binaria, esta indicada por len.
41-58: Funcion que extrae la informacion binaria de una cadena hexadecimal, la longitud resultante se almacenara en la direccion de len.
Optimizacion:
01: #include <stdlib.h> 02: #include <string.h> 03: 04: static const char *base="0123456789abcdef"; 05: 06: static const unsigned int ibase[]={ 07: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 08: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 09: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11: 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12: 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 13: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16: 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 17: 13, 14, 15}; 18: 19: char *uchar2hex(const unsigned char *in, size_t len) 20: { 21: char *out; 22: int i; 23: int l; 24: 25: l=sizeof(char)*len*2+1; 26: out=malloc(l); 27: out[l]='\0'; 28: for(i=0;i<len;i++) 29: { 30: int p; 31: int t; 32: 33: p=i*2; 34: t=in[i]; 35: out[p]=base[(t>>4)&0x0F]; 36: out[p+1]=base[t&0x0F]; 37: } 38: return out; 39: } 40: 41: unsigned char *hex2uchar(char *hexstr, size_t *len) 42: { 43: unsigned char *out; 44: int i; 45: int l; 46: 47: l=strlen(hexstr)/2; 48: out=malloc(sizeof(unsigned char)*l); 49: for(i=0;i<l;i++) 50: { 51: int p; 52: 53: p=i*2; 54: out[i]=(unsigned char)((ibase[hexstr[p]&0xEF]<<4)|(ibase[hexstr[p+1]&0xEF]&0xFF)); 55: } 56: *len=l; 57: return out; 58: } 59:
Explicacion:
04-04: Caracteres validos en hexadecimal, ordenados convenientemente
06-17: Arreglo que sirve para invertir el proceso, convirtiendo un caracter hexadeximal en binario
19-39: Funcion que codifica la informacion binaria en una cadena hexadecimal, la longitud de la informacion binaria, esta indicada por len.
41-58: Funcion que extrae la informacion binaria de una cadena hexadecimal, la longitud resultante se almacenara en la direccion de len.
Optimizacion:
- Se construye el arreglo resultante con la logitud exacta necesaria
- Se emplean arreglos, para minimizar el numero de operaciones
- Los valores regresados por estas funciones, se deben liberar con la funcion free, pues se aloja memoria con malloc
- En esta version, solo es posible usar minusculas
miércoles, 12 de mayo de 2010
Extraccion del nombre de una propiedad del getter respectivo en java
Extraccion del nombre de una propiedad del getter respectivo
Esta funcionalidad es requerida, para obtener dinamicamente el nombre de la propiedad asociada al methodo getter, sin embargo, puede complicarse, debido a que el estandard puede aceptar el prefijo is o el prefijo get
Explicacion:
06-06: Determinar donde inicia el nombre de la propiedad.
07-07: El primer caracter del nombre de la propiedad, lo convertimos a minuscula
09-14: Determinamos si el nombre de la propiedad, esta formado por 1 o mas letras.
Optimizacion:
Esta funcionalidad es requerida, para obtener dinamicamente el nombre de la propiedad asociada al methodo getter, sin embargo, puede complicarse, debido a que el estandard puede aceptar el prefijo is o el prefijo get
01: package test; 02: 03: public class Test { 04: public String getProperty(String methodName) { 05: assert methodName.startsWith("get") || methodName.startsWith("is"); 06: int index = methodName.charAt(0) == 'i' ? 2 : 3;// cache 07: char c = Character.toLowerCase(methodName.charAt(index));// cache 08: int l = methodName.length(); 09: if ((index == 3 && l > 4) || (index == 2 && l > 3)) { 10: return new StringBuilder(l-index).append(c).append( 11: methodName.substring(index + 1)).toString(); 12: } else { 13: return new String(new char[] { c }); 14: } 15: } 16: } 17:
Explicacion:
06-06: Determinar donde inicia el nombre de la propiedad.
07-07: El primer caracter del nombre de la propiedad, lo convertimos a minuscula
09-14: Determinamos si el nombre de la propiedad, esta formado por 1 o mas letras.
Optimizacion:
- Se realiza cache de variables, como el indice, para evitar calcularlo en cada ocasion
- Cuando el nombre de la propiedad esta formado por un solo caracter se construye una cadena formada por ese caracter exclusivamente, en caso contrario, se forma la cadena correspondiente.
- Cuando el nombre de la propiedad esta formado por mas de un caracter, se crea un StringBuilder de longitud exacta.
Suscribirse a:
Entradas (Atom)