Array oder std::vector?

Gast25250

_42 schrieb:

Wieso zum Teufel nehmt ihr für Arrays std::vector oder boost::array. Bald kommt bestimmt boost::bool.

Haha, sehr gut

Nimm für Bilddaten bitte normale arrays!! Da kannst du dann auch einfach mit read binary Daten reinlesen!

m_image = new char[dim_x*dim_y];
	FileBin.read(m_image , FileSize);
	FileBin.close();

Grüße vom boost:void*

Artchi

Bald kommt bestimmt boost::bool.

Wieso kommt noch? Gibts doch schon!

http://www.boost.org/doc/html/tribool.html

:p

joomoo

Gast25250 schrieb:

_42 schrieb:

Wieso zum Teufel nehmt ihr für Arrays std::vector oder boost::array. Bald kommt bestimmt boost::bool.

Haha, sehr gut

Nimm für Bilddaten bitte normale arrays!! Da kannst du dann auch einfach mit read binary Daten reinlesen!
m_image = new char[dim_x*dim_y];
	FileBin.read(m_image , FileSize);
	FileBin.close();
Grüße vom boost:void*

Nix da Das geht auch mit std::vector:

#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>

int main()
{
    std::vector<char> image;
    std::ifstream file("asd.bmp", std::ios::ate | std::ios::binary);
    assert(file);
    unsigned int filesize = file.tellg();
    file.seekg(0);
    // ...
    image.reserve(filesize);
    file.read(&image[0], filesize);
    // ...
    std::ofstream fout("copy.bmp", std::ios::binary);
    assert(file);
    fout.write(&image[0], filesize);
}

Und hierbei lässt sich nicht so leicht ein delete[] vergessen.

mfg.

DarthZiu

Hab vor ein paar Tagen einen einfachen Laufzeittest mit array vs. vector gemacht (eben wegen Bilddaten).
Probiert das mal bitte aus und sagt mir, welcher Zeitunterschied bei euch rauskommt. Bei mir war das Array um den Faktor 30(!) schneller.
Deswegen hab ich mich erstmal für das Array entschieden.
Aber vielleicht hab ich ja auch falsch gemessen...

#include <iostream>
#include <vector>
#include <windows.h>

using namespace std;

void arr(int size)
{
	int* myArray = new int[size];

	for(int i=0; i<size; i++)
		myArray[i] = 1;

	for(int j=0; j<size; j++)
		myArray[j] *= 3;

	delete[] myArray;
}

void vec(int size)
{
	vector<int>* myVector = new vector<int>;

	for(int i=0; i<size; i++)
		myVector->push_back(i);

	for(int j=0; j<size; j++)
		(*myVector)[j] *= 3;

	delete myVector;
}

void wait()
{
	cin.clear();
	cin.ignore(cin.rdbuf()->in_avail());
	cin.get();
}

int main(void)
{
	double start = 0, end = 0;
	double arrayZeiten[10];
	double vectorZeiten[10];

	for(int i=0; i<10; i++)
	{
		start = GetTickCount();
		arr(300000);
		end = GetTickCount();

		arrayZeiten[i] = end - start;

		start = GetTickCount();
		vec(300000);
		end = GetTickCount();

		vectorZeiten[i] = end - start;
	}

	double arrayD = 0, vectorD = 0;

	for(i=0; i<10; i++)
		arrayD += arrayZeiten[i];

	cout << "Array-Zeiten: " << arrayD / 10 << endl;	

	for(i=0; i<10; i++)
		vectorD += vectorZeiten[i];

	cout << "Vector-Zeiten: " << vectorD / 10 << endl;

	wait();

	return 0;
}

Würd mich mal interessieren, was bei euch für Werte rauskommen.

GPC

Du machst mir Spaß, das Array initalisierst du gleich mit der richtigen Größe und den std::vector nicht, schon klar dass der langsamer ist, der muss ja ständig neuen Speicher herscheffeln. Gib dem vector die Größe gleich im Ctor mit.
Im Übrigen ist es nicht notwendig, den vector selber auf dem Heap anzulegen.

DarthZiu schrieb:

for(int i=0; i<size; i++)
myArray[i] = 1;

for(int i=0; i<size; i++)
myVector->push_back(i);

Ist aber nicht wirklich das gleiche und push_back wird immer langsamer sein als [i].

Artchi

