c++ - ¿Hay alguna ventaja de usar map over unordered_map en caso de claves triviales?

hashmap c++ reference (12)

Una reciente charla sobre unordered_map en C ++ me hizo darme cuenta de que debería usar unordered_map para la mayoría de los casos donde usé map antes, debido a la eficacia de la búsqueda ( amortizado O (1) vs. O (log n) ). La mayoría de las veces que uso un mapa, utilizo int ''s o std::strings como teclas, por lo tanto no tengo problemas con la definición de la función hash. Cuanto más lo pensaba, más me daba cuenta de que no podía encontrar ninguna razón para usar std::map en el caso de tipos simples sobre un unordered_map . unordered_map un vistazo a las interfaces y no lo hice. Encuentra cualquier diferencia significativa que pueda impactar mi código.

De ahí la pregunta: ¿hay alguna razón real para usar std::map sobre un unordered map en el caso de tipos simples como int y std::string ?

Estoy preguntando desde un punto de vista estrictamente de programación: sé que no se considera completamente estándar y que puede plantear problemas con la migración.

También espero que una de las respuestas correctas sea "es más eficiente para conjuntos de datos más pequeños" debido a una sobrecarga más pequeña (¿es cierto?); Por lo tanto, me gustaría restringir la pregunta a los casos en que la cantidad de claves No es trivial (> 1 024).

Edit: duh, olvidé lo obvio (gracias GMan!) - sí, los mapas están ordenados por supuesto - lo sé, y estoy buscando otras razones.

Diferencias significativas que realmente no se han mencionado adecuadamente aquí:

map mantiene a los iteradores en todos los elementos estables, en C ++ 17 incluso puede mover elementos de un map a otro sin invalidar los iteradores que los invalidan (y si se implementan adecuadamente sin ninguna asignación potencial).
map tiempos de los map para operaciones individuales suelen ser más consistentes, ya que nunca necesitan grandes asignaciones.
unordered_map usando std::hash tal como se implementó en libstdc ++ es vulnerable a DoS si se alimenta con información no confiable (usa MurmurHash2 con una semilla constante, lo que no ayudaría realmente a la siembra, consulte https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ ).
El pedido permite realizar búsquedas de rango eficientes, por ejemplo, iterar sobre todos los elementos con la tecla> = 42.

Desde: http://www.cplusplus.com/reference/map/map/

"Internamente, los elementos en un mapa siempre se ordenan por su clave siguiendo un criterio de ordenamiento débil estricto específico indicado por su objeto de comparación interno (de tipo Comparar).

los contenedores de mapas son generalmente más lentos que los contenedores de mapas no ordenados para acceder a elementos individuales por su clave, pero permiten la iteración directa en subconjuntos según su orden ".

En la mayoría de los idiomas, el mapa no ordenado (también conocido como hash basado en diccionarios) es el mapa predeterminado; sin embargo, en C ++, el mapa ordenado se obtiene como mapa predeterminado. ¿Cómo ocurrió eso? Algunas personas asumen erróneamente que el comité de C ++ tomó esta decisión en su sabiduría única, pero la verdad es, lamentablemente, más fea que eso.

En general, se believed que C ++ terminó con el mapa ordenado como predeterminado porque no hay demasiados parámetros sobre cómo se pueden implementar. Por otro lado, las implementaciones basadas en hash tienen muchas cosas de las que hablar. Por lo tanto, para evitar los bloqueos en la estandarización, se llevaron el mapa ordenado. Alrededor de 2005, muchos idiomas ya tenían buenas implementaciones de implementación basada en hash, por lo que fue más fácil para el comité aceptar nuevos std::unordered_map . En un mundo perfecto, std::map estaría ordenado y tendríamos std::ordered_map como tipo separado.

Debajo de dos gráficos deben hablar por sí mismos ( source ):

Resumen

Suponiendo que el pedido no es importante:

Si va a crear una tabla grande una vez y hacer muchas consultas, use std::unordered_map
Si va a construir una tabla pequeña (puede tener menos de 100 elementos) y hacer muchas consultas, use std::map . Esto se debe a que las lecturas son O(log n) .
Si va a cambiar mucho la tabla, entonces puede que std::map sea una buena opción.
Si tiene dudas, simplemente use std::unordered_map .

Las razones se han dado en otras respuestas; aquí está otro.

Las operaciones std :: map (árbol binario equilibrado) se amortizan O (log n) y en el caso más desfavorable O (log n). Las operaciones std :: unordered_map (tabla hash) se amortizan O (1) y en el caso más desfavorable O (n).

La práctica en la práctica es que la tabla hash "falla" de vez en cuando con una operación O (n), que puede o no ser algo que su aplicación pueda tolerar. Si no puede tolerarlo, preferiría std :: map sobre std :: unordered_map.

