3. Array im Vector

Array im Vector

  • H

    1. Gibt es die Möglichkeit in einen Vector ein Array abzulegen?

    Nein.
    Versuchs mal mit boost::array (www.boost.org)

    2. Gibt's evtl. 'nen 2D-Vector? Also irgendwie sowas: "vector <double> <double> test"
    analog zu "double test[100][6]"

    vetor<vector<double> >.
    Beachte das leezeichen zwischen > >.

    3. Ich kann mit Vectoren wesentlich mehr Speicher reservieren als mit Arrays (erhalte
    dann Stack-Overflow). Ich Vermute daß der Vector auf dem Heap liegt (mehr Speicher
    verfügbar). Gibt es eine Möglichkeit auch Arrays in der Größenordnung 50.000.000 (in
    double) anzulegen (evtl. irgendwie auf dem Heap anlegen bzw. Stack-Size vergrößern)?

    Stacksize ist compilerspezifisch.
    Ansonsten ja klar:

    double * foo = new double [50000000];
...
delete [] foo;

    4. Wie sieht es bei dieser Lösung Performancetechnisch aus? Ich werde natürlich Anfangs
    mit reserve() schon den mindestens erforderlichen Speicher reservieren um ein unnötiges
    Vergrößern des Vectors im kritischen Programmteil zu minimieren. Wäre es Performancetechnisch
    besser selbst eine (einfach) verkettete Liste zu schreiben? PS. Wie lange anschließend
    das Auslesen dauert ist mir sch*** egal.

    Liste wachsen grantiert mit O(1), vector im worst case mit O(n). Allerdings werden recht wenig Wachstumsschritte nötig sein (wächst exponenziell). Deswegen ist vector die bessere Wahl. Du kannst aber auch mal mit deque profilen.

    5. Kann ich auf die automatische Größenanpassung des Vectors einfluss nehmen? Standardmäßig
    wird die Kapazität immer verdoppelt. In Java ist es möglich beim erzeugen des Vectors
    die Kapazität um die der Vector erweitert werden soll mit anzugeben. Ist das in C++
    auch möglich?

    Nein. Wenn du weißt um wieviel er wachsen wird kannst du zu dem Zeitpunkt reserve verwenden bzw. resize.

    0
  • ?

    Hilfe 3 Antworten in 6 Minuten!
    Ich krieg ja Angst vor euch :-).

    Scherz beiseite: Vielen dank!!! Werds gleich austesten.

    Gruß
    Threaddy

    0
  • P

    Hallo,

    also du könntest das natürlich mit nem const cast machen aber das ist garnicht schön. Viel interessanter sind die Fehlermeldungen die weiter unten stehen.

    Was funktioniert ist:

    vector<double*> vec;