DarthZiu! Du vergleichst einen statischen "Container" mit einem dynamischen Container. Ehm, das passt doch irgendwie nicht. Denn das Array kann in der Form einfach nicht das leisten, was vector leisten kann. Wenn dann müsstest du mit Array die gleich Funktionalität nachbilden: bei jeder Index-Erhöhung das selbst Array resizen. Mal schauen wie schnell du dann bist.

Der Vector spielt dann seinen Vorteil aus, wenn dir beim Anlegen des Containers die Endgröße unbekannt ist. Da kannst du noch soviele Performancetests machen, da wird jeder vector (wenn er vernünftig implementiert ist) sehr gute Arbeit leisten.

Ansonst kann man auch mit reserve()-Methode nach der Vector-Konstruktion die Laufzeit für das push_back drastisch runter drücken. Dann reserviert der Vector schon mal Speicher vor und du kannst trotzdem mit push_back arbeiten, weil die size() dann unabhängig vom reserve() arbeitet. Bei GPC-Vorschlag wäre size() allerdings gleich zu Anfang >0. Dann würde man anstatt push_back() den []-Op oder at() benutzen (wobei at() sicherer gg. Bufferoverflows ist, aber etwas langsamer, ggü. dem unsicheren []-Op).

Man muß einfach nur wissen, wie man vector benutzt, dann arbeitet dieser optimal und sicherer als jedes rohe Array.

DarthZiu

void vec(int size)
{
	vector<int>* myVector = new vector<int>(size);

	for(int i=0; i<size; i++)
		(*myVector)[i] = i;

	for(int j=0; j<size; j++)
		(*myVector)[j] *= 3;

	delete myVector;
}

Ist das jetzt richtig (effektiv)? Immer noch Faktor 10 langsamer als das Array.

DarthZiu

Artchi schrieb:

Man muß einfach nur wissen, wie man vector benutzt, dann arbeitet dieser optimal und sicherer als jedes rohe Array.

Dass ein vector sicherer und komfortabler als ein array ist, ist mir klar. Ich benutze vectoren auch so oft wie möglich.
Mein Problem ist aber, dass ich eine ziemliche Datenmenge (bis zu 20 Bilder pro Sekunde - in einer Auflösung von mindestens 640x480 (307200 Byte-Werte)) erfassen und verarbeiten muss.
Hier wollte ich ebenfalls vector benutzen und habe deswegen diesen "Performance-Test" gemacht. Aber einen Zeitaufwand, der 5 bis 10 mal höher ist, kann ich mir an dieser Stelle einfach nicht leisten.
Das ist der Grund meines ersten Posts.

PS: Vielleicht drücken wir den Zeitaufwand mit weiteren Verbesserungsvorschlägen ja noch auf einen annehmbaren Wert.

Z2

Schon mal versucht das std::vector-Objekt auf dem Stack statt auf dem Heap anzulegen? Dadurch, daß du über einen Zeiger auf dein Objekt zugreifst, hast du eine zusätzliche Indirektion, die Zeit kostet. Kann allerdings auch sein, daß das wegoptimiert wird (dazu wäre es interessant zu wissen mit welchen Optimierungs-Optionen du kompilierst).

Artchi

So, hier mal mein Test:

Ich habe deinen ersten Code so übernommen. Habe die Größe des Übergabe-Params von 300.000 auf 10.000.000 erhöht, weil bei deinen Werten mein Compilat nur 2x so langsam war und nicht 30x. Mit den 10.000.000x10 Durchläufen hat sich das auf 4x verlangsamt.

Zeit: 4 Sekunden für den Vector und 1 Sekunden für das Array.
So, das war jetzt OHNE Reservierung!!!

Compiler: VC++ Toolkit 2003 Professional, Compiler-Optionen: cl.exe /EHsc /G7 /O2 /Og

Vielleicht ist einfach dein Compiler und deine Std-Lib schlecht. 30x ist völlig utopisch bei 300.000 Elementen!

So, meine Änderung am Code:
Ich habe einfach mal 10.000.000 Elemente im Vector reserviert, Push_back() verwendet und den Vector nicht mit new angelegt sondern auf dem Stack.

Ergebnis: sowohl Array als auch Vector brauchen 1 Sekunde!!!!!!!

EDIT: hier noch mal der geänderte Code:

#include <iostream> 
#include <vector>
#include <ctime>

using namespace std; 