Las tablas hash tienen constantes más altas que las implementaciones de mapas comunes, que se vuelven importantes para los contenedores pequeños. ¿El tamaño máximo es 10, 100 o tal vez incluso 1,000 o más? Las constantes son las mismas que siempre, pero O (log n) está cerca de O (k). (Recuerde que la complejidad logarítmica sigue siendo muy buena).

Lo que hace que una función hash sea buena depende de las características de sus datos; así que si no planeo ver una función hash personalizada (pero ciertamente puedo cambiar de opinión más tarde, y fácilmente ya que tipeo casi todo) y aunque los valores predeterminados son elegidos para funcionar decentemente para muchas fuentes de datos, encuentro la ordenada La naturaleza del mapa es suficiente para una ayuda que inicialmente todavía tengo que asignar en lugar de una tabla hash en ese caso.

Además, de esa manera, no tiene que pensar siquiera en escribir una función hash para otros tipos (generalmente UDT), y simplemente escribir op <(que de todos modos quiere).

Me gustaría repetir aproximadamente el mismo punto que GMan hizo: según el tipo de uso, std::map puede ser (y con frecuencia es) más rápido que std::tr1::unordered_map (utilizando la implementación incluida en VS 2008 SP1).

Hay algunos factores complicados a tener en cuenta. Por ejemplo, en std::map , estás comparando claves, lo que significa que solo miras lo suficiente del principio de una clave para distinguir entre las subramas derecha e izquierda del árbol. En mi experiencia, casi la única vez que mira una clave completa es si está usando algo como int que puede comparar en una sola instrucción. Con un tipo de clave más típico como std :: string, a menudo se comparan solo unos pocos caracteres.

Una función hash decente, por el contrario, siempre mira la tecla completa . IOW, incluso si la búsqueda de tablas es de complejidad constante, el hash en sí mismo tiene una complejidad aproximadamente lineal (aunque en la longitud de la clave, no en el número de elementos). Con cadenas largas como claves, un std::map puede terminar una búsqueda antes de que unordered_map comience su búsqueda.

Segundo, aunque existen varios métodos para cambiar el tamaño de las tablas hash, la mayoría de ellas son bastante lentas, al punto de que, a menos que las búsquedas sean considerablemente más frecuentes que las inserciones y eliminaciones, std :: map a menudo será más rápido que std::unordered_map .

Por supuesto, como mencioné en el comentario de tu pregunta anterior, también puedes usar una tabla de árboles. Esto tiene tanto ventajas como desventajas. Por un lado, limita el peor de los casos al de un árbol. También permite una inserción y eliminación rápidas, porque (al menos cuando lo he hecho) he usado una tabla de tamaño fijo. Eliminar todo el cambio de tamaño de la tabla le permite mantener su tabla hash mucho más simple y típicamente más rápida.

Otro punto: los requisitos para el hashing y los mapas basados en árboles son diferentes. El hash, obviamente, requiere una función hash, y una comparación de igualdad, donde los mapas ordenados requieren una comparación menor que la normal. Por supuesto, el híbrido que mencioné requiere de ambos. Por supuesto, para el caso común de usar una cadena como la clave, esto no es realmente un problema, pero algunos tipos de claves se adaptan mejor al hashing (o viceversa).

Me intrigó la respuesta de @Jerry Coffin, que sugería que el mapa ordenado mostraría aumentos de rendimiento en cadenas largas, después de algunos experimentos (que se pueden descargar de pastebin ), he descubierto que esto solo parece ser válido para las colecciones. de cadenas aleatorias, cuando el mapa se inicializa con un diccionario ordenado (que contiene palabras con cantidades considerables de prefijo-superposición), esta regla se rompe, probablemente debido a la mayor profundidad de árbol necesaria para recuperar el valor. Los resultados se muestran a continuación, la columna del primer número es el tiempo de inserción, el segundo es el tiempo de recuperación.

g++ -g -O3 --std=c++0x -c -o stdtests.o stdtests.cpp g++ -o stdtests stdtests.o gmurphy@interloper:HashTests$ ./stdtests # 1st number column is insert time, 2nd is fetch time ** Integer Keys ** unordered: 137 15 ordered: 168 81 ** Random String Keys ** unordered: 55 50 ordered: 33 31 ** Real Words Keys ** unordered: 278 76 ordered: 516 298

No olvides que los map mantienen sus elementos ordenados. Si no puedes renunciar a eso, obviamente no puedes usar un unordered_map .