vec.push_back(new double[6]);
//jetzt müsstest du zuweisen

    Da darfst du nicht vergessen wieder aufzuräumen und den speicher wieder frei zu geben.

    Ich würde an deiner Stelle eine Struktur oder eine Klasse nehmen die die sechs Werte enthält und davon einen Vector anlegen.

    Ob es einen 2-dimensionalen Vector gibt ?
    Ja.

    vector< vector<double> > 2dvec;

    Da du nur am Ende des Vectors einfügst, fährst du mit einer List nicht besser. Beide schaffen das in O(1). Vorteil Vector liegt im Speicher wie ein Array.

    Stackgröße ist compilerabhängig.

    Ich glaub das wars.

    [Edit] Ich sollte nicht nebenbei essen. Gleich 3 schneller [/Edit]

    0
  • H

    also du könntest das natürlich mit nem const cast machen

    Nein. Datenfelder sind einander nicht zuweisbar.

    Ob es einen 2-dimensionalen Vector gibt ?
    Ja.

    Das haben wir vor 'ner halben Stunde geklärt.

    Beide schaffen das in O(1).

    Nein Vectoren schaffen das nicht mit O(1). Im worst case müssen alle Elemente kopiert werden.

    Wenn mit den Werten noch gearbeitet wird kann es durchaus sinnvoll sein diese sechs Werte zu kapseln. Ob das so ist weiß ich nicht.

    Ansonsten ist ein

    std::vector<boost::array<double, 6> > ...

    vorzuziehen.

    0
  • P

    Helium schrieb:

    also du könntest das natürlich mit nem const cast machen

    Nein. Datenfelder sind einander nicht zuweisbar.

    Sollte nen prinzipieller Hinweis sein. Dass es nicht geht sagt ihm doch auch der Compiler, Error blblbla da kein L-Value.

    Helium schrieb:

    Ob es einen 2-dimensionalen Vector gibt ?
    Ja.

    Das haben wir vor 'ner halben Stunde geklärt.

    Sry, hab gegessen.

    Helium schrieb:

    Beide schaffen das in O(1).

    Nein Vectoren schaffen das nicht mit O(1). Im worst case müssen alle Elemente kopiert werden.

    Ich dachte immer dass wär beim Einfügen am Ende nicht so. Warum müssen denn da alle Elemente kopiert werden ?

    0
  • V

    prolog schrieb:

    ...
    Ich dachte immer dass wär beim Einfügen am Ende nicht so. Warum müssen denn da alle Elemente kopiert werden ?

    Wenn der vorreservierte Speicherbereich (capacity) ueberschritten wird.

    mfg
    v R

    0
  • P

    Hallo,

    danke. Ok jetz ist es mir klar. Also ist das nur sinnvoll wenn man abschätzen kann wieviele Elemente ungefähr enthalten sein werden. Dann und wenn man halt oft per randomaccess drauf zugreifen will. Für mich war bis dato nur der zugriff ein Entscheidungsfaktor, ob list oder vector. Ok also danke für die Aufklärung.

    0
  • H

    Du hast einen Speicherblock. Darein Legst du deine Werte. Wenn du soviele Werte drin hast, das der Block voll ist holst du einen neuen doppelt so großen, kopierst die alten Werte rein und gibst den alten Block frei.

    Das ist die Funktionsweise eines Vectors.

    Für schnelles Einfügen an Anfang und Ende gibt es deque.

    0
  • ?

    Hi,
    danke nochmals an euch alle für die schnellen Antworten!!!
    Meine eigentliche Frage wurde geklärt, hab genau erfahren was ich wissen wollte, allerdings hab ich jetzt zu dieser Diskussion noch mal ein paar kurze Fragen:

    Du hast einen Speicherblock. Darein Legst du deine Werte. Wenn du soviele Werte drin hast, das der Block voll ist holst du einen neuen doppelt so großen, kopierst die alten Werte rein und gibst den alten Block frei.

    Wenn ich das richtig verstehe ist dann ein Vector (bei einer zeitkritischen Anwendung) bei großen Datenmengen nicht zu empfehlen, da beim Vergrößern der Komplette Inhalt kopiert werden muß.
    Kleine Nebenfrage: Warum kann man nicht mit nem Pointer am Ende des Datenfeldes auf den zweiten Teil des Feldes deuten? Denke mal daß dann die Zugriffsperformance stark sinkt oder?

    Für schnelles Einfügen an Anfang und Ende gibt es deque.

    Wie läuft da das Anfügen? Ist das eine Vekettete Liste?

    PS. Mir kommt es allein auf die Speicherung der Messwerte an. Die Ergebnisse werden dann von der C++ DLL sowieso in einem Array an eine andere Programmiersprache übergeben (und wie lange das dann dauert ist unkritisch).

    Für eure Bemühungen vielen Dank!

    Gruß
    Threaddy

    0
  • P

    Hmm,
    das mit dem Pointer is ne gute Frage, warum macht man das nicht ?
    Man müsste halt zusätzlich zu den Speicherblöcken noch n-1 pointe verwalten, wobei n die Anzahl der Speicherblöcke ist.

    Für den Zugriff kann man doch den Index in den entsprechenden Block relativ leicht abbilden. Wär doch eigentlich ne gute Idee mit dem Pointer oder ?
    Bei nem push_front hatte man immer noch das Problem mit reallocierung aber das hat man sowieso.
    hmmm

    0
  • T

    Hi,
    habe bezüglich den Performanceunterschieden zwischen Vector und Deque mal folgendes Testprogramm geschrieben:

    #include <VECTOR>
