c++ - libreria - map programacion
Diferencia en el rendimiento entre el mapa y el mapa no ordenado en c++ (3)
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 el nuevo mapa desordenado propuesto de tr1. Encontré que al menos al analizar un archivo y crear el mapa, insertaba un elemento en el momento.
el mapa tomó solo 2 minutos, mientras que unordered_map tardó 5 minutos.
Como voy a ser parte de un código para ser ejecutado en el clúster de 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 rangos de enteros de 1,2, ... a ~ 10 millones.
También puedo imponer al usuario para que especifique el valor máximo y para utilizar el orden como se indicó anteriormente, ¿afectará esto de manera significativa mi implementación? (Escuché que el mapa se basa en árboles rb e insertar en orden creciente conduce a un mejor rendimiento (¿o peor?))
aquí está 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 revisar los comentarios y las respuestas, creo que una matriz Dynamic C ++ sería la mejor opción, ya que la implementación usará claves densas. Gracias
El tiempo extra que se carga el mapa no ordenado se debe al redimensionamiento dinámico de la matriz. 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());
La división por max_load_factor es para dar cuenta de las celdas vacías que son necesarias para que funcione la tabla hash.
La inserción de unordered_map debe ser O (1) y la recuperación debe ser aproximadamente O (1) , (es esencialmente una tabla hash).
Como resultado, sus horarios están DESACTIVADOS , o hay algo INCORRECTO con su implementación o uso de unordered_map.
Debe proporcionar más información y, posiblemente, cómo está utilizando el contenedor.
Según la sección 6.3 de n1836 se dan las complejidades para la inserción / retreiva:
Un problema que debe tener en cuenta es que su implementación puede necesitar volver a estructurar continuamente la estructura, ya que dice que tiene más de 100 elementos . 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 para el constructor y el contenedor se creará una instancia acorde con un contenedor. tabla de tamaño apropiado.
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 son ~ 10 millones de entradas en total, podría asignar una matriz lo suficientemente grande y obtener búsquedas realmente rápidas, suponiendo que hay suficiente memoria física como para no causar agallas, pero esa no es una gran cantidad de memoria para los estándares modernos.
Editar: sí, un vector es básicamente una matriz dinámica.
Edit2: El código que ha agregado algunos problemas. Tu while (! LabelFile.eof() ) está roto. Normalmente desea hacer algo como while (LabelFile >> inputdata) 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, escribiría el ciclo algo así como:
while (LabelFile >> node >> label)
Label[node] = label;