Pre-allocating Eimer in einer C++ - std::unordered_map

Ich bin mit der std::unordered_map von gnu++0x speichern einer großen Menge von Daten. Ich will pre-Zuordnung von Speicherplatz für die große Anzahl von Elementen, da ich gebunden der gesamte Speicherplatz verwendet.

Was ich möchte in der Lage sein zu tun ist, rufen Sie:

std::unordered_map m;
m.resize(pow(2,x));

wo x bekannt ist.

std::unordered_map dies nicht unterstützt. Ich würde eher std::unordered_map wenn möglich, da er schließlich Teil des Standards.

Einige andere Einschränkungen:

Müssen zuverlässig O(1) der Zugriff und die mutation von der Karte. Die gewünschte hash und Vergleich der Funktionen sind bereits nicht-standard-und etwas teuer. O(log n) mutation (wie bei std::map) ist zu teuer.

-> Die teuren hash und Vergleich auch Abschreibungen-basiert Wachstum viel zu teuer. Jedes extra einfügen erfordert O(n) Operationen von Funktionen, die Ergebnisse in einem zusätzlichen quadratischen term in der der Algorithmus die Laufzeit, da der exponentielle Speicherbedarf benötigen O(n) Wucherungen.

InformationsquelleAutor JAD | 2011-05-05

buckets c++unordered-map

31
```
m.rehash(pow(2,x));
```
wenn pow(2, x) ist die Anzahl der buckets, die Sie möchten, reserviert. Sie können auch:
```
m.reserve(pow(2,x));
```
aber jetzt pow(2, x) ist die Anzahl der Elemente, die Sie planen, einführen. Die beiden Funktionen nichts zu tun, sondern preallocate Eimer. Sie don ' T fügen Sie beliebige Elemente. Und Sie sind sowohl dazu genutzt werden, um genau für Ihren Anwendungsfall.

Hinweis: Sie sind nicht garantiert, um genau pow(2, x) Eimer. Einige Implementierungen verwenden Sie nur eine Reihe von Eimern, die eine Potenz von 2 ist. Andere Implementierungen verwenden Sie nur eine prime Anzahl der buckets. Wieder andere verwenden nur eine Teilmenge der Primzahlen, für die Anzahl der buckets. Aber in jedem Fall, die Umsetzung sollte akzeptieren Ihre Hinweis bei der Anzahl der Perioden, die Sie wünschen, und dann intern die Runde bis zum nächsten akzeptablen Anzahl von Eimern.

Hier ist die genaue Formulierung, dass die neueste (N4660) verwendet, um das argument zu rehash:

a.rehash(n) : Postconditions: a.bucket_count() >= a.size() /a.max_load_factor() and a.bucket_count() >= n.

Diese postcondition sorgt dafür, dass bucket()_count() >= n, und dass load_factor() bleibt weniger als oder gleich max_load_factor().

Anschließend reserve(n) ist definiert in Bezug auf rehash(n):

a.reserve(n) : Wie a.rehash(ceil(n /a.max_load_factor())).
- Sie sind mit Hinweis, als ob es ist: iterator, std::set::insert( iterator Hinweis, const value_type& value ); en.cppreference.com/w/cpp/container/set/insert , sieht unsachgemäße Formulierung.
- Nein, er ist mit "Tipp", wie in der umgangssprachlichen Bedeutung des Begriffs im amerikanischen Englisch. Die Bedeutung ist klar.
- Ich bezog mich auf italicization des Wortes wenn man über eine C++ - Konzept.
InformationsquelleAutor Howard Hinnant
5

Ich glaube nicht, dass es darauf ankommt, für eine ungeordnete map, pre-allocated memory. Die STL wird erwartet, dass O(n) amortisiert einlegen Zeit. Sparen Sie sich das lästige schreiben Ihrer eigenen allocator, bis Sie wissen, dies ist der Flaschenhals des Codes, meiner Meinung nach.
- Die STL-garantiert in O(n) amortisiert Einfügung Zeit, aber ein gemeinsamer Weg der Umsetzung ist die Erhöhung der Anzahl der buckets von konstanter Faktor, und dann rehash jedes vorhandene element. Dies geschieht in O(log n) - mal, wenn Sie speichern von n Elementen in der map. Wenn n 2^große, dieser fügt einen zusätzlichen Faktor, der groß ist, um die Anzahl der Einfügungen. Ich versuche, sich zu rasieren Weg von diesem Faktor.
- "dies fügt einen zusätzlichen Faktor, der großen", Nein, es fügt einen zusätzlichen Faktor 2. Verstehen Sie, wie die fortgeführten Operationen arbeiten? Der einzige wirkliche Grund, warum diese Antwort falsch ist, weil es nicht "garantieren" O(n) amortisiert insertion der Zeit, es stellt nur erwartet O(n) amortisiert Einfügung Zeit, mit exponentiell hoher Wahrscheinlichkeit über beliebig eingefügte Elemente. Wenn Sie wissen, die genaue Größe, die den Eimer passen und die hash-Funktion verwendet wird, es ist immer noch möglich, zu betrügen, die hash-Tabelle und die Kraft N Kollisionen für alle einführen.
InformationsquelleAutor Mike Lyons
3

Ich würde vorschlagen, das schreiben Ihrer eigenen allocator für die std::unordered_map dass Speicher reserviert, genau so, wie Sie wollen.

InformationsquelleAutor orlp
1

Der Konstruktor nimmt einen parameter "size_type bucket_count" nach http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

so ist der einfachste Weg, das zu tun, was dein Beispiel code sagt, ist:
```
std::unordered_map m{ pow(2,x) };
```
Diese werden effizienter, da es undefiniert, wie viele buckets reserviert wird auf die Bau-andernfalls kann es zu reservieren und dann freigeben, wenn Sie anrufen, reservieren danach.

InformationsquelleAutor Ben
-2

Ich denke rehash und reserve beide funktionieren nur, wenn Sie im Voraus wissen, wie viel Speicher Ihr zugeordnete Wert wird. Wenn der zugeordnete Wert ist kompliziert oder dynamisch seine Größe ändert (z.B. ein Vektor), dann müssen Sie Ihre eigene Implementierung. Zum Beispiel, wenn Ihre Speicher-Größe ermöglicht es, Sie berechtigt ist, den größten container, kann immer passieren, zu existieren.
- Einige Punkte, die Sie machen keinen Sinn, oder Sie hat nicht selbst "machen" verstanden. Zum Beispiel "wenn der zugeordnete Wert dynamisch ändert, ist die Größe (z.B. vector)". Egal wie viele Elemente Sie haben in einem Vektor (oder einen beliebigen container oder Klasse für diese Angelegenheit), sizeof(std::vector<T>) bleibt die gleiche (für den gleichen T offensichtlich). Die map reserviert, die genaue Menge an Speicherplatz für eine std::vector 1 element oder eine std::vector 1 mil Elemente. "Sie können behalten uns das größte container-das kann immer passieren, zu existieren" ist ein weiterer Punkt, dass ich nicht als eine fundierte Beratung, die im Zusammenhang mit dieser Frage.
InformationsquelleAutor hrrl

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.