void arr(int size) 
{ 
    int* myArray = new int[size]; 

    for(int i=0; i<size; i++) 
        myArray[i] = 1; 

    for(int j=0; j<size; j++) 
        myArray[j] *= 3; 

    delete[] myArray; 
} 

void vec(int size) 
{ 
    vector<int> myVector;
	myVector.reserve(size);

    for(int i=0; i<size; i++) 
        myVector.push_back(i);

    for(int j=0; j<size; j++) 
        myVector[j] *= 3; 
} 

void wait() 
{ 
    cin.clear(); 
    cin.ignore(cin.rdbuf()->in_avail()); 
    cin.get(); 
} 

int main(void) 
{ 

	time_t t = time(NULL);
    for(int i=0; i<10; i++) 
    { 
        arr(10000000); 
	}
    cout << "Array duration: " << (time(NULL) - t) << endl;

    t = time(NULL);
	for(int i=0; i<10; i++) 
	{
        vec(10000000);
    }
	cout << "Vector duration: " << (time(NULL) - t) << endl;

    wait(); 

    return 0; 
}

Shade Of Mine

Artchi schrieb:

Ergebnis: sowohl Array als auch Vector brauchen 1 Sekunde!!!!!!!

klar, es nimmt sich nicht viel. am interessantesten ist ja, dass man die richtige datenstruktur waehlt, die hier eben array ist... wie man dieses array jetzt implementiert ist bei der hoch optimierten standard library von c++ ja schon fast egal.

es ist aber gut zu wissen dass vector immer new aufruft. den speicher also dynamisch allokiert. denn wenn man mal ganz viele kleine vectoren hat, dann _kann_ es mal ins gewicht fallen. wenn wir aber von 1 vector reden, dann ist das einfach nur egal...

push_back() schaut doch immer nach, ob die Größe ausreicht, er kann ja nicht wissen, dass sie reichen muss. Dann muss es doch etwas langsamer sein, als der [] Zugriff, oder?

Artchi

Shade Of Mine schrieb:

es ist aber gut zu wissen dass vector immer new aufruft. den speicher also dynamisch allokiert. denn wenn man mal ganz viele kleine vectoren hat, dann _kann_ es mal ins gewicht fallen. wenn wir aber von 1 vector reden, dann ist das einfach nur egal...

Und? Würdest du nicht viele kleine Vector haben, hättest du viele Arrays die du mit new instanzieren müsstest? Würde es Laufzeitmäßig anders sein? Sicherlich nicht...

Artchi

FrageBehauptung schrieb:

push_back() schaut doch immer nach, ob die Größe ausreicht, er kann ja nicht wissen, dass sie reichen muss. Dann muss es doch etwas langsamer sein, als der [] Zugriff, oder?

Ja, natürlich. Aber soll ich jetzt 1 Mrd. Elemenete puschen, damit man sieht, es dauert 2 sek.? Wenn überhaupt! Leider habe ich hier auf meinem Java-Entwickler-PC kein PlatformSDK, um die Windows-Timefunktion zu nutzen. Kann hier nur Angaben in vollen Sekunden machen. Wer will und ne genauere Zeitmessung machen kann, kann ja ausschliesslich den []-Operator benutzen. Aber das sind schon Containergrößen, die seltener vorkommen. Ich denke, man kann sagen, das Vector nicht so schlecht ist, wie zuerst der Eindruck war. Das C++-Standardkomitee hat sich auf jeden Fall seine Gedanken gemacht.

Artchi

Wer will, und ne genauere Zeitmessung machen kann, kann ja ausschliesslich den []-Operator benutzen. Aber dann auch im Konstruktor gleich die Größe angeben.

LordJaxom

Habe die Messung mal hier auf einem Linux mit g++ 3.2 und der mitgelieferten STL gemacht, allerdings eine Null gestrichen da die Kiste hier recht langsam ist. Zeit wird mit gettimeofday gemessen, compiliert wurde mit -O3. Zugegriffen wird via [].

Array: 550 - 590 ms

Vector (vorher reserve): 600 - 620 ms
Vector (vorher resize): 920 - 1050 ms
Vector (size im Konstruktor): 890 - 910 ms

Finde ich ehrlichgesagt verrückt dass reserve mehr Gewinn bringt als resize - bei dem Unterschied resize <=> Konstruktor könnte ich ja noch damit zufrieden sein dass der Compiler anders optimiert hat. Ich liege doch richtig dass resize die Größe vollständig reserviert und reserve nur ein Hint ist, oder?

