1. Inicio
  2. Pregunta y respuesta
  3. Mapa Hash optimizado para la búsqueda

Mapa Hash optimizado para la búsqueda

2011-12-08 12 views
5

Estoy buscando un mapa que tenga teclas fijas (corregidas durante la inicialización) y que haga una búsqueda más rápida. Es posible que no admita la adición/actualización de elementos más adelante. ¿Hay algún algoritmo que busque la lista de claves y formule una función para que sea más rápido buscarla más tarde? En mi caso, las llaves son cuerdas.Mapa Hash optimizado para la búsqueda

Actualización:

Las llaves no son conocidos en tiempo de compilación. Pero durante el tiempo de inicialización de la aplicación. No habrá más inserciones más adelante, pero habrá muchas búsquedas. Así que quiero que las búsquedas estén optimizadas.

Fuente

2011-12-08 balki

+3

Mira [gperf] (http://www.gnu.org/s/gperf/), facilita el hash perfecto en tiempo de compilación cuando todas las claves de la tabla hash son conocido. –

Respuesta

2

CMPH puede ser lo que estás buscando. Básicamente esto es gperfsin requiriendo el conjunto en tiempo de compilación.

Aunque por supuesto std::unordered_map como por C++ 11 podría hacerlo, aunque posiblemente con algunas colisiones.

Dado que las operaciones de búsqueda cuerdas, cadenas, un trie (cualquiera de los diferentes sabores trie, Crit bits o lo que sea nombres muy exóticos que tienen) también puede ser útil para investigar, especialmente si usted tiene muchos de ellos. Hay muchas implementaciones gratuitas gratuitas disponibles.
La ventaja de los intentos es que pueden indexar cadenas, por lo que usan menos memoria, que tiene una mayor probabilidad de tener datos en la memoria caché. Además, el patrón de acceso es menos aleatorio, que también es amigable con el caché. Una tabla hash debe almacenar el valor más el hash e índices más o menos al azar (no aleatoriamente, pero impredeciblemente) en la memoria. Una estructura trie/trie idealmente solo necesita un bit adicional que distinga una clave de su prefijo común en cada nodo.

(Nota de la forma en que O (log (n)) puede ser muy posiblemente más rápido que O (1), en tal caso, debido a las grandes O no tiene en cuenta cosas por el estilo.)

Fuente

2011-12-08 10:21:06 Damon

+0

Trie es mucho más lento que std :: unordered_map para cadenas (también conocido como std :: string alias std :: basic_string ). Ha probado con diferentes indicadores de optimización. Y hay muchos informes en Internet sobre eso. – cppist

+0

@cppist: Esto depende de la implementación y del conjunto de datos (tanto su tamaño como los datos reales). 'std :: unordered_map' es un mapa hash. Es 'O (1)' con respecto a la búsqueda real, pero 'O (N)' con respecto a la longitud de la cadena, y debe hacer una comparación 'O (N)' adicional. Un árbol o trie de crit-bit es 'O (log (N))' con respecto a la longitud de la clave y al número de claves. No necesita una comparación final, no necesita tocar datos después del primer byte diferente, y es más compatible con la memoria caché, tocando menos páginas. En la medida en que la respuesta no es tan fácil, un hash _may_ de hecho no será la herramienta más rápida. – Damon

+1

N es una cantidad de palabras. C - es una cantidad de colisiones. S - longitud de la cuerda. Trie busca cadena para T = O1 (S). El conjunto Hash busca cadenas para H = O2 (S) + O3 (C). Pero O1 (S) es mucho más grande que O2 (S). El conjunto Hash usa operaciones aritméticas simples bajo los datos consiguientes. Pero trie usa múltiples dereferences y if-branches. Incluso si la desreferenciación y la derivación serán más rápidas que los aritméticos simples, los procesadores comunes funcionan mejor con datos secuenciales en lugar de inconsecuentes. El bien hecho trie es realmente más lento que unordered_map aka hash set. Por lo menos para cadenas de (char). – cppist

0

probar Google-sparsehash: http://code.google.com/p/google-sparsehash/

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed.

Fuente

2011-12-08 10:21:01

1

Tenga en cuenta que Estas son cosas distintas: ¿necesita un límite superior, necesita una tasa típica rápida o necesita la búsqueda más rápida, sin preguntas? El último le costará, los primeros dos pueden ser objetivos conflictivos.

Se podría intentar crear una función hash perfecta basada en la entrada (es decir, uno que no tiene colisiones del conjunto de entrada). Este es un problema resuelto de alguna manera (por ejemplo, this, this). Sin embargo, generalmente generan código fuente y pueden pasar un tiempo significativo generando la función hash.

Una modificación de esto sería usar una función hash genérica (por ejemplo, shift-multiplicaly-add) y hacer una búsqueda de fuerza bruta sobre parámetros adecuados.

Esto tiene que ser intercambiado con el costo de unas pocas comparaciones de cuerdas (que no son tan terriblemente caras si no tiene que cotejar).

Otra opción es utilizar dos funciones hash distintas: esto aumenta el costo de una búsqueda única, pero hace que la degradación sea menos probable que la de los extraterrestres al robar los relojes de su reloj. Es bastante improbable que esto sea un problema con cadenas típicas y una función hash decente.

Fuente

2011-12-08 10:36:29 peterchen

+1

+1 por considerar hacer la pregunta "¿necesita un límite superior?", Más su último párrafo. Lo que describes en el último párrafo es básicamente hash de cuco. Es más lento para la búsqueda individual como dijiste (y para insertos, también), pero tiene un límite superior garantizado en el peor de los casos, que, si uno tiene ese requisito, es súper genial. – Damon

Cuestiones relacionadas

 Cuestiones relacionadas