set vs unordered_set für die Schnellste iteration

In meiner Anwendung habe ich folgende Anforderungen -

  1. Strukturierung der Daten aufgefüllt wird, einfach mal mit einigen Werten (keine Schlüssel/Wert-Paare).
    Die Werte können wiederholt werden, aber ich möchte die Datenstruktur zum speichern von Ihnen nur einmal.
  2. Werde ich Durchlaufen 100s von Zeiten, durch alle Elemente der Datenstruktur, die oben erstellt. Die Reihenfolge, in der die Elemente angezeigt werden, die in die iteration ist dabei unerheblich.

Constraint 1 deutet darauf hin, dass ich entweder mit set oder unordered_set, da die Daten nicht in form von Schlüssel-Wert-Paare.

Nun Einschub ist teurer als unordered_set einfügen, aber die Datenstruktur ist nur ausgefüllt, einmal am Anfang von meinem Programm.

Ich glaube, der entscheidende Faktor wird sein, wie schnell ich iterieren über alle Elemente der Datenstruktur. Ich bin mir nicht sicher, ob set oder unordered_set wird schneller sein für diesen Zweck. Ich glaube, der standard macht keine Erwähnung dieser Tatsache als dieser Vorgang wird O(n) für die Daten-Struktur. Aber ich Frage mich, für welche Datenstruktur iterator.next() schneller sein wird.

Also, Messen Sie es und sehen.
Wie wäre es mit einem vector?
Sie können verschiedene Strukturen für verschiedene Zwecke. Zum Beispiel, bauen eine set, dann sobald Sie fertig sind kopieren/verschieben und alles in eine vector für die schnelle iteration. Also die Frage ist: brauchst du etwas andere als iteration, sobald es gefroren ist ? (wie schnell look-up)
Sie denken, dass die Satz magisch nicht haben, diese Kosten zu bezahlen?
std::lower_bound :-S

InformationsquelleAutor Aviral Goel | 2014-07-01

  1. 12

    Gibt es mehrere Ansätze.

    1. Die Kommentare auf deine Frage vorschlagen, halten Sie ein std::unordered_set hat die Schnellste O(1) lookup/einfügen und das O(N) iteration (da hat jeder container). Wenn Sie Daten haben, die viel ändert, oder erfordert eine Menge von zufälligen lookups, dies ist wahrscheinlich die Schnellste. Aber test.
    2. Wenn Sie benötigen zu Durchlaufen, 100s von Zeiten ohne zwischen-Insertionen, die Sie tun können eine einzelne O(N) kopieren auf eine std::vector gewinnen und aus angrenzenden Speicher-layout 100s von Zeiten. Testen, ob dies schneller ist als ein normales std::unordered_set.
    3. Wenn Sie eine kleine Anzahl von Zwischenprodukten, Einfügungen zwischen den Iterationen, könnte es zahlen für die Nutzung eines speziellen Vektor. Wenn Sie verwenden können,Steigern.Container, versuchen boost::flat_set bietet eine std::set - Schnittstelle mit einem std::vector Speicher-back-end (D. H. einen zusammenhängenden Speicher-layout, das ist sehr cache - und prefetch-freundlich). Wieder, test, ob dieser gibt ein speed-up zu den anderen beiden Lösungen.

    Für die Letzte Lösung, finden Sie in der Boost Dokumentation für einige der Nachteile (es ist gut, sich bewusst zu sein, alle anderen Fragen wie die iterator-Aufhebungs -, move-Semantik und exception safety):

    Steigern.Container-flat_[multi]map/set-Container sind bestellt-Vektor
    basierend assoziative Container basierend auf Austern und Alexandrescu ist
    - Richtlinien. Diese bestellten vector-Container haben auch profitiert
    vor kurzem mit dem Zusatz von move-Semantik in C++ für eine Beschleunigung
    Einfügung und Löschung Zeiten erheblich. Flache assoziative Container
    die folgenden Attribute haben:

    • Schneller nachschlagen als standard assoziative Container
    • Viel schneller iteration als standard assoziative Container
    • Weniger Speicherbedarf für kleine Objekte (und für große Objekte, wenn shrink_to_fit verwendet wird)
    • Bessere cache-performance (Daten werden in zusammenhängenden Speicher)
    • Nicht stabil Iteratoren (Iteratoren ungültig werden, wenn einfügen und löschen von Elementen)
    • Nicht-kopierbaren und nicht-bewegliche Werte-Typen können nicht gespeichert werden
    • Schwächer Ausnahme Sicherheit als standard assoziative Container (copy/move-Konstruktoren werfen kann, wenn Werte sich verschieben in Radierungen
      und Insertionen)
    • Langsamer Einfügung und Löschung als standard assoziative Container (speziell für nicht-beweglichen Lettern)

    HINWEIS: mit schneller nachschlagen, es ist gemeint, dass eine flat_set hat O(log N) auf zusammenhängenden Speicher anstatt O(log N) Zeiger jagt, die einer regelmäßigen std::set. Natürlich, ein std::unordered_set hat O(1) - lookup, der wird schneller für große N.

    schneller nachschlagen als hash-Container? Ich bezweifle, dass.
    Sie bedeuten schneller als std::set, die nicht O(log N) Zeiger jagt, anstatt O(log N) binäre Suche auf zusammenhängenden Speicher
    Gut, als Sie sollten eine klärende Bemerkung zu diesem Effekt.
    es ist ein Zitat aus der Boost-docs
    scheint etwas übertrieben, wenn ein einfaches std::vector ist ausreichend.

    InformationsquelleAutor TemplateRex

  2. 5

    Ich würde vorschlagen, Sie verwenden entweder oder unordered_set für "filtration" und wenn Sie fertig sind, verschieben Sie die Daten in Vektor-fester Größe

    unordered_set ist eine schlechte option für die "filtration" im Vergleich zu set. testen, ob ein einzelnes element ist, bereits dort ist die lineare Zeit.
    im Durchschnitt unordered_set ständige nachschlagen Komplexität, im Vergleich zu einer logarithmischen von set

    InformationsquelleAutor Michał Walenciak

  3. 4

    Wenn Gebäude von der Daten-Struktur nicht Faktor in der performance-Probleme (oder zumindest nur am Rande), betrachten Sie die Speicherung Ihrer Daten in einer std::vector: Es gibt nichts, es zu schlagen.

    Für die Beschleunigung der ersten Gebäude von der Daten-Struktur, die Sie vielleicht zuerst einen insert in eine std::unordered_set oder zumindest eine für die überprüfung der Existenz vor dem einsetzen.

    Im zweiten Fall braucht es nicht enthalten die Elemente, konnte aber enthalten z.B. Indizes.

    std::vector<T> v;
