|
Hash tables
Copyright © 2001 Alirio A Gavidia B.. Para ver más de
mis artículos visite Programación Orientada en Delphi
Cómo tomar una decisión
Un problema común en la programación está en la toma de un rumbo basado
en el valor de una secuencia literal de caracteres. Esto es simplemente
poder ejecutar una opción si por ejemplo la variable Pago es
'efectivo', 'cheque',
'tarjeta' o 'transferencia'.
Podríamos diseñar una secuencia de código como la siguiente:
Const
STransfer = 'transferencia';
SCheck = 'cheque';
SCard = 'tarjeta';
SCash = 'efectivo';
SPayMode = 'Forma de pago';
SUnknow = 'desconocido';
If pago=SCash then
...
If pago=SCheck then
...
If pago=SCard then
...
If pago=STransfer then
...
Esto funcionaría, y para ser sincero no me preocuparía mucho por ello.
Es práctico. Sin embargo si hablamos de más opciones (unas 32, se me
ocurre) se puede volver algo incómodo y ciertamente poco elegante.
La opción de un case es, en este nivel, inutilizable.
Simplemente se requiere tipos matemáticamente "contables" (enteros,
letras y enumerados). Esto permite que el case sea
realmente eficiente (a diferencia del "Case" de lenguajes xBase).
Mejorando el ejemplo anterior podemos ir a:
If pago=SCash then
...
else If pago= SCheck then
...
else If pago= SCard then
...
else If pago= STransfer then
...
Esto cambio evita que se hagan "n" lecturas para igual número de
opciones, pero, para el caso de la última opción, o peor aún, el caso
en que la opción sea diferente a las esperadas, igual se realizan "n"
consultas.
Las alternativas – orden
El orden parece ser la vía. Se establece una lista ordenada y se realiza
una búsqueda binaria (divide y conquista). Supongamos tenemos 32
elementos: Dividimos en dos de 16 y seleccionamos, dividimos en dos de 8
y seleccionamos, dividimos en dos de 4 y seleccionamos, dividimos en dos
de 2 y seleccionamos, y se escoge el final. Total: 5 decisiones (nótese
el hecho de que 2 elevado a la 5ta potencia es 32).
Hasta ahora la búsqueda binaria nos garantiza para 32 opciones un máximo
de 5 (log N) consultas (en realidad, 50% de las búsquedas se resolverían
en 5 consultas, piénselo). Los if anidados nos darían en
promedio 16 consultas (n/2).
Más cerca del "case..of"
Una idea que siempre se presenta, y que he visto usar, es tomar la
primera letra. Para el ejemplo inicial esto nos dejaría usar una
estructura tipo Case, pero al llegar a la
letra 't' de 'tarjeta' y de
'trasferencia' (o 'c' de 'cash',
'check' o 'card' en inglés) necesitaríamos,
al menos, colocar un if. Otra aproximación sería crear una
función que nos dé un número por identificador. Propongo para el ejemplo
dado lo siguiente:
Function IdentIndex(AIdent: String): integer;
Begin
Result := length(AIdent) + Ord(AIdent[3])
end
sCash 109 // en castellano
SCheck 107 // en castellano
SCard 121 // en castellano
STransfer 110 // en castellano
sCash 119 // en inglés
SCheck 106 // en inglés
SCard 118 // en inglés
STransfer 105 // en inglés
Ahora es posible usar Case:
Var
Ident : string;
begin
Ident := 'efectivo';
if InputQuery('Hash', SPayMode, Ident) then
case IdentIndex(Ident) of
109: ShowMessage(SCash);
107: ShowMessage(SCheck);
121: ShowMessage(SCard);
110: ShowMessage(STransfer);
else
ShowMessage(SUnknown);
end
end;
Pros y contras
El método es interesante ante el hecho de reducir el número de consultas
necesarias a una. Sin embargo tenemos ahora la sobrecarga de determinar
la función adecuada que devuelva los índices. Una incorrecta determinación
de esta fórmula nos presenta los siguientes problemas:
- Repetición de índices
- Índices esparcidos
- Lentitud en evaluación de la fórmula
El último punto es muy obvio y no lo comentaré.
La repetición de índices nos obliga a pasos adicionales dentro
del Case. Si tenemos dos identificadores generando el
mismo índice hay que hacer al menos un análisis adicional para reconocer
cuál es el camino correcto.
Los índices esparcidos son un inconveniente si pretendemos construir una
tabla. En este caso podríamos diseñar un arreglo como el que a continuación
ejemplifico:
Begin
:
FillChar(JumpTable,SizeOf(JumpTable), 0);
JumpTable[IdentIndex(SCash)] := PayModeCash;
JumpTable[IdentIndex(SCheck)] := PayModeCheck;
JumpTable[IdentIndex(SCard)] := PayModeCard;
JumpTable[IdentIndex(sTransfer)] := PayModeTransfer;
:
End;
Var
JumpTable : array [100..130] of TRoutine;
Index : Integer;
Ident : string;
Begin
Ident := SCash;
InputQuery('Hash', SPayMode, Ident);
Index := IdentIndex(Ident);
if (Index in [100..130]) and (Assigned(JumpTable[Index])) then
JumpTable[Index]
end;
Tenemos JumpTable como un arreglo de rutinas que se ejecutan
dado un índice. Pero hay un desperdicio ya que utilizamos desde 30 posibles
valores sólo cuatro. Lo ideal sería que IdentIndex nos otorgara
cuatro valores consecutivos. A veces tenemos que vivir con eso, pero a veces
no. En el caso del analizador de un compilador normalmente es posible
dedicar esfuerzo para determinar la fórmula adecuada sin desperdicio.
Pero cuando son muchas palabras, o no se conocen todas de antemano,
tenemos que reenfocar todo este asunto.
Las listas o tablas "Hash"
La fórmula para determinar el índice debe por lo general ser limitada
dado que no solemos estar en capacidad de crear arreglos con índices de
14 dígitos. La solución más simple es dividir. Si queremos limitarnos a
sólo 8 posibilidades podríamos dividir entre 8 y obtener el resto.
Así los nuevos valores serán
sCash 5 // en castellano
SCheck 3 // en castellano
SCard 1 // en castellano
STransfer 6 // en castellano
sCash 7 // en inglés
SCheck 2 // en inglés
SCard 6 // en inglés
STransfer 1 // en inglés
Demasiado bueno, pero a veces no resulta así, por ejemplo limitándolo a
cuatro se hace presente la repetición de los índices.
sCash 1 // en castellano
SCheck 3 // en castellano
SCard 1 // en castellano
STransfer 2 // en castellano
sCash 3 // en inglés
SCheck 2 // en inglés
SCard 2 // en inglés
STransfer 1 // en inglés
El límite sugerido para una tabla suele ser un número primo que no sea
muy cercano a una potencia de 2.
Para tablas con repetición de índices normalmente se obtiene el índice,
se consulta la tabla, y si la celda esta libre se toma, sino se busca la
siguiente libre de manera linear. Cada falla en esta búsqueda reduce la
eficiencia del método.
Las listas de hashing se construyen como listas de listas. Cada nodo de
la lista principal apunta a la lista de identificadores que corresponden
al índice dado. Hay otras soluciones a este problema, pero no las
analizaré aquí.
Enfrentando la manera de hallar el índice - Método de multiplicación
Me gusta esta manera de resolver el problema cuando tenemos un número en
un rango amplio y queremos reducirlo en un rango menor.
Para número de posibles valores 2^N (2 elevado a la N). Key es un
valor generado directamente al evaluar el identificador.
La fórmula se determina de la siguiente manera:
Hash := ((K*Key) and M) mod S;
Dónde:
- K es 158 para índices de 8 bits, 40503 para índices de 16 bits y
2654435769 para índices de 32 bits.
- S es 2 elevado la diferencia del número de bits y N.
- M es el tamaño de la tabla menos 1. (2^N-1).
Para N=10 tenemos
K=40503 (16 bits)
S=2^(16-10) = 2^6 = 64
M=1023
Hash := ((40503*Key) and 1023) mod 64;
El resultado será un valor desde 0 hasta 63 (de una rango original de 0
a 1023).
Manipulando cadenas de caracteres
Usualmente se puede simplemente tomar cada carácter de una cadena,
sumarlos y tomar el modulo con 256. Sin embargo esto genera problemas
con los anagramas ('arroz' y 'zorra' por
ejemplo) y palabras similares.
Una solución es utilizar xor ("o" exclusivo) en lugar de
la adición y agregar una tabla intermedia de valores pseudo-aleatorios
que nos den una mejor distribución, además considerar en el algoritmo
la posición de cada letra y no sólo su valor intrínseco.
Conclusión
Utilizar "hash tables" puede dar resultados espectaculares en situaciones
donde se tiene conocimiento de los identificadores a buscar y/o
dónde podemos desperdiciar memoria a cambio de velocidad. En lo
particular, los compiladores e interpretadores son, a mi parecer, los
mejores casos. También es útil en sistemas de base de datos donde el
problema no sea espacio sino la necesidad de mínima cantidad de
lecturas. Sin embargo un problema a tener en cuenta es la eliminación de
registros en la tabla, algo usual en bases de datos.
Para aprender más:
- D. E. Knuth, 1973, The Art of Computer Programming, Vol. 3: Sorting
and Searching, Reading, MS: Addison-Wesley.
Copyright © 2001 por Alirio A. Gavidia B. Todos los derechos reservados.
Se permite la publicación de este material por cualquier medio por parte
de cualquiera siempre que este no sea modificado en contenido y se cite
la fuente original.
Puede encontrar el código fuente completo de este artículo en el archivo que acompaña al Boletín Pascal #23.
|
