¿Hay alguna ventaja de usar map sobre unordered_map en caso de claves triviales?

Una conversación reciente sobre unordered_map en C ++ me hizo darme cuenta de que debería usar unordered_map para la mayoría de los casos en los que utilicé el map anteriormente, debido a la eficiencia de la búsqueda ( O (1) amortizado frente a O (log n) ). La mayoría de las veces que utilizo un mapa utilizo int ‘s o std::strings como claves, por lo tanto, no tengo problemas con la definición de la función hash. Cuanto más pensaba en ello, más me daba cuenta de que no podía encontrar ningún motivo para usar un std::map en el caso de tipos simples sobre un std::map unordered_map . unordered_map un vistazo a las interfaces y no lo hice. encuentre cualquier diferencia significativa que pueda afectar mi código.

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

Pregunto desde un punto de vista estrictamente de progtwigció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 menor (¿es eso cierto?) – por lo tanto, me gustaría restringir la pregunta a los casos donde 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.

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

Otra cosa a tener en cuenta es que los unordered_map generalmente usan más memoria. Un map solo tiene algunos indicadores de mantenimiento de la casa y luego memoria para cada objeto. Por el contrario, unordered_map tiene una gran matriz (estos pueden ser bastante grandes 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 matriz grande.

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

Solo por experiencia personal, encontré una enorme mejora en el rendimiento (medida, por supuesto) al usar un map no unordered_map lugar de un map en una tabla de búsqueda de entidades principales.

Por otro lado, descubrí que era mucho más lento al insertar y eliminar elementos repetidamente. Es ideal para una colección de elementos relativamente estática, pero si estás haciendo toneladas de inserciones y eliminaciones, el hashing + el agrupamiento parece sumrse. (Tenga en cuenta que esto fue en muchas iteraciones).

Si desea comparar la velocidad de las implementaciones std :: map y std :: unordered_map, puede usar el proyecto sparsehash de Google, que tiene un progtwig time_hash_map para medir el tiempo. Por ejemplo, con gcc 4.4.2 en un sistema Linux x86_64

 $ ./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) 

Me gustaría repetir más o menos el mismo punto que hizo GMan: según el tipo de uso, std::map puede ser (y a menudo 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á comparando claves, lo que significa que solo mira lo suficiente del comienzo de una tecla para distinguir entre las twigs secundarias derecha e izquierda del árbol. En mi experiencia, casi la única vez que miras una clave completa es si estás usando algo como int que puedes comparar en una sola instrucción. Con un tipo de clave más típico como std :: string, a menudo solo se comparan unos pocos caracteres.

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

En segundo lugar, si bien existen varios métodos para cambiar el tamaño de las tablas hash, la mayoría de ellas son bastante lentas, hasta el 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 su pregunta anterior, también puede usar una tabla de árboles. Esto tiene ventajas y desventajas. Por un lado, limita el peor caso al de un árbol. También permite la inserción y eliminación rápida, porque (al menos cuando lo he hecho) he utilizado una tabla de tamaño fijo. Eliminar 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.

Editar: Vaya, casi me olvido de mencionar otro punto: los requisitos para hash y mapas basados ​​en árboles son diferentes. Evidentemente, Hashing requiere una función hash y una comparación de igualdad, donde los mapas ordenados requieren una comparación menor que. Por supuesto, el híbrido que mencioné requiere ambos. Por supuesto, para el caso común de utilizar una cadena como clave, esto no es realmente un problema, pero algunos tipos de teclas se adaptan mejor que hashing (o viceversa).

Estaba intrigado por 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 encontrado que esto solo parece ser cierto para las colecciones de cadenas aleatorias, cuando el mapa se inicializa con un diccionario ordenado (que contienen palabras con cantidades considerables de superposición de prefijos), esta regla se descompone, presumiblemente 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 búsqueda.

 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 

Solo señalaría que … hay muchos tipos de unordered_map .

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

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

Por ejemplo, algunos mapas hash tienen un reajuste lineal, en el que en lugar de volver a procesar todo el mapa hash a la vez, se vuelve a aplicar una porció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 cubo, otros usan un mapa, otros no usan nodos pero encuentran el espacio más cercano y por último algunos usarán una lista de nodos pero lo reordenarán para que el último elemento al que se accedió está en la parte frontal (como una cosa de almacenamiento en caché).

Por lo tanto, en este momento tiendo a preferir el std::map o quizás un loki::AssocVector (para conjuntos de datos congelados).

No me malinterpreten, me gustaría usar std::unordered_map y puedo hacerlo en el futuro, pero es difícil “confiar” en la portabilidad de dicho contenedor cuando se piensa en todas las formas de implementarlo y varias actuaciones que resultan de esto.

Las tablas hash tienen constantes más altas que las implementaciones de mapas comunes, que se vuelven significativas 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 de siempre, pero O (log n) está cerca de O (k). (Recuerde que la complejidad logarítmica sigue siendo realmente buena).

Lo que hace que una buena función hash dependa de las características de tus datos; así que si no planeo mirar una función hash personalizada (pero puedo cambiar de opinión más adelante, y fácilmente ya que defino casi todo) y aunque los valores predeterminados son elegidos para funcionar decentemente para muchas fonts de datos, encuentro el orden la naturaleza del mapa es suficiente como una ayuda al principio, por lo que todavía prefiero mapear en lugar de una tabla hash en ese caso.

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

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

  • map mantiene iteradores estables a todos los elementos, en C ++ 17 incluso puede mover elementos de un map a otro sin invalidar los iteradores invalidantes para ellos (y si se implementa correctamente sin ninguna asignación potencial).
  • map tiempos del 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 una entrada que no es de confianza (utiliza MurmurHash2 con una semilla constante – no esa siembra realmente ayudaría, consulte https://emboss.github.io/blog/2012) / 12/14 / breaking-murmur-hash-flooding-dos-reloaded / ).
  • Ser ordenado permite búsquedas de rango eficientes, por ejemplo, iterar sobre todos los elementos con la tecla> = 42.

Recientemente hice una prueba que hace 50000 fusionar y ordenar. Eso significa que si las claves de cadena son las mismas, combine la cadena de bytes. Y el resultado final debe ser ordenado. Entonces esto incluye una búsqueda para cada inserción.

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

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

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

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

Cómo esto se desarrolla en la práctica es que la tabla hash “hipo” de vez en cuando con una operación O (n), que puede o no ser algo que tu aplicación puede tolerar. Si no puede tolerarlo, preferiría std :: map over std :: unordered_map.

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

En general, se cree que C ++ terminó con un 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 muchísimas cosas de qué hablar. Por lo tanto, para evitar las retenciones en la estandarización, se llevan bien con el mapa ordenado. Alrededor de 2005, muchos lenguajes ya tenían buenas implementaciones de la implementación basada en hash y, por lo tanto, era más fácil para el comité aceptar el nuevo std::unordered_map . En un mundo perfecto, std::map habría sido desordenado y tendríamos std::ordered_map como tipo separado.

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

enter image description here

enter image description here

Resumen

Suponiendo que ordenar no es importante:

  • Si va a construir 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 ser std::map es una buena opción.
  • Si tiene dudas, solo use std::unordered_map .

Pequeña adición a todo lo anterior:

Utilice mejor el map , cuando necesite obtener elementos por rango, ya que están ordenados y puede iterar sobre ellos de un límite a otro.

De: 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 Comparación).

los contenedores de mapas generalmente son 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 en función de su orden “.