auto h = [&v](size_t i){return std::hash<T>()(v[i]);};
auto c = [&v](size_t a, size_t b){return v[a] == v[b];};
std::unordered_set<size_t, decltype(h), decltype(c)> tester(0, h, c);

    InformationsquelleAutor Deduplicator

  4. 3

    Empfehle ich Ihnen nicht für die Verwendung in diesem Fall. set ist der binäre Baum, und unordered_set ist hash-Tabelle - so viel Speicher verwenden, und haben langsam iteration Geschwindigkeit und schlechte Lokalität der Referenz. Wenn Sie die einfügen/entfernen/suchen von Daten Häufig set oder unordered_set gute Wahl, aber jetzt müssen Sie nur Lesen, speichern, Sortieren Sie die Daten einmal und verwenden Sie nur Daten viele Male.

    In diesem Fall sortiert Vektor werden kann, wie eine gute Wahl. vector ist dynamisch array, so hat es wenig overhead.

    Nur direkt, siehe code.

    std::vector<int> data;

int input;
for (int i = 0; i < 10; i++)
{
    std::cin >> input;
    data.push_back(input); //store data
}

std::sort(data.begin(), data.end()); //sort data

    Das ist alles. Alle Ihre Daten bereit ist.

    Wenn Sie brauchen, um Duplikate entfernen wie set, verwenden Sie einfach unique - erase nach der Sortierung.

    data.erase(
    std::unique(data.begin(), data.end()),
    data.end()
    );

    Beachten Sie, dass Sie verwenden sollten lower_bound, upper_bound und equal_range eher als find oder find_if zu verwenden, die Vorteile der sortiert Daten.

    InformationsquelleAutor ikh

  5. 2

    Ungeordnete-set verwendet eine hash-Tabelle, um in der Nähe von O(1) Zeit mit der Suche. Dies geschieht, indem ein hash des Schlüssels zur Berechnung der offset des Elements-Sie-sind-suchen (Schlüssel) aus dem Anfang des Datensatzes. Es sei denn, Ihr Datensatz ist klein (wie chars) unterschiedliche Schlüssel haben können dem gleichen hash (eine Kollision).

    Zur Minimierung von Kollisionen eine ungeordnete-set haben um die Daten zu halten-store ziemlich Dünn besiedelt. Dies bedeutet, dass die Suche nach einem Schlüssel wird ochstens O(1) Zeit (es sei denn, es ist eine Kollision).

    Jedoch bei der Iteration durch eine hash-Tabelle unserer iterator wird auch eine Menge ungenutzten Raum in unserem datastore-die verlangsamt die Suche nach dem nächsten element, durch unsere iterator. Wir könnten verbinden Sie benachbarte Elemente in die hash-Tabelle mit extra Zeiger, aber ich glaube nicht, dass eine ungeordnete-set so.

    Im Lichte der oben genannten, ich schlage vor, Sie verwenden einen sortierten Vektor für Ihre "set". Mit bisections Sie können nach dem speichern in O(log n) Zeit und das Durchlaufen der Liste ist trivial. Ein Vektor hat den zusätzlichen Vorteil, dass der Speicher zusammenhängend ist, so dass Sie sind weniger wahrscheinlich zu erleben-cache findet.

    InformationsquelleAutor doron

Schreibe einen Kommentar