Différence de performance entre la carte et unordered_map en c++
J'ai une simple exigence, j'ai besoin d'une carte de type . cependant j'ai besoin le plus rapide possible, en théorie, temps de récupération.
j'ai utilisé à la fois la carte et le nouveau projet de unordered_map de tr1
j'ai trouvé qu'au moins lors de l'analyse d'un fichier et la création de la carte, par l'insertion d'un élément à la fois.
carte n'a pris que 2 minutes, tout en unordered_map a pris 5 minutes.
Que je c'est faire partie d'un code destiné à être exécuté sur un cluster Hadoop et contiendra ~100 millions d'entrées, j'ai besoin de plus possible la durée de récupération.
Également une autre information utile:
actuellement les données (clés) qui est insérée est la gamme de nombres entiers compris entre 1,2,... à ~10 millions de dollars.
Je peut également imposer à l'utilisateur de spécifier la valeur maximum et d'utiliser la commande comme ci-dessus, est-ce que de manière significative l'effet de mon application? (j'ai entendu parler de la carte est basée sur rb arbres et de l'insertion dans l'ordre croissant conduit à une meilleure performance (ou pire?) )
voici le code
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();
}
Tentative de Solution: Après l'examen des commentaires et des réponses, je crois, une Dynamique en C++ tableau serait la meilleure option, car la mise en œuvre permettra d'utiliser dense clés. Grâce
Vous devez vous connecter pour publier un commentaire.
D'Insertion pour unordered_map devrait être O(1) et de récupération devrait être à peu près O(1), (ce qui est essentiellement une table de hachage).
Votre timings, en conséquence, de façon HORS, ou il ya quelque chose MAL avec votre mise en œuvre ou l'utilisation de unordered_map.
Vous devez fournir quelques informations, et éventuellement, la façon dont vous utilisez le conteneur.
Conformément à la section 6.3 de n1836 la complexité pour une insertion/extraction sont donnés:
Une question que vous devriez considérer est que votre application peut avoir besoin d'être constamment ressasser la structure, comme vous le dites vous avez 100mil+ articles. Dans ce cas, lors de l'instanciation du conteneur, si vous avez une idée approximative de combien de "uniques" éléments seront insérées dans le conteneur, vous pouvez passer qu'en tant que paramètre du constructeur et le conteneur sera instancié en conséquence avec un seau de table de taille appropriée.
Le temps de chargement de la unordered_map est due à la dynamique de la matrice de redimensionnement. Le redimensionnement de la planification est de doubler le nombre de cellules de chaque lorsque la table dépasse c'est le facteur de charge. Donc, à partir d'une table vide, attendez-O(lg n) exemplaires de l'ensemble des données de la table. Vous pouvez éliminer ces copies supplémentaires par le dimensionnement de la table de hachage à l'avance. Plus précisément
En divisant par le max_load_factor est de rendre compte des cellules vides qui sont nécessaires pour la table de hachage à utiliser.
unordered_map (au moins dans la plupart des implémentations) donne une récupération rapide, mais relativement pauvre insertion de vitesse par rapport à la carte. Un arbre est généralement à son meilleur lorsque les données sont ordonnés aléatoirement, et au pire lorsque les données sont commandées (vous constamment à l'insérer à une extrémité de l'arbre, l'augmentation de la fréquence de ré-équilibrage).
Étant donné que c'est ~10 millions d'entrées total, vous avez juste à allouer un assez grand tableau, et obtenir une recherche très rapide, en supposant que suffisamment de mémoire physique que cela ne cause pas de raclée, mais ce n'est pas une énorme quantité de mémoire par rapport aux normes modernes.
Edit: oui, un vecteur est essentiellement un tableau dynamique.
Edit2: Le code que vous avez ajouté quelques problèmes. Votre
while (! LabelFile.eof() )
est cassé. Normalement, vous voulez faire quelque chose commewhile (LabelFile >> inputdata)
à la place. Vous avez également la lecture des données quelque peu inefficace -- ce que vous apparemment attend est de deux nombres séparés par une tabulation. Cela étant le cas, je ferais la boucle quelque chose comme: