400390102. Contenedores de Hash en STL C++ y sus Prestaciones
Si estamos escribiendo aplicaciones comerciales, códigos back-end para sitios web, juegos, o prácticamente cualquier otra aplicación moderna, es probable que necesitemos tener acceso de forma rápida a grandes cantidades de datos y a realizar cálculos en base a dichos datos.
Por ejemplo, en Advertising.com tenemos que realizar con rapidez complejos cálculos matemáticos en base a enormes cantidades de datos que se hallan en la memoria, para así poder elegir los anuncios más pertinentes para mostrar a los visitantes del sitio web.
Existen, desde luego, muchas y distintas técnicas de perfilado y optimización que podemos utilizar una vez hemos completado la aplicación. Pero incluso aunque creamos que “la optimización prematura es la causa de todos los males”, conviene que empecemos a pensar lo antes posible en las prestaciones de la aplicación. ¿Por qué? Porque la elección correcta de las estructuras de datos es una decisión arquitectónica clave para las aplicaciones de prestaciones críticas.
Afortunadamente, para los programadores de C++, la Biblioteca de Plantillas Estándar de C++ ofrece una enorme cantidad de estructuras de datos que se usan con frecuencia y que se pueden incorporar fácilmente a la mayoría de los programas. Muchas de las estructuras de datos más sencillas son bien conocidas: Los intercambios de prestaciones entre vectores, listas enlazadas y colas se enseñan en los cursos de introducción a la ciencia de la computación.
Es también sencillo entender y usar contenedores asociativos clasificados como mapas y conjuntos sin saber lo que realmente contienen, especialmente si ha pasado algún tiempo desde la última vez que examinamos los detalles de los algoritmos de Árboles Rojos/Negros que normalmente los sustentan.
Pero la comprensión de los detalles de implementación y los intercambios en el diseño es fundamental para usar algunas de las estructuras más eficaces y potentes de datos que se encuentran disponibles en las distribuciones de STL —estructuras basadas en hash y que incluyen hash_map, hash_set, hash_multimap, y hash_multiset.
Aunque estas estructuras todavía no son parte del Estándar de C++, vienen incluidas en muchos paquetes de STL, incluida la versión SGI que se envía con la mayoría de las distribuciones de Linux. Se incluirán también en TR1 con los nombres ligeramente diferentes de unordered_map, unordered_multimap, unordered_set, y unordered_multiset. Los ejemplos que se incluyen en el presente artículo usan la implementación SGI STL. Pero incluso si utilizamos un STL distinto, es probable que las implementaciones sean similares.
Cada una de estas estructuras de datos ofrece una funcionalidad similar a sus equivalentes no basados en hash.
– hash_maps almacena parejas de clave/valor que tienen claves exclusivas.
– hash_sets almacena valores exclusivos.
– hash_multimaps almacena parejas de clave/valor con claves no exclusivas.
– hash_multisets almacena valores no exclusivos.
Con muchas aplicaciones, la velocidad que se obtiene al usar, por ejemplo, hash_maps en lugar de mapas normales es significativa. En teoría, los contenedores basados en hash pueden ofrecer inserción, eliminación y acceso en tiempo constante a cualquier valor que se halle en los contenedores. Por el contrario, los Árboles Rojos/Negros que alimentan los mapas, conjuntos, mapas y conjuntos múltiples de STL necesitan de un tiempo O(log n) para operaciones equivalentes.
Factores que influyen en las prestaciones
Pero los contenedores basados en hash no son una garantía, y el tiempo de reloj varía drásticamente dependiendo de la función hash empleada, el número de objetos almacenados en el contenedor, el tiempo que se tarda en comprobar los valores para la igualdad y otros factores. Saber como interactúan estos factores es esencial para aprovechar las mejoras en las prestaciones que ofrecen los contenedores de hash.
Para entender el efecto que cada uno de estos factores tiene en las prestaciones, hemos de entender cómo se implementan los contenedores basados en hash. Pensemos en los conjuntos de hash.
Los conjuntos de hash se pueden considerar como matrices de listados enlazados. Cada elemento de la matriz, denominado en la figura 1 como B0…B4, es un «cubo.» Cuando se inserta un nuevo elemento en el conjunto de hash, se computa el valor de hash del elemento. A continuación, se computa el número del cubo tomando el valor de hash mediante la factorización modular del número de cubos.
En la figura 1, el elemento A, cuyo valor hash es 7, se almacena en el cubo 2 (Valor de Hash de 7 factorización modular 5 cubos=cubo 2). Cuando invocamos find(A) para comprobar si el elemento A está en el conjunto de hash, el programa computa el valor hash de 7 para A, y busca en el cubo 2 para ver si A está allí. Como sólo hay un elemento en el cubo 2, es relativamente rápido.
Pero incluso aunque sólo haya un elemento en un cubo, find() sigue teniendo que comprobar si es el elemento en cuestión que buscamos, lo que conlleva una invocación a operator==. Si la comparación de igualdad es lenta, las prestaciones del contenedor de hash se degradan.
Figura 1: Elementos de la matriz
Supongamos ahora que insertamos otro elemento, el elemento Z, en el conjunto de hash. Si el elemento Z tiene un valor hash de 12, y no aumentamos el número de cubos en el conjunto de hash, en ese caso el elemento Z también termina en el cubo 2. (Figura 2). Cuando hay más de un elemento en un cubo de hash, find() puede hacerse más lento. Si invocamos find(Z), el programa busca de nuevo en el cubo 2, pero tiene que examinar primero el elemento A antes de ir al siguiente elemento de las lista enlazada, y de decirnos que Z está de hecho en nuestro conjunto hash. Afortunadamente, conforme va aumentando el número de elementos en nuestro conjunto de hash, aumenta también de forma automática el número de cubos. Eso reduce la posibilidad de que dos elementos con distintos valores de hash terminen en el mismo cubo.
Figura 2: Inserción de otro elemento en un conjunto de hash.
Pero, ¿qué pasa si teníamos muchos elementos con el mismo valor de hash, como en el listado número 1? Cuando dos elementos distintos se “reducen” (hash) al mismo valor, hay una “colisión hash”. Estos elementos siempre terminan en el mismo cubo, independientemente del número de cubos que tengamos, lo que degrada de forma significativa las prestaciones de la colección.
Si las colisiones de hash se producen con la suficiente frecuencia, el hallazgo de elementos en el contenedor se convierte de manera efectiva en O(n) en vez de O(1) porque tenemos que atravesar las listas enlazadas que forman los cubos de hash.
struct terribleHasher
size_t operator()(const myClass& myObj) const
return 1;
;
Listado número 1
Además de ser relativamente exclusivos, los valores hash deberían ser muy rápidos de computar. SGI STL ofrece algunas funciones hash básicas. La mayoría de los primitivos se reducen a sí mismos. integers, characters, y longs sencillamente se asignan todos ellos a size_t, que es el tipo de retorno para las funciones hash compatibles con STL. SGI STL incluye además funciones para reducir char*s (cadenas, por ejemplo) que iteran sobre cada carácter y aplican una sencilla fórmula recursiva.
El manejo de otros tipos sencillos es casi igual de fácil. Igual que con los primitivos, tiene sentido reducir (hash) cualquier cosa que se pueda asignar rápidamente y de forma exclusiva a un size_t, a su propio valor. Esta asignación es trivial y, por tanto, muy rápida. Puesto que obviamente es exclusivo, debería preferirse a otras funciones hash siempre que sea posible. Pero en lugar de volver a implementar este concepto de “hashing” para cada tipo que puede ser asignado a size_t, es mejor utilizar la plantilla del listado número 2.
template< typename T_TypeToHash >
struct SizeTCastHasher
size_t operator()( const T_TypeToHash& i_TypeToHash ) const
return size_t( i_TypeToHash );
;
Listado número 2
Un caso de uso para SizeTCastHasher es la reducción o “hashing” de un puntero. Supongamos, por ejemplo, que estamos escribiendo un programa para una empresa de publicidad en Internet. Tenemos una clase adFactory que crea objetos del tipo myAdvertisement. La clase de fábrica coloca también los anuncios en los sitios web invocando myWebsite.placeAd(); véase el listado número 3. El sitio web sigue la pista de los anuncios que se han colocado en dicho sitio colocando cada anuncio en un hash_set.
Como se crea cada myAdvertisement en una posición distinta dentro de la memoria, podemos utilizar la dirección del objeto myAdvertisement (el valor del puntero) como la clave para entrar en el mapa, y asignar el puntero a size_t cuando tengamos que calcular el valor hash de la clave. Indudablemente ello restringe de alguna forma la gestión de la memoria, ya que dos objetos idénticos situados en distintas posiciones dentro de la memoria no se reducirán al mismo valor.
Por consiguiente, hemos de asegurarnos de que sólo tengamos una copia en la memoria de un myAdvertisement dado. No obstante, a cambio de satisfacer esta restricción, la invocación de funciones de búsqueda como website.doWeShowAd() es ahora muy rápida porque la función hash es a la vez computacionalmente trivial y reduce cada objeto a un valor exclusivo.
class adFactory
...
myAdvertisement* createAd(TAdType adType)
myAdvertisement* newAd=new myAdvertisement(adType);
myWebsite* website=websiteFactory.getBestWebsite(newAd);
website.placeAd(newAd);
return newAd;
...
;
class website
public:
...
void placeAd(const myAdvertisement* const ad)
myAds.insert(ad);
bool doWeShowAd(myAdvertisement* ad) const
return myAds.find(ad)!=myAds.end();
...
private:
__gnu_cxx::hash_set< const myAdvertisement*, SizeTCastHasher< const myAdvertisement* > > myAds;
;
Listado número 3
Cuando diseñemos funciones hash para tipos más complejos, es importante saber lo más posible sobre los datos que utilizamos. La extensión y distribución de los datos es especialmente importante. Por ejemplo, supongamos que en la aplicación de anuncios, queremos saber cuantas personas vieron un anuncio dado, en un sitio web dado.
Una forma de realizarlo sería mediante un mapa de hash que reduzca un anuncio y un sitio web a un size_t. Supongamos ahora que cada anuncio y sitio web tiene un identificador exclusivo asociado al mismo.
Por ejemplo, podría ser un número de fila que nuestra aplicación asignó al anuncio o al sitio web cuando se cargaba desde una base de datos. En esa situación, queremos que el mapa de hash reduzca un par de enteros no asignados (el número de fila del anuncio y el sitio web) a otro entero no asignado.
Si asumimos que las identidades del sitio web y del anuncio son ambas más pequeñas que 216, en ese caso podemos empaquetar ambos identificadores a un único size_t sin que haya colisión hash. Eso es exactamente lo que hace ShiftedPairHasher (en el listado número 4).
struct ShiftedPairHasher
size_t operator()(std::pair
return (key.first << ( sizeof(unsigned int) * 8/2)) ^ key.second;
Listado número 4
Cómo funciona el código
Así es cómo funciona el código. Conceptualmente, estamos colocando key.first dentro de los 16 bits superiores de size_t y key.second en los 16 bits inferiores. Para ello, utilizamos el << operator de bits para trasladar key.first el número adecuado de bits a la izquierda. El número de bits a trasladar es la mitad del número de bits que hay en nuestro tipo de clave, y que calculamos con la fórmula sizeof(unsigned int)*8/2. A continuación, utilizamos ^, el operador XOR de bits, para poner key.second en la mitad inferior del valor hash. He elegido XOR en vez de OR porque si key.second aumenta a más de 16 bits, XOR produce valores hash que son más exclusivos que OR, ya que OR fija el bit nº17 en 1, para todos los valores de key.second que superan la cifra de 65536. ShiftedPairHasher es bastante rápido: Simplemente hace una operación de cambio a la izquierda y una operación XOR. El compilador optimiza sizeof(unsigned int)*8/2 a una constante en el tiempo de compilación. Este mismo concepto se puede ampliar si deseamos reducir más de dos valores, con simplemente cambiar cada valor el número adecuado de bits y a continuación utilizar XOR con los otros valores cambiados. Con los “hashers” adecuados, los contenedores de hash nos pueden dar un tiempo de acceso O(1). No obstante, incluso si somos capaces de crear unas funciones hash excelentes, hay ciertos casos en los que los contenedores que no han sido reducidos nos dan mejores prestaciones en tiempo de ejecución. Consideremos el caso en el que creamos un número enorme de contenedores que contienen sólo unos cuantos valores, y entonces sólo haremos unas cuantas búsquedas en cada contenedor (Listado número 5). Si tecleamos typedef TMap en un mapa normal en doMapBenchmark(), este programa tarda entorno a 5,9 segundos en ejecutarse (todos los tiempos se generaron en un Pentium 4 2.8 GHz). Pero si cambiamos TMap para que sea hash_map, ese mismo programa tarda 16,5 segundos. La razón de este aumento del 280% en el tiempo de ejecución está en cómo se asigna la memoria cuando la aplicación instancia mapas de hash y mapas.
#include
#include
#include
Noticias relacionadas
Programador Java con conocimientos de Scrum, el perfil IT más demandado para 2018
Workday amplía su set de herramientas de seguridad con Duo Security
El 71% de las empresas ya están utilizando metodologías Agile y la extensión de las prácticas de DEVOps entre ellas
Deja un comentario
Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *
Debes haber iniciado sesión para comentar una noticia.
Comentarios
No hay comentarios.