Boost.Unordered

Tomahawk

Das Einlesen von etwa 3.000.000 std::strings in einen boost::unordered_setstd::string geht relativ schnell. Danach muss ich aber im Verlauf einer Berechnung 20.000 - 30.000 std::strings dem Container hinzufügen. Das dauert unverhältnismässig lange (7-8 Sek. auf i7 im Release-Mode).

Vor dem Hinzufügen der 20.000 - 30.000 std::strings in den Container hat der Container denselben max-bucket-count und max-load-factor wie danach. Natürlich hat sich load-factor etwas vergrössert (von 0.931 auf 0.937).

Weshalb dauert das Eintragen von nur 20.000 - 30.000 std::strings so verhältnismässig lange und wie kann ich das verbessern?

/// insert() is a simplified function
void insert(boost::unordered_set<std::string>* set, std::string& file) {
  set->clear();
  std::ifstream ifs(file.c_str());
  std::string input;
  // insert approx 3.000.0000 std::strings into the unordered container
  while (!getline(ifs, input).eof()) {
    // do something
    set->insert(input);
    // do something
  }
}

/// insert_more() is a simplified function
void insert_more(boost::unordered_set<std::string>* set) {
  std::string input;
  // insert further 20.000 - 30.000 std::strings into the unordered container
  while (condition()) {
    // do something
    set->insert(input);  // time consuming
    // do something
  }
}

Danke und Gruss
T.

Ich weiß nicht was bei dir schnell, nicht schnell ist, bzw was unordered_set eigentlich genau machen soll. Aber ich sehe, dass du im ersten Fall auf einen leeren Container operierst. Vielleicht bringt es was, das auch im zweiten Fall zu machen. Und im Anschluss die beiden Container zusammen zu führen.

Tomahawk

Timothy Lovejoy schrieb:

Ich weiß nicht was bei dir schnell, nicht schnell ist, bzw was unordered_set eigentlich genau machen soll. Aber ich sehe, dass du im ersten Fall auf einen leeren Container operierst. Vielleicht bringt es was, das auch im zweiten Fall zu machen. Und im Anschluss die beiden Container zusammen zu führen.

Auch im zweiten Fall mit einem leeren Container zu arbeiten behebt das Laufzeitproblem. Nur darum geht es nicht, ich möchte genauer verstehen, weshalb das Beschreiben des Containers in der zweiten Funktion zu teuer ist.

Laufzeit:

Das Eintragen (insert) von 3.000.000 std::strings in den leeren Container dauert 4 Sek.
Das Eintragen (insert) von 22.000 std::strings in denselben Container dauert 8 Sek.

Gruss
T.

pumuckl

Tomahawk schrieb:

Natürlich hat sich load-factor etwas vergrössert (von 0.931 auf 0.937).

Weshalb dauert das Eintragen von nur 20.000 - 30.000 std::strings so verhältnismässig lange und wie kann ich das verbessern?

Nach allem was ich bisher über hash-tables gelesen hab (was zugegebenermaßen nicht so viel ist), ist ein load-factor von über 0.66 nicht so prickelnd, d.h. führt zu häufigen Kollisionen, was wiederum die Einfüge-Operation Laufzeit kostet.
Bei den 300k Einträgen werden zumindest am Anfang erstmal wenige bis garkeine Kollisionen auftauchen, bei den 20-30k neuen Einträgen dagegen wohl ständig. Im schlechtesten Fall ist laut Doku die Komplexität O(n), im Vergleich zu O(1) im besten Fall.

Überprüf doch mal wie lange du für jeweils 10k "zuladung" brauchst bei den ersten 300k Einträgen. Überprüf außerdem den load-factor.
Ggf. solltest du die Zahl der buckets erhöhen und schauen was bei rauskommt.