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

371

Una charla reciente sobre unordered_mapC ++ me hizo darme cuenta de que debería usarlo unordered_mappara la mayoría de los casos en los que lo usaba mapantes, debido a la eficiencia de la búsqueda ( O amortizado (1) versus O (log n) ). La mayoría de las veces utilizo un mapa, utilizo cualquiera into std::stringcomo tipo de clave; 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 encontraba ninguna razón para usar un std::mapover a std::unordered_mapen el caso de teclas con tipos simples: eché un vistazo a las interfaces y no encontré ninguna diferencias significativas que afectarían mi código.

De ahí la pregunta: ¿hay alguna razón real para utilizar std::mapsobre std::unordered_mapen el caso de los tipos simples como inte std::string?

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

Además, 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 casos donde la cantidad de las claves no son triviales (> 1 024).

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

Kornel Kisielewicz
fuente
22
Me gusta hacer esta pregunta en entrevistas: "¿Cuándo es mejor la clasificación rápida que la clasificación por burbuja?" La respuesta a la pregunta proporciona información sobre la aplicación práctica de la teoría de la complejidad y no solo las declaraciones en blanco y negro como O (1) es mejor que O (n) u O (k) es equivalente a O (logn), etc. ..
42
@Beh, creo que te referías a "cuándo es mejor ordenar burbujas que ordenar rápidamente": P
Kornel Kisielewicz
2
¿Sería un puntero inteligente una clave trivial?
thomthom
Este es uno de los casos en los que el mapa es el más ventajoso: stackoverflow.com/questions/51964419/…
anilbey

Respuestas:

399

No olvides que mapmantiene sus elementos ordenados. Si no puedes renunciar a eso, obviamente no puedes usarlo unordered_map.

Algo más a tener en cuenta es que unordered_mapgeneralmente usa más memoria. mapsolo tiene algunos indicadores de mantenimiento y memoria para cada objeto. Por el contrario, unordered_maptiene una gran matriz (estas pueden ser bastante grandes en algunas implementaciones), y luego memoria adicional para cada objeto. Si necesita tener en cuenta la memoria, mapdebería ser mejor, ya que carece de la gran matriz.

Entonces, si necesita una búsqueda de recuperación pura, diría que unordered_mapes 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 (medido, por supuesto) cuando se usa en unordered_maplugar de mapen una tabla de búsqueda de entidad principal.

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

GManNickG
fuente
3
Una cosa más sobre la propiedad de bloque de memoria grande (r) de unordered_map vs. map (o vector vs list), el montón de proceso predeterminado (hablando de Windows aquí) está serializado. Asignar bloques (pequeños) en grandes cantidades en una aplicación multiproceso es muy costoso.
ROAR
44
RA: Puede controlar eso con su propio tipo de asignador combinado con cualquier contenedor, si cree que es importante para cualquier programa en particular.
99
Si conoce el tamaño de la unordered_mapreserva y la reserva al principio, ¿todavía paga una multa de muchas inserciones? Digamos que solo está insertando una vez cuando creó la tabla de búsqueda, y luego solo leyó de ella.
thomthom
3
@thomthom Por lo que puedo decir, no debería haber penalización en términos de rendimiento. La razón por la que el rendimiento se ve afectado se debe al hecho de que si la matriz crece demasiado, hará una repetición de todos los elementos. Si llama a reserve, potencialmente volverá a mostrar los elementos existentes, pero si lo llama al principio, entonces no debería haber penalización, al menos de acuerdo con cplusplus.com/reference/unordered_map/unordered_map/reserve
Richard Fung
66
Estoy bastante seguro de que en cuanto a memoria es todo lo contrario. Suponiendo el factor de carga predeterminado de 1.0 para un contenedor desordenado: tiene un puntero por elemento para el depósito y un puntero por elemento para el siguiente elemento en el depósito, por lo tanto, termina con dos punteros más datos por cada elemento. Para un contenedor ordenado, por otro lado, una implementación típica de árbol RB tendrá: tres punteros (izquierda / derecha / padre) más un bit de color que debido a la alineación toma una cuarta palabra. Eso es cuatro punteros más datos por cada elemento.
Yakov Galka
126

