¿Cómo elegir entre mapa y mapa desordenado?
Supongamos que quisiera asignar datos con una cadena como clave.
¿Qué contenedor debería haber elegido, map o unordered_map? unordered_map ocupa más memoria, así que supongamos que la memoria no es un problema, y la preocupación es la velocidad.
unordered_map debe dar generalmente complejidad media de O(1) con el peor caso de O (n).
¿En qué casos llegaría a O (n)?
¿Cuándo un map es más eficiente en el tiempo que unordered_map? ¿Sucede cuando n es pequeña?
Asumiendo que usaría STL unordered_map con el haser por defecto Vs. asignar. la cuerda es la clave.
Si voy a iterar sobre los elementos en lugar de acceder a un elemento individual cada vez, ¿debería preferir map?
4 answers
En la práctica, si la memoria no es un problema, unordered_map siempre es más rápido si desea acceso a un solo elemento.
El peor de los casos es teórico y está ligado a un único hash que da cuenta de todos los elementos. Esto no tiene importancia práctica. unordered_map se vuelve más lento tan pronto como tenga al menos elementos log N pertenecientes al mismo hash. Esto tampoco tiene importancia práctica. En algunos escenarios especiales, podría usar un algoritmo de hash específico que garantice una distribución más uniforme. Para cadenas ordinarias que no comparten un patrón específico, las funciones hash genéricas que vienen con unordered_map son igual de buenas.
Si desea recorrer el mapa (utilizando iteradores) de manera ordenada, no puede usar unordered_map. Por el contrario, map no solo permite eso, sino que también puede proporcionarle el siguiente elemento en un mapa basado en una aproximación de la clave (ver métodos lower_bound y upper_bound).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-31 09:55:51
| map | unordered_map
---------------------------------------------------------
element ordering | strict weak | n/a
| |
common implementation | balanced tree | hash table
| or red-black tree|
| |
search time | log(n) | O(1) if there are no hash collisions
| | Up to O(n) if there are hash collisions
| | O(n) when hash is the same for any key
| |
Insertion time | log(n)+rebalance | Same as search
| |
Deletion time | log(n)+rebalance | Same as search
| |
needs comparators | only operator < | only operator ==
| |
needs hash function | no | yes
| |
common use case | when good hash is| In most other cases.
| not possible or |
| too slow. Or when|
| order is required|
¿Qué contenedor debería haber elegido, map o unordered_map? unordered_map ocupa más memoria así que supongamos que la memoria no es un problema, y la preocupación es la velocidad.
Perfil y luego decidir. unordered_map es generalmente más rápido, pero varía según el caso.
¿En qué casos llegaría a O(n)?
Cuando el hashing no es bueno y un montón de elementos están siendo asignados a los mismos contenedores.
¿Cuándo un mapa es más eficiente en el tiempo que unordered_map? ¿Sucede cuando n es pequeño?
Probablemente no, pero de perfil se si realmente te importa. Tener un contenedor con un tamaño pequeño sea el cuello de botella de su programa parece extremadamente improbable. De todos modos, un simple vector con búsqueda lineal puede ser más rápido para tales casos.
Lo más importante a la hora de decidir son los requisitos de ordenar y la falta de invalidación del iterador. Si necesitas cualquiera de los dos, tienes que usar map. De lo contrario, unordered_map.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-12-10 11:09:10
¿En qué casos llegaría a O(n)?
Si tiene una función hash mala que produce el mismo valor hash para todos los stirngs de entrada (es decir, produce colisiones)...
¿Qué contenedor debería haber elegido, map o unordered_map?
Siempre son las preguntas de requisitos y tipo/cantidad de datos que tiene.
¿Cuándo un mapa es más eficiente en el tiempo que unordered_map?
Es simplemente diferente estructura. Es mejor hacer una elección para usar uno de ellos dependiendo de sus casos de uso típicos (teniendo en cuenta qué tipo de datos tiene y su cantidad)
¿hppaen cuando n es pequeño?
En caso de pequeña cantidad de datos, todo depende de la implementación de STL en particular... Así que a veces incluso un vector/matriz simple podría ser más rápido que los contenedores asociativos...
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-12-10 11:07:04