Otra cosa a tener en cuenta es que unordered_map generalmente usa más memoria. Un map solo tiene unos pocos indicadores de mantenimiento y memoria para cada objeto. Por el contrario, unordered_map ''s tiene una gran variedad (esto puede ser bastante grande en algunas implementaciones) y luego memoria adicional para cada objeto. Si necesita ser consciente de la memoria, un map debería ser mejor, ya que carece de la gran matriz.

Por lo tanto, si necesita recuperación de búsqueda pura, diría que un unordered_map es el camino a seguir. Pero siempre hay concesiones, y si no puedes pagarlas, entonces no puedes usarlas.

Solo a partir de la experiencia personal, encontré una enorme mejora en el rendimiento (medido, por supuesto) al usar un map no unordered_map lugar de un map en una tabla de consulta de la entidad principal.

Por otro lado, descubrí que era mucho más lento en insertar y quitar elementos repetidamente. Es genial para una colección relativamente estática de elementos, pero si estás haciendo un montón de inserciones y eliminaciones, el hashing + bucketing parece sumarse. (Nota, esto fue durante muchas iteraciones.)

Pequeña adición a todo lo anterior:

Mejor uso del map , cuando necesita obtener elementos por rango, ya que están ordenados y puede iterarlos de un límite a otro.

Recientemente hice una prueba que hace que 50000 se fusionen y clasifiquen. Eso significa que si las claves de cadena son las mismas, fusione la cadena de bytes. Y la salida final debe ser ordenada. Así que esto incluye una búsqueda para cada inserción.

Para la implementación del map , se necesitan 200 ms para finalizar el trabajo. Para unordered_map + map , se necesitan 70 ms para la inserción de unordered_map y 80 ms para la inserción del map . Así que la implementación híbrida es 50 ms más rápida.

Debemos pensar dos veces antes de usar el map . Si solo necesita que los datos se clasifiquen en el resultado final de su programa, una solución híbrida puede ser mejor.

Si desea comparar la velocidad de sus implementaciones std :: map y std :: unordered_map, puede utilizar el proyecto sparsehash de Google, que tiene un programa time_hash_map para cronometrarlas. Por ejemplo, con gcc 4.4.2 en un sistema x86_64 Linux

$ ./time_hash_map TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations): map_grow 126.1 ns (27427396 hashes, 40000000 copies) 290.9 MB map_predict/grow 67.4 ns (10000000 hashes, 40000000 copies) 232.8 MB map_replace 22.3 ns (37427396 hashes, 40000000 copies) map_fetch 16.3 ns (37427396 hashes, 40000000 copies) map_fetch_empty 9.8 ns (10000000 hashes, 0 copies) map_remove 49.1 ns (37427396 hashes, 40000000 copies) map_toggle 86.1 ns (20000000 hashes, 40000000 copies) STANDARD MAP (4 byte objects, 10000000 iterations): map_grow 225.3 ns ( 0 hashes, 20000000 copies) 462.4 MB map_predict/grow 225.1 ns ( 0 hashes, 20000000 copies) 462.6 MB map_replace 151.2 ns ( 0 hashes, 20000000 copies) map_fetch 156.0 ns ( 0 hashes, 20000000 copies) map_fetch_empty 1.4 ns ( 0 hashes, 0 copies) map_remove 141.0 ns ( 0 hashes, 20000000 copies) map_toggle 67.3 ns ( 0 hashes, 20000000 copies)

Simplemente señalo que ... hay muchos tipos de unordered_map .

Busque el artículo de Wikipedia en el mapa hash. Dependiendo de la implementación que se usó, las características en términos de búsqueda, inserción y eliminación pueden variar bastante.

Y eso es lo que más me preocupa con la adición de unordered_map a la STL: tendrán que elegir una implementación particular ya que dudo que sigan el camino de la Policy , por lo que nos quedaremos con una implementación para el uso promedio y nada para los otros casos ...

Por ejemplo, algunos mapas hash tienen repetición lineal, donde, en lugar de repetir todo el mapa hash a la vez, una parte es repetición en cada inserción, lo que ayuda a amortizar el costo.

Otro ejemplo: algunos mapas hash usan una lista simple de nodos para un grupo, otros usan un mapa, otros no usan nodos pero encuentran la ranura más cercana y, finalmente, algunos usarán una lista de nodos pero los reordenarán para que el último elemento accedido está en la parte delantera (como una cosa de almacenamiento en caché).

Así que en este momento tiendo a preferir std::map o quizás un loki::AssocVector (para conjuntos de datos congelados).

No me malinterpreten, me gustaría usar std::unordered_map y quizás en el futuro, pero es difícil "confiar" en la portabilidad de tal contenedor cuando piensa en todas las formas de implementarlo y en el Varias actuaciones que resultan de esto.