Si desea comparar la velocidad de sus std::mape std::unordered_mapimplementaciones, se puede usar de Google sparsehash proyecto, que tiene un programa time_hash_map en cuando ellos. 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)
Blair Zajac
fuente
2
Parece que el mapa desordenado supera el mapa en la mayoría de las operaciones. Evento en la inserción ...
Michael IV
77
sparsehash ya no existe. Se ha eliminado o eliminado.
Usuario9102d82
1
@ User9102d82 He editado la pregunta para hacer referencia a un enlace de waybackmachine .
andreee
Solo para asegurarse de que otros noten también los otros números además del tiempo: esas pruebas se realizaron con objetos de 4 bytes / estructuras de datos, también conocido como int. Si almacena algo que requiere un hashing más pesado o es más grande (lo que hace que las operaciones de copia sean más pesadas), ¡el mapa estándar podría tener una ventaja rápidamente!
AlexGeorg
82

Hago eco aproximadamente del mismo punto que GMan hizo: dependiendo del tipo de uso, std::mappuede ser (y a menudo es) más rápido que std::tr1::unordered_map(usando 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 el comienzo de una clave para distinguir entre las ramas secundarias 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 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 el número de elementos). Con cadenas largas como llaves, una std::mappodría terminar una búsqueda antes de una unordered_mapsiquiera comenzar 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 ellos son bastante lentos, 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 sobre su pregunta anterior, también puede usar una tabla de árboles. Esto tiene ventajas y 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 hice) 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 generalmente más rápida.

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

Jerry Coffin
fuente
2
El cambio de tamaño del hash puede ser amortiguado por las dynamic hashingtécnicas, que consisten en tener un período de transición en el que cada vez que inserta un elemento, también vuelve a mostrar kotros elementos. Por supuesto, significa que durante la transición tienes que buscar 2 tablas diferentes ...
Matthieu M.
2
"Con cadenas largas como teclas, un std :: map podría finalizar una búsqueda antes de que un_ororped_map incluso comience su búsqueda". - si la clave no está presente en la colección. Si está presente, entonces, por supuesto, se debe comparar la longitud total para confirmar la coincidencia. Pero también unordered_mapdebe confirmar una coincidencia hash con una comparación completa, por lo que todo depende de las partes del proceso de búsqueda que esté contrastando.
Steve Jessop
2
Por lo general, puede reemplazar la función hash en función del conocimiento de los datos. por ejemplo, si sus cadenas largas varían más en los últimos 20 bytes que en los primeros 100, simplemente
divida
56

Me intrigó la respuesta de @Jerry Coffin, que sugirió que el mapa ordenado exhibiría aumentos de rendimiento en cadenas largas, después de un poco de experimentación (que se puede descargar desde pastebin ), descubrí que esto solo parece ser cierto para las colecciones de cadenas aleatorias, cuando el mapa se inicializa con un diccionario ordenado (que contiene palabras con cantidades considerables de superposición de prefijos), esta regla se rompe, presumiblemente debido a la mayor profundidad del á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
Gearoid Murphy
fuente
2
Gracias por la prueba Para asegurarme de que no estamos midiendo el ruido, lo cambié para hacer cada operación muchas veces (e inserté el contador en lugar de 1 en el mapa). Lo ejecuté en un número diferente de teclas (de 2 a 1000) y hasta ~ 100 teclas en el mapa, std::mapgeneralmente supera std::unordered_map, especialmente para las teclas enteras, pero ~ 100 teclas parece que pierde su ventaja y std::unordered_mapcomienza a ganar. Insertar una secuencia ya ordenada en una std::mapes muy mala, obtendrá el peor de los casos (O (N)).
Andreas Magnusson
30

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

Busque el artículo de Wikipedia en el mapa hash. Dependiendo de la implementación utilizada, 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 incorporación de unordered_mapSTL: tendrán que elegir una implementación particular, ya que dudo que sigan adelante Policy, por lo que nos quedaremos atrapados con una implementación para el uso promedio y nada para los otros casos ...

Por ejemplo, algunos mapas hash tienen rehashing lineal, donde en lugar de volver a rehacer todo el mapa hash a la vez, se repite 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 la ranura más cercana y, por último, algunos usarán una lista de nodos pero la reordenarán para que el último elemento accedido está en la parte delantera (como una cosa de almacenamiento en caché).

Entonces, en este momento, tiendo a preferir el std::mapo quizás un loki::AssocVector(para conjuntos de datos congelados).

No me malinterpreten, me gustaría usarlo std::unordered_mapy podría 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 las diversas actuaciones que resultan de esta.