#include <deque>
#include <iostream>
#include <windows.h>

void main()
{
	using namespace std;
	DWORD starttime, endtime, temp;
	double size=10;  // bzw. size=100  size=1.000.000  size=100.000

	starttime=GetTickCount();
	vector <double*> test;
	endtime=GetTickCount();
	cout << "      Benoetigte Zeit zum anlegen des Vectors: " << endtime-starttime << " ms\n";
	double temparray[6]={1,2,3,4,5,6};
	starttime=GetTickCount();
	for (int k=0; k<10000000; k++)  // bzw. k<100  k<1000  k<1000000
	{
		temp=GetTickCount();
		for (long i=0; i<size; i++)
			test.push_back(temparray);
		cout << "Benötigte Zeit für " << k << ". Vector: " << GetTickCount()-temp << " ms\n";
	}
	endtime=GetTickCount();
	cout << "      Benoetigte Zeit zum fuellen des Vectors: " << endtime-starttime << " ms\n";
	cout << "                                     Capacity: " << test.capacity() << "\n";
	cout << "                                         Size: " << test.size() << "\n\n";
	cout << "================================================================================\n";	
	starttime=GetTickCount();
	deque <double*> test2;
	endtime=GetTickCount();
	cout << "        Benoetigte Zeit zum anlegen der Deque: " << endtime-starttime << " ms\n";
	starttime=GetTickCount();
	for (k=0; k<1000000; k++)  // bzw. k<100  k<1000  k<1000000
	{
		temp=GetTickCount();
		for (long i=0; i<size; i++)
			test2.push_back(temparray);
		cout << "Benötigte Zeit für " << k << ". Deque: " << GetTickCount()-temp << " ms\n";
	}
	endtime=GetTickCount();
	cout << "        Benoetigte Zeit zum fuellen der Decue: " << endtime-starttime << " ms\n";
	cout << "                                         Size: " <<test2.size() << "\n\n";
}

    Die Ausgaben (cout << irgendwas) hab ich beim Aufrufen in eine Datei umgeleitet und verschiedene Versionen getestet:

    1. 10x 10.000.000 Werte geschrieben:
    Benoetigte Zeit zum anlegen des Vectors: 0 ms
    Benötigte Zeit für 0. Vector: 451 ms
    Benötigte Zeit für 1. Vector: 440 ms
    Benötigte Zeit für 2. Vector: 241 ms
    Benötigte Zeit für 3. Vector: 741 ms
    Benötigte Zeit für 4. Vector: 280 ms
    Benötigte Zeit für 5. Vector: 271 ms
    Benötigte Zeit für 6. Vector: 26848 ms <-- Was zur Hölle ist das????
    Benötigte Zeit für 7. Vector: 260 ms
    Benötigte Zeit für 8. Vector: 271 ms
    Benötigte Zeit für 9. Vector: 270 ms
    Benoetigte Zeit zum fuellen des Vectors: 30083 ms
    Capacity: 134217728
    Size: 100000000

    Benoetigte Zeit zum anlegen der Deque: 0 ms
    Benötigte Zeit für 0. Deque: 3245 ms
    Benötigte Zeit für 1. Deque: 4887 ms
    Benötigte Zeit für 2. Deque: 5428 ms
    Benötigte Zeit für 3. Deque: 4657 ms
    Benötigte Zeit für 4. Deque: 4687 ms
    Benötigte Zeit für 5. Deque: 4656 ms
    Benötigte Zeit für 6. Deque: 4076 ms
    Benötigte Zeit für 7. Deque: 4026 ms
    Benötigte Zeit für 8. Deque: 4116 ms
    Benötigte Zeit für 9. Deque: 3185 ms
    Benoetigte Zeit zum fuellen der Decue: 43683 ms
    Size: 100000000

    2. 100x 1.000.000 Werte geschrieben (gekürzt):
    ...
    Benötigte Zeit für 63. Vector: 20 ms
    Benötigte Zeit für 64. Vector: 40 ms
    Benötigte Zeit für 65. Vector: 30 ms
    Benötigte Zeit für 66. Vector: 30 ms
    Benötigte Zeit für 67. Vector: 45385 ms <-- schon wieder
    Benötigte Zeit für 68. Vector: 20 ms
    Benötigte Zeit für 69. Vector: 30 ms
    Benötigte Zeit für 70. Vector: 20 ms
    Benötigte Zeit für 71. Vector: 20 ms
    Benötigte Zeit für 72. Vector: 30 ms
    Benötigte Zeit für 73. Vector: 20 ms
    ...
    Benötigte Zeit für 30. Deque: 521 ms
    Benötigte Zeit für 31. Deque: 511 ms
    Benötigte Zeit für 32. Deque: 510 ms
    Benötigte Zeit für 33. Deque: 531 ms
    Benötigte Zeit für 34. Deque: 511 ms
    Benötigte Zeit für 35. Deque: 511 ms
    Benötigte Zeit für 36. Deque: 510 ms
    Benötigte Zeit für 37. Deque: 521 ms
    Benötigte Zeit für 38. Deque: 20 ms
    Benötigte Zeit für 39. Deque: 511 ms
    Benötigte Zeit für 40. Deque: 521 ms
    Benötigte Zeit für 41. Deque: 20 ms
    Benötigte Zeit für 42. Deque: 521 ms
    Benötigte Zeit für 43. Deque: 520 ms
    Benötigte Zeit für 44. Deque: 511 ms
    ...

    Bei 1000x 100 Werten (Weitere Kombinationen kann man auch austesten) hat sich ähnliches gezeigt. Es waren immer beim Vector ziemliche Ausreißer nach oben dabei (Ok mir ist schon klar, daß beim Vergrößern des Vectors dieser komplett kopiert werden muß, aber 36 sec. sind trotzdem etwas viel). Bei der Deque schwanken die Werte zwischen 0 und 500ms (konstant aber da die meisten Werte bei ca 500ms liegen auch etwas langsam).
    Wenn ich einfach in einer Schleife schreibe (war mein erster Test) ist die Performance bei ca 30 Mio Werten gleich (bei kleineren Größen ist die Deque schneller bzw. konstanter, aber das ist mir klar).

    Jetzt meine Fragen:
    Kann mir jemand erklären woher die Ausreißer kommen (Selbst wenn ausgelagert werden müsste sollte das doch schneller gehn, wir verwenden ja schließlich keine Lochkarten mehr 😉 )?
    Deque ist mit 500ms auch teilweise etwas langsam (ok. bei 1mio Werten is des eigentlich schon ok, tritta aber teilweise auch bei Weniger Werten auf), allein an der Ausgabe kann das doch nicht liegen oder?
    Generell denke ich daß ich mit der Deque besser (weil konstantere Speicherzeiten) fahre, und werde das dann mal mit der Deque implementieren.
    PS. Die Compilerkonfiguration ist 'Release', im 'Debug'-Modus kann man das schon nur noch über Nacht laufen lassen!
    PPS. Getestet mit VC98 auf mehreren Rechnern

    Wie immer im Voraus besten Dank und schönes Wochenende!!!

    Gruß
    Threaddy

    0
Anmelden zum Antworten