Array oder std::vector?

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...

Shade Of Mine

Artchi schrieb:

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.

es geht doch um ein array von fixer groesse, oder? denn wenn die groesse nicht fix ist, dann faellt ein statisches array ja soweiso weg, oder?

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.

wenn du auf das feature der dynamischen groessen aenderung verzichten kannst ist array besser. das ist der ganze punkt.

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...

exakt. deshalb sehe ich keinen sinn ein statisches array (also ein array mit einer fixen anzahl elemente) auf den freestore zu packen (ausnahme es wuerde den stack sprengen).

wenn wir die groesse des arrays dynamisch wollen dann ist die antwort auf die frage was man nehmen will ja eindeutig, weil ein array die notwendigen features nicht bietet. nur ich hatte mit dem ganzen resize und reserve irgendwie das gefuehl dass es hier um eine fixe anzahl elemente geht...

Artchi

Nein, der Fragesteller will eine Bilddatei reinladen. Diese wird selten immer gleich groß sein. Ich kann mir gut vorstellen, das sie unterschiedliche Größen hat, sowohl Farbtiefe, Pixelanzahl, Fileformatinformationen usw.

Ein Resize ist noch lange kein Indiz dafür, das er zur Compilezeit die Größe kennt. Weiterhin kann es auch sein, das er im Laufe der Bildverarbeitung z.B. das Bild vergrößert oder ähnliches. Ich glaube nicht, das hier im Laufe des Programmverlaufes ein rohes Array bei der Arbeit Vorteile bringt. Von Bufferoverflows lesen wir auf heise.de schon genug.

Shade Of Mine

Artchi schrieb:

Nein, der Fragesteller will eine Bilddatei reinladen. Diese wird selten immer gleich groß sein. Ich kann mir gut vorstellen, das sie unterschiedliche Größen hat, sowohl Farbtiefe, Pixelanzahl, Fileformatinformationen usw.

dann kann man keine statischen arrays verwenden und thema hat sich erledigt.

Ich glaube nicht, das hier im Laufe des Programmverlaufes ein rohes Array bei der Arbeit Vorteile bringt. Von Bufferoverflows lesen wir auf heise.de schon genug.

wir verwenden ja auch alle schoen brav boost::array oder aehnliches. da passiert sowas nicht :p

btw schuetzt dich vector kein bisschen vor einem buffer overflow...

btw schuetzt dich vector kein bisschen vor einem buffer overflow...

und boost::array auch nicht...

DarthZiu

Artchi schrieb:

Nein, der Fragesteller will eine Bilddatei reinladen. Diese wird selten immer gleich groß sein. Ich kann mir gut vorstellen, das sie unterschiedliche Größen hat, sowohl Farbtiefe, Pixelanzahl, Fileformatinformationen usw.

Fast richtig. Es sind zwar Bilddaten, aber die kommen direkt von einer Kamera. Also steht, bevor ich das Bild speichere und bearbeite, die fixe Größe fest und ändert sich nicht mehr, da ich keine zusätzlichen Bildinformationen speichere.