Matthieu M.
fuente
17
+1: punto válido - la vida era más fácil cuando estaba usando mi propia implementación - al menos sabía dónde apestaba:>
Kornel Kisielewicz
25

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

  • mapmantiene los iteradores a todos los elementos estables, en C ++ 17 incluso puede mover elementos de uno mapa otro sin invalidar los iteradores (y si se implementa correctamente sin ninguna asignación potencial).
  • map Los tiempos para operaciones individuales son típicamente más consistentes ya que nunca necesitan grandes asignaciones.
  • unordered_mapel uso std::hashimplementado en libstdc ++ es vulnerable a DoS si se alimenta con una entrada no confiable (usa MurmurHash2 con una semilla constante; no es que la siembra realmente ayude, consulte https://emboss.github.io/blog/2012/12/14/ romper-murmullo-hash-flooding-dos-reloaded / ).
  • Ser ordenado permite búsquedas de rango eficientes, por ejemplo, iterar sobre todos los elementos con la tecla ≥ 42.
usuario1531083
fuente
14

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 sus datos; así que si no planeo mirar una función hash personalizada (pero ciertamente puedo cambiar de opinión más tarde, y fácilmente ya que escribo bastante cerca de todo) y aunque los valores predeterminados se eligen para funcionar decentemente para muchas fuentes de datos, encuentro el pedido la naturaleza del mapa es suficiente para ayudar inicialmente, que todavía prefiero asignar en lugar de una tabla hash en ese caso.

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


fuente
@Roger, ¿sabes la cantidad aproximada de elementos en los que unordered_map supera el mapa? Probablemente escribiré una prueba para ello, de todos modos ... (+1)
Kornel Kisielewicz
1
@Kornel: No se necesitan muchos; mis pruebas fueron con alrededor de 10,000 elementos. Si queremos un gráfico realmente preciso, puede mirar una implementación de mapuna unordered_map, con cierta plataforma y cierto tamaño de caché, y hacer un análisis complejo. : P
GManNickG
Depende de los detalles de implementación, los parámetros de ajuste en tiempo de compilación (fácil de soportar si está escribiendo su propia implementación) e incluso la máquina específica utilizada para las pruebas. Al igual que para los otros contenedores, el comité solo establece los requisitos generales.
13

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

Las operaciones std :: map (árbol binario balanceado) se amortizan O (log n) y el peor de los casos O (log n). Las operaciones std :: unordered_map (tabla hash) se amortizan O (1) y el peor de los casos O (n).

Lo que sucede en la práctica es que la tabla hash "tiene hipo" 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.

Don Hatch
fuente
12

Resumen

Asumir que el pedido 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, úsela std::map. Esto es porque las lecturas son O(log n).
  • Si va a cambiar mucho la tabla, entonces puede ser std::map una buena opción.
  • Si tiene dudas, solo use std::unordered_map.

Contexto histórico

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

Se cree ampliamente 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 toneladas de cosas de qué hablar. Entonces, para evitar bloqueos en la estandarización, simplemente se llevaron bien con 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 nuevas std::unordered_map. En un mundo perfecto, std::maphabría sido desordenado y tendríamos std::ordered_mapcomo tipo separado.

Actuación

A continuación, dos gráficos deben hablar por sí mismos ( fuente ):

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Shital Shah
fuente
Datos interesantes ¿Cuántas plataformas incluiste en tus pruebas?
Toby Speight el
1
¿por qué debería usar std :: map para una tabla pequeña cuando hago muchas consultas ya que std :: unordered_map siempre funciona mejor que std :: map de acuerdo con las 2 imágenes que publicaste aquí?
ricky
El gráfico muestra el rendimiento para 0.13M o más elementos. Si tiene elementos pequeños (pueden ser <100), entonces O (log n) podría volverse más pequeño que el mapa desordenado.
Shital Shah
10

Hice una prueba recientemente que hace 50000 fusionar y ordenar. Eso significa que si las teclas 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 mapimplementación, se requieren 200 ms para finalizar el trabajo. Para el unordered_map+ map, se requieren 70 ms para la unordered_mapinserción y 80 ms para la mapinserción. Entonces, la implementación híbrida es 50 ms más rápida.

Deberíamos pensarlo dos veces antes de usar el map. Si solo necesita ordenar los datos en el resultado final de su programa, una solución híbrida puede ser mejor.

Wendong
fuente
0

Pequeña adición a todo lo anterior:

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

Denis Sablukov
fuente
-1

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

"Internamente, los elementos en un mapa siempre se ordenan por su clave siguiendo un criterio de orden 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 desordenados para acceder a elementos individuales por su clave, pero permiten la iteración directa en subconjuntos según su orden ".

Kunal Bansal
fuente