3. frage zu STL containern

frage zu STL containern

  • ?

    mich wuerde mal interessieren ab wieviel elementen fuer einen STL-container
    (z.B. vector) es problematisch hinsichtlich algorithmen oder jeglichem zugriff gibt?
    gibt es solch eine maximum grenze ?
    falls ja, was waere eine alternative datenstruktur ?

    ich schreibe gerade einen parser der aus einer text-datei bestimmte daten extrahiert und diese dann in form von instanzen einer klasse in einem STL container ablegt.

    allerdings kann die anzahl an instanzen schonmal leicht die 1000.000 grenze erreichen 😞 -> keine ahnung ob das ein problem sein duerfte?

    vielen dank vorab.

    0
  • S

    Wikliche Probleme wird es erst geben, falls dir der virtuelle Speicher ausgeht. Das dürfte aber von Containertyp weitgehend unabhängig sein. Du musst einfach schauen, wie groß eine Instanz ist, das gibt dir die Möglichkeit, den Speicherbedarf abzuschätzen. Natürlich gibt es auch Algorithmen die auf manchen Containern bei großer Anzahl an Elementen sehr langsam werden. Das kann man aber nur für die konkrete Kombination aus Container und Algorithmus sagen.

    0
  • ?

    ok, danke.

    im prinzip geht es nur um lineare suche (find etc.) was die algorithmen angeht.
    hoffe das mit dem langsam werden trifft hier nicht zu.
    bei der sache mit dem virtuellen speicher muesste ich mir das mal zusammenrechnen.

    gruss

    0
  • V

    Ich gehe mal von Windows aus.
    Hast mehrere Grenzen.
    Paßt alles noch in den Prozessorcache und liegt zufällig auch noch da, ist es schnell wie Proz.
    So bei 128k hört das aber sachon auf.
    Anderenfalls ist es schonmal spürbar, weil das RAM nicht so fix ist. Aber geht ja nicht anders.
    So bei RAM-größe, die eingebaut ist minus 150MB hört das dann auf.
    Ab jetzt muß Speicher immer von der Festplatte eingelagert werden und das ist LAHM.
    Geht bis zur Menge des virtuellen Speichers, also Größe der Auslagerungsdatei.
    Danach bricht das Programm einfach ab.
    Zusatzgrenze: Geht bis ca 1.8GB. Danach geht der virtuelle Adressraum aus und das Programm bricht einfach ab.
    Bei einem 64-Bit-Betriebssystem fällt die Grenze mit dem virtuellen Adressraum weg.

    0
  • S

    pepe75 schrieb:

    ok, danke.
    im prinzip geht es nur um lineare suche (find etc.) was die algorithmen angeht.
    gruss

    Da hängt es sehr stark vom benutzten Kontainer ab. Bei ner list oder nem vector ist die Dauer zum Suchen proportional zur Anzahl der Elemente also O(n);
    Bei Associativen Kontainern wie map oder set ist sie O(log n). Das ist für große n schon deutlich schneller.

    0
  • N

    Bei sehr grossen Datenmengen kann sich eventuell std::deque auszahlen, da dieser Container kleinere Speicherbereiche anfordert (und die Wahrscheinlichkeit grösser ist, dass mehrere kleine Stücke frei sind als ein grosses).

    Ich würde am besten etwas herumexperimentieren, auch bezüglich Performance. Wenn du wirklich aufs Speicher-Ausgehen gefasst sein willst, fange std::bad_alloc (allerdings hatte ich selbst noch nie einen Fall, in dem das nötig war – du musst dir auch überlegen, wie du in so einer Situation sinnvoll reagierst).

    0

  • Nexus schrieb:

    Bei sehr grossen Datenmengen kann sich eventuell std::deque auszahlen, da dieser Container kleinere Speicherbereiche anfordert (und die Wahrscheinlichkeit grösser ist, dass mehrere kleine Stücke frei sind als ein grosses).

    Ich würde am besten etwas herumexperimentieren, auch bezüglich Performance. Wenn du wirklich aufs Speicher-Ausgehen gefasst sein willst, fange std::bad_alloc (allerdings hatte ich selbst noch nie einen Fall, in dem das nötig war – du musst dir auch überlegen, wie du in so einer Situation sinnvoll reagierst).

    Da muss ich dich leider übelst enttäuschen, denn den gleichen Gedankengang hatte ich auch und hab da einige interessante Erkenntnisse über std::deque gewonnen. Bei der STLport Implementierung von SGI besteht eine deque aus einzelnen "maps", die untereinander verlinkt sind. Jede map besteht aus 1-16 (auf den ersten Blick in die Dinkumware deque) Elementen und einigen Zeigern, sodass bei kleinen Datentypen das Verhältnis von organisatorischen Daten zu Nutzdaten exorbitant schlecht wird. Leider kann man die map size nicht einstellen, um ein besseres Verhältnis zu erzielen, aber so bleibt eine deque für eine große Anzahl von kleinen Objekten ein Speicherfresser.

    0
  • N

    Ich habe eben die MSVC++-Implementierung getestet:

    #include <cstdlib>
#include <fstream>
#include <deque>
#include <vector>

size_t allocations;
size_t bytes;

