Diferencia en el rendimiento entre el mapa y unordered_map en C++

Question

Tengo un requisito simple, necesito un mapa de tipo. sin embargo, necesito el tiempo de recuperación teóricamente más rápido posible.

utilicé tanto el mapa como la nueva propuesta de unordered_map de tr1 encontré que al menos al analizar un archivo y crear el mapa, al insertar un elemento en el momento.

el mapa tomó solo 2 minutos, mientras que unordered_map tardó 5 minutos.

Como i va a ser parte de un código para ser ejecutado en el clúster Hadoop y contendrá ~ 100 millones de entradas, necesito el menor tiempo de recuperación posible.

También otra información útil: actualmente los datos (claves) que se insertan son de un rango de números enteros de 1,2, ... a ~ 10 millones.

También puedo imponer al usuario que especifique el valor máximo y que use el orden como se indicó anteriormente, ¿afectará esto significativamente a mi implementación? (Mapa que he oído se basa en árboles rb e insertar en orden creciente conduce a un mejor rendimiento (o peor)?)

Este es el código

map<int,int> Label // this is being changed to unordered_map 
fstream LabelFile("Labels.txt"); 


// Creating the map from the Label.txt 
if (LabelFile.is_open()) 
{ 
    while (! LabelFile.eof()) 
    {    
     getline (LabelFile,inputLine); 
     try 
     { 
      curnode=inputLine.substr(0,inputLine.find_first_of("\t")); 
      nodelabel=inputLine.substr(inputLine.find_first_of("\t")+1,inputLine.size()-1); 
      Label[atoi(curnode.c_str())]=atoi(nodelabel.c_str()); 
     } 
     catch(char* strerr) 
     { 
      failed=true; 
      break; 
     } 
    } 
    LabelFile.close(); 
} 

Solución provisional: Después de la revisión de los comentarios y respuestas, i creemos que una matriz Dynamic C++ sería la mejor opción, ya que la implementación usará claves densas. Gracias

Answer 1

inserción para unordered_map debe ser O (1) y recuperación debe ser aproximadamente O (1), (su esencialmente una tabla hash).

Sus tiempos como resultado están muy por OFF, o hay algo MAL con su aplicación o uso de unordered_map.

Debe proporcionar más información y, posiblemente, cómo está utilizando el contenedor.

De acuerdo con la sección 6.3 del n1836 las complejidades de inserción/retreival se dan:

• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf

Una cuestión que debe considerar es que su aplicación puede tener que estar continuamente rehashing la estructura, como dices tienes 100mil + artículos. En ese caso, al crear una instancia del contenedor, si tiene una idea aproximada de cuántos elementos "únicos" se insertarán en el contenedor, puede pasar eso como un parámetro al constructor y el contenedor se creará una instancia de acuerdo con una cubo de mesa de tamaño apropiado.

Answer 2

unordered_map (al menos en la mayoría de las implementaciones) proporciona una recuperación rápida, pero una velocidad de inserción relativamente baja en comparación con el mapa. Generalmente, un árbol está en su mejor momento cuando los datos se ordenan aleatoriamente, y en el peor momento cuando se ordenan los datos (inserta constantemente en un extremo del árbol, aumentando la frecuencia de reequilibrio).

Dado que se trata de ~ 10 millones de entradas totales, podría asignar una matriz lo suficientemente grande y obtener búsquedas realmente rápidas, suponiendo suficiente memoria física que no causara agitación, pero esa no es una gran cantidad de memoria estándares modernos.

Editar: sí, un vector es básicamente una matriz dinámica.

Edit2: El código que ha agregado algunos problemas. Su while (! LabelFile.eof()) está roto. Normalmente desea hacer algo como while (LabelFile >> inputdata) en su lugar. También está leyendo los datos de manera un tanto ineficiente: lo que aparentemente espera es dos números separados por una pestaña. Siendo ese el caso, me gustaría escribir el bucle algo como:

while (LabelFile >> node >> label) 
    Label[node] = label; 

Answer 3

El tiempo extra de cargar el unordered_map es debido a la matriz dinámica de cambio de tamaño. El calendario de cambio de tamaño es duplicar el número de celdas cada una cuando la tabla excede su factor de carga. Por lo tanto, desde una tabla vacía, espere O (lg n) copias de toda la tabla de datos. Puede eliminar estas copias adicionales al dimensionar la tabla hash por adelantado. Específicamente

Label.reserve(expected_number_of_entries/Label.max_load_factor()); 

dividiendo por el max_load_factor es para tener en cuenta las celdas vacías que son necesarias para la tabla hash para operar.