Nicht, dass ich gerade eine zeitkritische Anwendung programmiere, aber interessant finde ich es schon

Und hier die gettimeofday-Version des Code:

#include <iostream>
#include <vector>
#include <stdint.h>
#include <sys/time.h>

using namespace std;

uint64_t time_ms()
{
	struct timeval tv;
	gettimeofday(&tv, 0);
	return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

void arr(int size)
{
    int* myArray = new int[size];

    for(int i=0; i<size; i++)
        myArray[i] = 1;

    for(int j=0; j<size; j++)
        myArray[j] *= 3;

    delete[] myArray;
}

void vec(int size)
{
	// 1.
    // vector<int> myVector(size);
	// 2.
	// vector<int> myVector;
	// myVector.reserve(size);
	// 3.
	vector<int> myVector;
	myVector.resize(size);

    for(int i=0; i<size; i++)
        myVector[i] = 1;

    for(int j=0; j<size; j++)
        myVector[j] *= 3;
}

void wait()
{
    cin.clear();
    cin.ignore(cin.rdbuf()->in_avail());
    cin.get();
}

int main(void)
{

    uint64_t t = time_ms();
    for(int i=0; i<10; i++)
    {
        arr(1000000);
    }
    cout << "Array duration: " << (time_ms() - t) << endl;

    t = time_ms();
    for(int i=0; i<10; i++)
    {
        vec(1000000);
    }
    cout << "Vector duration: " << (time_ms() - t) << endl;

    wait();

    return 0;
}

camper

LordJaxom schrieb:

Finde ich ehrlichgesagt verrückt dass reserve mehr Gewinn bringt als resize - bei dem Unterschied resize <=> Konstruktor könnte ich ja noch damit zufrieden sein dass der Compiler anders optimiert hat. Ich liege doch richtig dass resize die Größe vollständig reserviert und reserve nur ein Hint ist, oder?

nein. in beiden fällen wird definitiv genug speicher reserviert. der wesentliche unterschied ist, dass resize die elemente auch initialisiert, während reserve das nicht tut und der vector (also die sequenz von begin() bis end() ) sich nicht verändert - im prinzip müsste der zugriff in diesen uninitialisierten bereich sogar verboten sein (bin jetzt aber nicht ganz sicher im falle von PODs - wir wissen ja, das vector die daten in einem array speichert). folglich ist ein vergleich zwischen new T[] und vector<T> mit resize von vornherein asymmetrisch, denn new T[] tut für PODs etwas, das man mit vector nicht erreichen kann.
ein fairer vergleich müsste also zwischen new T[x]() und vector<T>(x) ablaufen. nat. hindert dich auch niemand daran, vector gleich mit dem korrekten wert zu initialisieren (das ist nun wieder etwas, das mit array-new nicht geht, sofern es nicht der default-wert ist).

void vec(int size)
{
    vector<int> myVector(size,1);
    for(int j=0; j<size; j++)
        myVector[j] *= 3;
}

Shade Of Mine

Artchi schrieb:

Und? Würdest du nicht viele kleine Vector haben, hättest du viele Arrays die du mit new instanzieren müsstest? Würde es Laufzeitmäßig anders sein? Sicherlich nicht...

einfache rechnung:
vector auf stack: 1 new
vector auf freestore: 2 new

array auf stack: 0 new
array auf freestore: 1 new

es macht bei sehr vielen kleinen objeketen einen unterschied. stack ist einfach schneller als freestore.

aber bei wenigen objekten ists egal.

Artchi

Entweder steht ich auf dem Schlauch, oder du. Also, nochmal: wo ist der Vorteil Array auf Stack ggü. Vector auf Stack? Leg ich den Array auf dem Stack an, muß ich zur Compilezeit die Größe kennen. Leg ich den Vector auf dem Stack an, macht er zwar intern ein new, ich kann aber zur Laufzeit die Size bestimmen. Der Vergleich hinkt hier, weil du die Features verheimlichst.

Wie gesagt, ich verstehe den Vorteil des Arrays hier nicht so ganz. Sobald ich mit Array das erreichen will, was Vector auch kann, bringt mir Array keinen Vorteil. Vorteil des Arrays ist nur dann, wenn ich auf Vector-Features verzichten kann.

stack ist einfach schneller als freestore.

Ja, etwas das wir hier alle wissen. Nur hat der Stack auch seine Nachteile. Stack da wo möglich, Heap/Freestore wo nötig. Schön...