how - map values c++
Inserción de mapa C++ y rendimiento de búsqueda y sobrecarga de almacenamiento (8)
Me gustaría almacenar una asignación de una clave integer a un valor float en memoria.
Tengo aproximadamente 130 millones de llaves (y, en consecuencia, 130 millones de valores).
Mi enfoque está en el rendimiento de búsqueda, tengo que hacer muchos, muchos millones de búsquedas.
La biblioteca STL de C ++ tiene una clase de map para matrices asociativas de este tipo. Tengo varias preguntas sobre el map .
¿Cuál es la sobrecarga de almacenamiento del map para un conjunto de datos del tamaño mencionado anteriormente? ¿Cómo escala de gastos generales de almacenamiento, en general, con el map ?
Parece que la estructura de datos subyacente para el map es un árbol binario equilibrado rojo-negro. Parece que el performance mundo real para esto es O(log n) para la inserción y recuperación.
Menciona O(1) para una inserción insinuada. Mi entrada está pre-ordenada, por lo que creo que debería poder proporcionar una sugerencia para los eventos de inserción. ¿Cómo puedo proporcionar esta sugerencia, utilizando los métodos que se enumeran here ?
¿Hay un contenedor STL que ofrezca un mejor rendimiento de búsqueda?
¿Existen otros marcos de código abierto, disponibles públicamente, con una clase de matriz asociada que use una estructura de datos subyacente que funcionaría mejor que el map STL?
Si escribir mi propia clase de contenedor proporcionaría un mejor rendimiento de búsqueda, ¿qué estructuras de datos podría investigar?
Estoy usando GCC 4 para esta tarea, corriendo bajo Linux o Mac OS X.
Pido disculpas por adelantado si estas son preguntas tontas. Gracias por tu consejo.
Como respuesta parcial a su pregunta sobre el rendimiento de búsqueda, debe considerar su patrón de inserción . Notó que std::map usa un árbol rojo-negro como cobertura contra la linealización de una inserción cuidadosamente ordenada en una lista vinculada. Por lo tanto, dicho árbol proporciona O (log n) tiempo de búsqueda a pesar de un orden de inserción aberrante. Usted paga un costo por esto, sin embargo, en la inserción, eliminación y rendimiento transversal, además de perder la localidad de referencia para la lectura repetida de datos "cercanos".
Una tabla hash puede ofrecer una búsqueda más rápida si puede ajustar una función hash para su tipo de clave (un entero, digamos) que excluirá las colisiones. Si su conjunto de datos fue arreglado, de modo que pudiera cargarlo una vez y solo leerlo después, podría usar matrices paralelas de enteros y flotantes, y usar std::lower_bound para encontrar su coincidencia mediante la búsqueda binaria. Ordenar las matrices paralelas correctamente sería una tarea, si sus claves están divorciadas de sus valores correspondientes, pero disfrutaría de un almacenamiento y una localidad de referencia más estrictos que almacenar una matriz de, por ejemplo, std::pair .
La mayoría de los compiladores se envían con un hash_map (o hash_map ) no estándar (pero en funcionamiento) que podría ser más rápido para usted. Viene en C ++ 0x (está en tr1) y también está (como siempre) en boost .
GCC también lo hizo, pero no he hecho C ++ en eso durante 12 años, pero aún debería estar allí en algún lugar.
Puede echar un vistazo a std :: tr1 :: unorderd_map.
Pero si tiene claves enteras sin signo de 32 bits (4294967296 valores posibles) y 130 millones de claves diferentes, debe escribir su propio contenedor optimizado para esta tarea. Especialmente si el caso clave de 130 millones es el caso habitual (y no solo un máximo raro).
4294967296/130000000 = 33, por lo que aproximadamente cada número 33 en todo el espacio se utiliza en sus datos.
Por ejemplo, podría dividir su rango de claves en particiones de tamaño fijo. Si las claves están distribuidas de manera bastante uniforme, debe dividir el espacio de la clave en, por ejemplo, cubos de tamaño 256 o incluso cubos de tamaño 32, dependiendo de la cantidad de almacenamiento que desee desperdiciar cuando solo se almacenan unos pocos valores.
Ejemplo, para darte una idea:
#define BUCKET_SIZE 256
#define BUCKET_SIZE_SHIFT 8
struct Bucket {
uint32_t key;
float value;
Bucket* pNext;
};
Bucket data[ 4294967296 / BUCKET_SIZE ];
Bucket* find( uint32_t key ) {
uint32_t bucket_index = key / BUCKET_SIZE;
// or faster: uint32_t bucket_index = key >> BUCKET_SIZE_SHIFT;
Bucket* pBucket = &data[ bucket_index ];
while( pBucket ) {
if( pBucket->key == key ) return pBucket;
pBucket = pBucket->pNext;
}
return NULL;
}
Si su entrada está ordenada, debe probar solo un vector y una búsqueda binaria (es decir, lower_bound() ). Esto podría resultar adecuado (también es O (log n)). Dependiendo de la distribución de sus claves y la función hash utilizada, un hash_map también podría funcionar. Creo que esto es tr1::unordered_map en gcc.
Si sus llaves no cambian, podría considerar una función hash perfecta como alternativa a un contenedor estándar.
No sé en qué obstáculos se encontrará con un conjunto de datos de ese tamaño, pero podría valer la pena dedicar unos minutos a experimentar.
Teniendo en cuenta la gran cantidad de memoria utilizada, también debe tener en cuenta que cualquier acceso a la memoria en la búsqueda dará como resultado un error en la memoria caché.
En este sentido, una solución mixta de un pequeño hashmap como primera capa y vectores ordenados para los cubos es probablemente la mejor.
La idea es mantener el índice de tabla hash en la memoria caché y buscar en contenedores ordenados más pequeños para reducir el número de fallas de caché.
Teniendo en cuenta lo que has dicho, me gustaría mucho usar un std::vector<pair<int, float> > , y usar std::lower_bound , std::upper_bound y / o std::equal_range para buscar hasta los valores.
Si bien la sobrecarga exacta de std::map puede (y lo hace) variar, hay poco o ningún espacio para cuestionar que normalmente consumirá más memoria y buscará valores más lentamente que una búsqueda binaria en un vector. Como se ha señalado, normalmente (y casi inevitablemente) se implementa como una especie de árbol equilibrado, que impone una sobrecarga para los punteros y la información de balanceo, y generalmente significa que cada nodo también se asigna por separado. Dado que sus nodos son bastante pequeños (normalmente 8 bytes), es probable que los datos adicionales sean al menos tanto como lo que realmente está almacenando (es decir, al menos un 100% de gastos generales). Las asignaciones separadas a menudo significan una mala localidad de referencia, lo que conduce a un uso inadecuado de la memoria caché.
Edición: Observando solo las implementaciones de std::map , probablemente vale la pena señalar que la mayoría usa un árbol rojo-negro. Si iba a usar un std::map , una implementación que use un árbol AVL probablemente se adaptaría mejor a sus propósitos: un árbol AVL tiene restricciones ligeramente más estrictas para el equilibrio. Esto proporciona una búsqueda ligeramente más rápida a expensas de una inserción y eliminación ligeramente más lentas (ya que tiene que volver a equilibrarse con más frecuencia para mantener su interpretación más estricta de "equilibrado"). Sin embargo, mientras sus datos permanezcan constantes durante el uso, un std::vector es probablemente mucho mejor.
Otra posibilidad que vale la pena mencionar: si sus claves están al menos distribuidas de manera equitativa, puede intentar buscar mediante interpolación en lugar de bisección. es decir, en lugar de comenzar siempre en la mitad del vector, realiza una interpolación lineal para adivinar el punto de inicio más probable para la búsqueda. Por supuesto, si sus claves siguen una distribución no lineal conocida, puede utilizar una interpolación correspondiente.
Edición 2: Suponiendo que las claves están razonablemente distribuidas, la búsqueda de interpolación tiene una complejidad de O (registro log N). Para 130 millones de teclas, eso equivale a alrededor de 4 sondas para encontrar un artículo. Para hacerlo significativamente mejor que eso con el hash (normal / no perfecto), necesita un buen algoritmo, y debe mantener el factor de carga en la tabla alrededor del 75% aproximadamente, es decir, debe permitir algo así como 32 millones Puntos extra (vacíos) en su mesa para mejorar la complejidad esperada de cuatro sondas a tres. Puede que sea un poco anticuado, pero eso me parece una gran cantidad de almacenamiento adicional para usar en una mejora de velocidad tan pequeña.
OTOH, es cierto que esta es casi la situación ideal para el hashing perfecto: el conjunto se conoce con anticipación y la clave es bastante pequeña (importante, ya que el hashing normalmente es lineal en el tamaño de la clave). Aun así, a menos que las claves se distribuyan de forma bastante desigual, no esperaría ninguna mejora enorme: una función hash perfecta es a menudo (¿en general?) Bastante compleja.
Un vector absolutamente va a matar un mapa aquí, asumiendo que no es necesario hacer inserciones en el medio del vector. Escribí un asignador personalizado para rastrear el uso de la memoria, y aquí están los resultados en Visual Studio 2005:
std::map<int, float>:
1.3 million insertions
Total memory allocated: 29,859 KB
Total blocks allocated: 1,274,001
Total time: 17.5 seconds
std::vector<std::pair<int, float> >:
1.3 million insertions
Total memory allocated: 12,303 KB
Total blocks allocated: 1
Total time: 0.88 seconds
std :: map utiliza más del doble del almacenamiento y tarda 20 veces más en insertar todos los elementos.