¿Por qué el mapa sería mucho más rápido que unordered_map?

Question

Implementé un resultado de caché de búsqueda que consiste en claves de tipo State (una clase con 7 entradas cortas) y valores de tipo Socre (una clase de 3 dobles). Usar unordered_map fue al menos 20 veces más lento que el mapa. ¿Por qué?

Edit: Darn it! Mi función hash era

namespace std { 
    size_t hash<State>::operator()(State const& s) const { 
     size_t retval = hash<short>()(s.s[0]); 
     for (int i = 1; i < R; i += 2) { // 1 3 5 
      int x = (static_cast<int>(s.s[i + 1]) << 16) 
       + (static_cast<int>(s.s[i])); 
      hash_combine(retval, x); 
     } 
    } 
} 

me olvidó return retval, así que todo era chocar! Deseo que unordered_map tenga una función hash_function_quality() que informa el número promedio de colisiones.

Answer 1

La velocidad de unordered_map es directamente proporcional a la velocidad de su función de hashing. Nunca es una relación directa. El caso en cuestión, si se utiliza la función hash simple:

std::size_t myHash(MyObjectType _object){ return 1; } 

entonces lo que va a terminar con una colección que se comporta como una lista en lugar de un contenedor de hash. Todos los elementos se asignarán a un solo cubo y tendrás que atravesar todo el cubo hasta llegar al elemento que deseas (algo que podría tomar el tiempo O (N))

Lo que debes hacer es mirar en dos cosas:

1. ¿Qué función de hashing está utilizando? ¿Cuesta una cantidad de tiempo ridícula procesar?
2. ¿Cuántas colisiones está produciendo? Es decir, ¿cuántos elementos únicos se asignan al mismo valor hash?

Cualquiera de los dos por sí solo puede matar el rendimiento.

Answer 2

std::unordered_map es generalmente lento para una pequeña cantidad de elementos debido a la función hash. Toma una cantidad fija (-ish) de tiempo, pero tal vez una cantidad significativa de tiempo, no obstante.

std::map por el contrario es más simple que std::unordered_map. El tiempo que lleva acceder a un elemento depende del recuento de elementos, pero cada vez menos a medida que crece la cantidad de elementos. Y el gran factor c para std :: map también es comúnmente muy pequeño, en comparación con std::unordered_map.

En general, prefiera usar std::map sobre std::unordered_map, a menos que tenga un motivo específico para usar std::unordered_map. Esto se aplica especialmente si no tiene una gran cantidad de elementos.

Answer 3

unordered_map usa una tabla hash debajo del capó, por lo que la razón más obvia por la cual el hash tiene un bajo rendimiento es porque tiene demasiadas colisiones. Puede considerar usar una función hash diferente, no predeterminada, que dará mejores resultados para su tipo de claves.

Answer 4

Para

Me gustaría unordered_map tenía una función hash_function_quality() que informa del número promedio de colisiones.

Creo que la siguiente función puede ser útil.

unordered_map::load_factor 
    float load_factor() const; 
The member function returns the average number of elements per bucket. 

Bajo el load_factor, mejor es la función hash.