std::ofstream logger("log.txt");

void* operator new(size_t size)
{
	++allocations;
	bytes += size;
	return malloc(size);
}

void operator delete(void* mem)
{
	free(mem);
}

template <size_t Bytes>
struct byter
{
	char arr[Bytes];
};

template <typename T>
void test_container()
{
	allocations = 0;
	bytes = 0;

	std::deque<T> c(1048576 / sizeof(T));
	logger << "Groesse des Typs:           " << sizeof(T) << std::endl;
	logger << "Anzahl Elemente:            " << c.size() << std::endl;
	logger << "Allokationen:               " << allocations << std::endl;
	logger << "Speicherverbrauch (Total):  " << bytes << std::endl;
	logger << "Speicherverbrauch (Daten):  " << c.size() * sizeof(T) << std::endl;
	logger << "Anteil Speicher fuer Daten: " << static_cast<float>(c.size() * sizeof(T)) / bytes << std::endl;
	logger << c[rand()%c.size()].arr << std::endl; // Wegoptimieren verunmöglichen
}

int main()
{
	test_container<byter<4> >();
	test_container<byter<16> >();
	test_container<byter<64> >();
	test_container<byter<256> >();
	test_container<byter<1024> >();
}

    Nun zu den Resultaten. Der STL-Container std::deque ist bezüglich Speicherverbrauch nicht sehr effizient, wenn die Elementtypen klein sind. Je grösser sie werden, desto vernachlässigbarer wird der Overhead.

    Groesse des Typs:           4
Anzahl Elemente:            262144
Allokationen:               65560
Speicherverbrauch (Total):  1995280
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.525528

Groesse des Typs:           16
Anzahl Elemente:            65536
Allokationen:               65560
Speicherverbrauch (Total):  1995280
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.525528

Groesse des Typs:           64
Anzahl Elemente:            16384
Allokationen:               16405
Speicherverbrauch (Total):  1329052
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.788965

Groesse des Typs:           256
Anzahl Elemente:            4096
Allokationen:               4113
Speicherverbrauch (Total):  1103936
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.949852

Groesse des Typs:           1024
Anzahl Elemente:            1024
Allokationen:               1038
Speicherverbrauch (Total):  1064936
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.984638

    Nun zum Vergleich der std::vector (identischer Code bis auf Containerdeklaration):

    Groesse des Typs:           4
Anzahl Elemente:            262144
Allokationen:               2
Speicherverbrauch (Total):  1048580
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.999996

Groesse des Typs:           16
Anzahl Elemente:            65536
Allokationen:               2
Speicherverbrauch (Total):  1048580
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.999996

Groesse des Typs:           64
Anzahl Elemente:            16384
Allokationen:               2
Speicherverbrauch (Total):  1048580
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.999996

Groesse des Typs:           256
Anzahl Elemente:            4096
Allokationen:               2
Speicherverbrauch (Total):  1048580
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.999996

Groesse des Typs:           1024
Anzahl Elemente:            1024
Allokationen:               2
Speicherverbrauch (Total):  1048580
Speicherverbrauch (Daten):  1048576
Anteil Speicher fuer Daten: 0.999996

    Aber dieser Vergleich ist natürlich etwas unfair, da der std::vector seinen Speicher in den wenigsten Fällen so gut ausnutzen kann. Als Konstrast dazu, nachdem ich nach der Deklaration die Anweisung c.resize(c.capacity()+1); eingefügt habe:

    Groesse des Typs:           4
Anzahl Elemente:            262145
Allokationen:               3
Speicherverbrauch (Total):  2621444
Speicherverbrauch (Daten):  1048580
Anteil Speicher fuer Daten: 0.400001

Groesse des Typs:           16
Anzahl Elemente:            65537
Allokationen:               3
Speicherverbrauch (Total):  2621444
Speicherverbrauch (Daten):  1048592
Anteil Speicher fuer Daten: 0.400005

Groesse des Typs:           64
Anzahl Elemente:            16385
Allokationen:               3
Speicherverbrauch (Total):  2621444
Speicherverbrauch (Daten):  1048640
Anteil Speicher fuer Daten: 0.400024

Groesse des Typs:           256
Anzahl Elemente:            4097
Allokationen:               3
Speicherverbrauch (Total):  2621444
Speicherverbrauch (Daten):  1048832
Anteil Speicher fuer Daten: 0.400097

Groesse des Typs:           1024
Anzahl Elemente:            1025
Allokationen:               3
Speicherverbrauch (Total):  2621444
Speicherverbrauch (Daten):  1049600
Anteil Speicher fuer Daten: 0.40039

    Ganz so rosig sieht es also auch beim std::vector nicht immer aus, die Wahrheit liegt irgendwo dazwischen. Die std::deque benötigt zwar bei kleinen Objekten relativ viel Speicher (die Hälfte ist Overhead), aber vor allem bei grösseren bzw. sehr vielen Elementen kann sie sich trotzdem auszahlen, weil sie flexibler ist, was Reallokationen und Speicherfreigaben betrifft. Schlussendlich kommts halt immer auf den Anwendungsfall an, deshalb vorhin auch mein Vorschlag mit dem Herumexperimentieren.

    0
Anmelden zum Antworten