Leistungsunterschied zwischen map und unordered_map in C ++

Habe ich eine einfache Anforderung, ich brauche eine Karte von Typ . aber ich brauche schnellsten theoretisch möglichen Ladezeiten.

ich habe sowohl die Karte und der neu vorgeschlagenen unordered_map aus tr1
ich fand, dass zumindest während der Analyse einer Datei und erstellen Sie die Karte, indem Sie ein element zu einem Zeitpunkt.

Karte dauerte nur 2 Minuten, während unordered_map dauerte 5 Minuten.

Als ich es ist Teil der code ausgeführt werden kann auf Hadoop-cluster und enthält ~100 Millionen Einträge, ich brauche kleinstmöglichen Ladezeiten.

Auch andere nützliche Informationen:
derzeit werden die Daten (keys), die eingefügt ist in den Bereich von ganzen zahlen aus 1,2,... , ~10 Millionen.

Kann ich auch verhängen Benutzer angeben, max-Wert und zu verwenden, um wie oben beschrieben, wird deutlich, dass Wirkung meine Umsetzung? (ich hörte Karte basiert auf rb Bäume und einfügen in aufsteigender Reihenfolge führt zu einer besseren Leistung (oder schlimmsten?) )

hier ist der 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(); 
}

Vorläufige Lösung: Nach überprüfung der Kommentare und Antworten, ich glaube, eine Dynamische C++ - Arrays wäre die beste option, da die Umsetzung verwenden dichter Schlüssel. Dank

InformationsquelleAutor der Frage | 2010-02-28

  1. 10

    Insertion für unordered_map sollte O(1) und Abfrage sollte ungefähr O(1), (es ist im wesentlichen eine hash-Tabelle).

    Ihre timings als Ergebnis sind Sie Weg AUS, oder es ist etwas FALSCH mit der Implementierung oder der Nutzung von unordered_map.

    Müssen Sie einige weitere Informationen, und eventuell wie Sie mit dem container.

    Gemäß Abschnitt 6.3 der n1836 die Komplexität für einfügen/retreival sind gegeben:

    Einem Problem, das Sie berücksichtigen sollten ist, dass Ihre Durchführung möglicherweise brauchen, um ständig Aufwärmen die Struktur, wie Sie sagen, Sie haben 100mil+ items. In diesem Fall muss bei der Instanziierung des Behälters, wenn Sie haben eine grobe Idee, wie viele "einzigartige" Elemente werden eingefügt in die container, die Sie übergeben können, die als parameter an den Konstruktor und den container instanziiert werden entsprechend mit einem Eimer-Tabelle der entsprechenden Größe.

    InformationsquelleAutor der Antwort

  2. 2

    Die zusätzliche Zeit laden die unordered_map ist durch das dynamische array-Größe. Die Größe Zeitplan ist um die doppelte Anzahl an Zellen pro, wenn die Tabelle übersteigt, load-Faktor. Also mit einer leeren Tabelle, erwartet O(lg n) Kopien der gesamten Daten-Tabelle. Eliminieren Sie diese zusätzlichen Kopien durch Bestimmung der Größe der hash-Tabelle im Voraus. Speziell

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

    Geteilt durch die max_load_factor ist zu berücksichtigen, für die leeren Zellen, sind notwendig für die hash-Tabelle zu bedienen.

    InformationsquelleAutor der Antwort John Kolen

  3. 1

    unordered_map (zumindest in den meisten Implementierungen) gibt schnell abrufen, aber relativ arm insertion Geschwindigkeit im Vergleich zu map. Ein Baum ist in der Regel am besten, wenn die Daten zufällig sortiert, und am schlimmsten ist, wenn die Daten sortiert ist (Sie ständig legen Sie an einem Ende der Struktur, die Erhöhung der Häufigkeit von re-balancing).

    Gegeben, dass es ~10 Millionen der Gesamtzahl der Einträge, könnte man nur reservieren, ein genügend großes array, und erhalten Sie wirklich schnell lookups-vorausgesetzt, genügend Physischer Speicher, dass es nicht die Ursache für Prügel, aber das ist nicht eine riesige Menge von Speicher nach modernen standards.

    Edit: ja, ein vector ist im Grunde ein dynamisches array.

    Edit2: Der code, den Sie Hinzugefügt haben einige Probleme. Ihre while (! LabelFile.eof() ) ist gebrochen. Sie normalerweise wollen, etwas zu tun, wie while (LabelFile >> inputdata) statt. Du bist auch das Lesen der Daten etwas ineffizient-was Sie offenbar erwartet zwei zahlen getrennt durch einen tab. Wenn das der Fall ist, würde ich schreiben die Schleife so etwas wie:

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

    InformationsquelleAutor der Antwort Jerry Coffin

Schreibe einen Kommentar