Wie kann ich die Speichernutzung von std :: map schätzen?

Zum Beispiel habe ich eine std::map mit bekannten sizeof(A) sizeof(B), während die Karte hat N Einträge drin. Wie schätzen Sie die Speichernutzung?
Ich würde sagen, es ist so etwas wie

(sizeof(A) + sizeof(B)) * N * factor

Aber was ist der Faktor? Verschiedene Formel vielleicht?

Vielleicht ist es einfacher zu Fragen, für die Obere Grenze?

InformationsquelleAutor der Frage Drakosha | 2009-04-06

  1. 30

    Schätzung wäre näher zu 

    (sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

    Es ist ein overhead für jedes element, das Sie hinzufügen, und es gibt auch einen festen overhead für die Aufrechterhaltung der Daten-Struktur, für die Daten Struktur Speicherung der Karte. Dies ist in der Regel ein binärer Baum, wie ein Rot-Schwarz-Baum. Zum Beispiel, in den GCC-C++ STL-Implementierung ELEMENT_OVERHEAD wäre sizeof(_Rb_tree_node_base) und CONTAINER_OVERHEAD wäre sizeof(_Rb_tree). Auf dem Bild oben sollte man auch hinzufügen, der overhead der memory-management-Strukturen verwendet für die Speicherung der Karte, die Elemente.

    Es ist wahrscheinlich einfacher zu erreichen eine Schätzung durch Messen der code-Speicherverbrauch für verschiedene große Sammlungen.

    InformationsquelleAutor der Antwort Diomidis Spinellis

  2. 14

    Könnten Sie MemTrackvon Curtis Bartley. Es ist ein Speicher-Zuweisung ersetzt die Standard ein und kann Speichernutzung verfolgen nach unten, um die Art der Zuweisung.

    Ein Beispiel der Ausgabe:

    -----------------------
Memory Usage Statistics
-----------------------

allocated type                        blocks          bytes  
--------------                        ------          -----  
struct FHRDocPath::IndexedRec          11031  13.7% 2756600  45.8%
class FHRDocPath                       10734  13.3%  772848  12.8%
class FHRDocElemPropLst                13132  16.3%  420224   7.0%
struct FHRDocVDict::IndexedRec          3595   4.5%  370336   6.2%
struct FHRDocMDict::IndexedRec         13368  16.6%  208200   3.5%
class FHRDocObject *                      36   0.0%  172836   2.9%
struct FHRDocData::IndexedRec            890   1.1%  159880   2.7%
struct FHRDocLineTable::IndexedRec       408   0.5%  152824   2.5%
struct FHRDocMList::IndexedRec          2656   3.3%  119168   2.0%
class FHRDocMList                       1964   2.4%   62848   1.0%
class FHRDocVMpObj                      2096   2.6%   58688   1.0%
class FHRDocProcessColor                1259   1.6%   50360   0.8%
struct FHRDocTextBlok::IndexedRec        680   0.8%   48756   0.8%
class FHRDocUString                     1800   2.2%   43200   0.7%
class FHRDocGroup                        684   0.8%   41040   0.7%
class FHRDocObject * (__cdecl*)(void)     36   0.0%   39928   0.7%
class FHRDocXform                        516   0.6%   35088   0.6%
class FHRDocTextColumn                   403   0.5%   33852   0.6%
class FHRDocTString                      407   0.5%   29304   0.5%
struct FHRDocUString::IndexedRec        1800   2.2%   27904   0.5%

    InformationsquelleAutor der Antwort Xavier Nodet

  3. 13

    Wenn Sie wirklich wollen, zu wissen, die Laufzeit, Speicherbedarf, verwenden Sie eine benutzerdefinierte Zuweisung und übergeben Sie es bei der Erstellung der Karte. Siehe Josuttis' Buch und diese Seite sein (für eine individuelle Zuweisung).

    Vielleicht ist es einfacher zu Fragen, für die Obere Grenze?

    Die Obere Grenze hängt von der genauen Umsetzung (z.B. die Besondere Variante des balanced tree). Vielleicht können Sie uns sagen, warum Sie benötigen diese Informationen, damit wir besser helfen können?

    InformationsquelleAutor der Antwort dirkgently

  4. 4

    Vor kurzem musste ich diese Frage zu beantworten, für mich selbst, und schrieb nur ein kleines benchmark-Programm mit std::map die ich zusammengestellt unter MSVC 2012 im 64-bit Modus.

    Einer Karte mit 150 Millionen Knoten getränkt bis ~ 15 GB, was bedeutet, die 8-byte-L, 8-byte-R, 8-byte-int-Taste, und 8-byte-datum in Höhe von 32 bytes, getränkt über 2/3rds der Karte - Speicher für den internen Knoten, verlassen 1/3 der Blätter.

    Persönlich, ich fand das überraschend schlechte Speicher-Effizienz, aber es ist was es ist.

    Hoffe, das macht für eine praktische Regel-of-Daumen.

    PS: Der Aufwand für eine std::map ist, die von einem einzelnen Knoten, der Größe AFAICT.

    InformationsquelleAutor der Antwort user2548100

  5. 0

    Die Formel ist mehr wie:

    (sizeof(A) + sizeof(B) + factor) * N

    wo Faktor ist die pro Eintrag overhead. C++ - Karten werden normalerweise implementiert, als rot-schwarz-Bäume. Diese sind binäre Bäume, so gibt es mindestens zwei Zeiger für den linken/rechten Knoten. Es wird auch eine Umsetzung Zeug - wahrscheinlich ein Eltern-Zeiger und eine "Farbe" - Anzeige, also Faktor kann so etwas wie 

    (sizeof( RBNode *) * 3 + 1) / 2

    Allerdings ist dies alles sehr implementierungsabhängig - um herauszufinden, für sicher, Sie wirklich brauchen, zu prüfen, den code für die eigene Bibliothek Umsetzung.

    InformationsquelleAutor der Antwort

  6. -1

    Die Größe der Karte hängt wirklich davon ab, die Umsetzung der Karte. Sie können unterschiedliche Größen auf verschiedenen Compilern/Plattformen, je nachdem, welche STL-Implementierung Sie stellen.

    Warum brauchen Sie diese Größe?

    InformationsquelleAutor der Antwort Cătălin Pitiș

Schreibe einen Kommentar