Tengo un requisito para (muy) rápidamente procesar cadenas de un rango limitado, contabilizando sus valores. El archivo de entrada tiene el formato:¿Hay alguna manera de hacer esta búsqueda hash más rápido?
January 7
March 22
September 87
March 36
y así sucesivamente. Debido a que los anchos de línea son idénticos, simplemente puedo leer en una línea con fread razonablemente rápido, y he desarrollado una función de hash perfecta que funciona, pero quería ver si alguien puede ofrecer algún consejo sobre cómo hacerlo aún más rápido. Voy a perfilar cada sugerencia para ver cómo va.
La función de hash se basa en el nombre del mes para permitir la asignación rápida del valor a un depósito. Ten paciencia conmigo aquí. La primera vez que descubrí el número mínimo de caracteres para un hash perfecta:
January
February
March
April
May
June
July
August
September
October
November
December
Tenga en cuenta que los meses son todos nueve caracteres debido al hecho de que tengo toda la línea de entrada.
Desafortunadamente, no hay una sola columna para marcar un mes único. La columna 1 duplica J, la columna 2 duplica a, la columna 3 duplica r, la columna 4 duplica u y las columnas 5 en adelante duplican <space> (hay otros duplicados, pero uno es suficiente para evitar una clave hash de columna única).
Sin embargo, mediante el uso de la primera y cuarta columna, obtener los valores Ju, Fr, Mc, Ai, M<space>, Je, Jy, Au, St, Oo, Ne y De, que son únicos. No habrá valores inválidos en este archivo, así que no tengo que preocuparme por los cubos incorrectos para los datos de entrada.
Al ver los códigos hexadecimales de los caracteres, descubrí que podía obtener valores únicos bajas con sólo AND con valores estratégicos:
FirstChar Hex Binary &0x0f
--------- --- --------- -----
A x41 0100 0001 1
D x44 0100 0100 4
F x46 0100 0110 6
J x4a 0100 1010 10
M x4d 0100 1101 13
N x4e 0100 1110 14
O x4f 0100 1111 15
S x53 0101 0011 3
SecondChar Hex Binary &0x1f
---------- --- --------- -----
<space> x20 0010 0000 0
c x63 0110 0011 3
e x65 0110 0101 5
i x69 0110 1001 9
o x6f 0110 1111 15
r x72 0111 0010 18
t x74 0111 0100 20
u x75 0111 0101 21
y x79 0111 1001 25
y esto me ha permitido configurar una matriz estática para crear una (con suerte) función hash deslumbrantemente rápido:
#define __ -1
static unsigned int hash (const char *str) {
static unsigned char bucket[] = {
// A S D F J M N O
__, __, __, __, __, __, __, __, __, __, __, __, __, 4, __, __, // space
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, 2, __, __, // c
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, 11, __, __, __, __, __, 5, __, __, __, 10, __, // e
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, 3, __, __, __, __, __, __, __, __, __, __, __, __, __, __, // i
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 9, // o
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, 1, __, __, __, __, __, __, __, __, __, // r
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, 8, __, __, __, __, __, __, __, __, __, __, __, __, // t
__, 7, __, __, __, __, __, __, __, __, 0, __, __, __, __, __, // u
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, 6, __, __, __, __, __ // y
};
return bucket[((unsigned int)(str[3]&0x1f)<<4)|(str[0]&0xf)];
}
Prueba que con el código:
#include <stdio.h>
#include <string.h>
// Hash function here.
static char *months[] = {
"January ", "February ", "March ", "April ", "May ", "June ",
"July ", "August ", "September", "October ", "November ", "December "
};
int main (void) {
int i;
for (i = 0; i < sizeof(months)/sizeof(*months); i++)
printf ("%-10s -> %2d\n", months[i], hash(months[i]));
return 0;
}
muestra que es funcionalmente correcto:
January -> 0
February -> 1
March -> 2
April -> 3
May -> 4
June -> 5
July -> 6
August -> 7
September -> 8
October -> 9
November -> 10
December -> 11
pero quiero saber si se puede hacer más rápido.
¿Alguna sugerencia por ahí? Estoy abierto a cualquier optimización simple o incluso a una reescritura total si hay algo intrínsecamente malo con mi función de hash.
No creo que esto sea tan importante, pero la versión final utilizará EBCDIC. La teoría seguirá en pie, pero la operación AND puede cambiar ligeramente ya que los caracteres tienen diferentes puntos de código. Estaré contento con cualquier ayuda solo en el frente ASCII ya que estoy seguro de que cualquier consejo que se ofrezca se traducirá bien en EBCDIC.
No entiendo por qué necesita una tabla hash cuando tiene un número fijo de teclas, que lógicamente representan 0 - 11. Editar: Creo que ahora entiendo, no importa la pregunta :) – leppie
Para aclarar, no puede simplemente tomar una externa la dirección de la cadena y espero que le dé un índice a una matriz :) – leppie
@leppie, tiene razón, los datos de entrada son las cadenas, mi programa de prueba muestra los números (de matriz) solo para mi depuración. Perdón por eso, lo editaré para eliminar cualquier confusión. – paxdiablo