Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

C++ 2D Array

Werbeanzeige

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

11

13.11.2013, 21:06

Verschachtelte Vektoren (vector<vector<X>>) sollte man eher nicht benutzen, auch aus dem Grund, den Jonathan_Klein schon genannt hat.
Zudem können hier Inkonsistenzen entstehen, wenn nicht alle Vektoren gleich lang sind.

Ich benutze normalerweise auch ein einfaches Array (bzw. Vektor) und organisiere den Inhalt spaltenweise von "oben" nach "unten". So wie man Texte zeilenweise von oben nach unten liest und jede Zeile von links nach rechts ;)
David Scherfgens Website | Konzentrationstest Polizei

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

12

13.11.2013, 21:59

Zum Thema Memory sehr empfehlenswert: http://channel9.msdn.com/Events/Build/2013/4-329
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

anti-freak

Alter Hase

Beiträge: 635

  • Private Nachricht senden

13

14.11.2013, 08:22

Für multidimensionale Container, die zur Laufzeit ihre Größe ändern sollen, nutze ich eigentlich ganz gerne
http://www.boost.org/doc/libs/1_54_0/lib…/reference.html

Wundert mich, dass es sowas noch nicht im C++ Standard gibt.

ERROR

Alter Hase

  • »ERROR« ist der Autor dieses Themas

Beiträge: 417

Wohnort: Paderborn

Beruf: Informatik Student

  • Private Nachricht senden

14

14.11.2013, 10:22

Ich habe jetzt mal kleine Tests durchgeführt und hier sind meine Ergebnisse:


C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10

void ArrXY::Fill()
{
    for(int w = 0; w < b; w++)
    {
        for(int h= 0; h < a; h++)
        {
            arr[h][w] = 1;
        }
    }
}

Dauer: 0.06 Sekunden


C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10

void ArrYX::Fill()
{
    for(int h = 0; h < a; h++)
    {
        for(int w = 0; w < b; w++)
        {
            arr[h][w] = 1;
        }
    }
}

Dauer: 1,26 Sekunden


Eine von Jonathan inspirierte Anwendung des Vectors:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class vec2D
{
    std::vector<int> data;
    int width, height;
public:
    void init(int w, int h)
    {
        data.reserve(w*h);
        width = w;
        height = h;
    }
    int& Access(int x, int y)
    {
        return data[x+y*width];
    }
    void Fill()
    {
        for(int y = 0; y < height; y++)
        {
            for(int x = 0; x < width; x++)
            {
                Access(x,y) = 1;
            }
        }
    }
};

Dauer (Debug)0.40 Sekunden, (Release)0.1 Sekunden
(ob erst x dann y oder umgekehrt in den beiden for macht bei diesr Methode keinen wirklichen Unterschied, allerdings dauert das reservieren für den Vector ne Ewigkeit)


Was mich jetzt wundert ist vor allem, dass ich gedacht hätte dass die beiden Array Methode genau anders rum sind von der Dauer her. Ausserdem ist der Vector ja langsamer als das Array.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »ERROR« (14.11.2013, 10:54)

eXpl0it3r

Treue Seele

Beiträge: 386

Wohnort: Schweiz

Beruf: Professional Software Engineer

  • Private Nachricht senden

15

14.11.2013, 10:35

Ist jetzt natürlich etwas schwierig so zu überprüfen da du die Initialisierung beim Array ja nicht mit einbezogen hast - ein statisches Array steht daher bereits bei der Ausführung der Applikation bereit. Falls du es etwas fairer machen möchtest solltest du ein dynamische Array verwenden. Auch darfst du nicht vergessen das alles im Release Mode zu testen, weil ein Vektor im Debug Modus noch asserts und ähnlich verarbeiten könnte was ihn auch langsamer macht als ein normales Array das gar keine Überprüfungen enthält. ;)

Die Reihenfolge sollte auch im Vektor eine Rolle spielen, da ein Vektor unter der Haube ebenfalls ein Array ist, ob du nun im Speicher hin und her springst oder diesen Schritt für Schritt liest hat einen relative grossen Einfluss auf die Performance des Caches und deshalb der gesamten Applikation.
Blog: https://dev.my-gate.net/
—————————————————————————
SFML: https://www.sfml-dev.org/
Thor: http://www.bromeon.ch/libraries/thor/
SFGUI: https://github.com/TankOs/SFGUI/

ERROR

Alter Hase

  • »ERROR« ist der Autor dieses Themas

Beiträge: 417

Wohnort: Paderborn

Beruf: Informatik Student

  • Private Nachricht senden

16

14.11.2013, 10:54

Im Release Modus braucht der Vector zum befüllen 0.1 Sekunden. Die Arrays bleiben gleich.

Die Reservierungszeit habe ich allerdings beim Vector nicht mitberechnet. Also die 0.1 Sekunden sind nur das Befüllen.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

17

14.11.2013, 11:16

Ich denke man sieht eindeutig genug, was passiert, wenn man multidimensionale Arrays für den Cache ungünstig anspricht.
Mich hätte aber auch interessiert welchen Unterschied int[][] und std::array<std::array<int>> hier macht.
0.1 Sekunden sind aber generell zu wenig, um daraus eine akkurate Entscheidung abzuleiten. Konkret wenn die Höhe und Breite ebenfalls unbekannt sind. Am Ende sind die Werte so gigantisch, dass sie völlig irrelevant sind. In der Praxis wird es jede Variante mit ausreichend Performance tun. Drauf achten kann man auf die richtige Zugriffsreihenfolge natürlich trotzdem.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

KeksX

Community-Fossil

Beiträge: 2 107

Beruf: Game Designer

  • Private Nachricht senden

18

14.11.2013, 12:17

Naja, Schorsch hat das vielleicht noch etwas unklar ausgedrückt, aber der Performancetest ist natürlich je nach Umgebung unterschiedlich. Es gibt verschiedene Optimierungsstufen die das Array "verbessern" können und den vector sogar "entoptimieren" können. Ich kann mir gut vorstellen, dass bei dir in dem Fall die Optimierung nicht optimal(hah..) für den vector ist. Der vector, wie schon angesprochen, arbeitet anders, also speichert nicht konsekutiv in einen Block sondern in mehrere Speicherblöcke etc. Außerdem arbeitet er auf dem Heap(im Gegensatz zum Stack), was sich auch nochmal auswirkt.

Aber siehst du, so einfach hast du bewiesen, dass wir alle in diesem Fall falsch lagen und performancetechnisch ein array für dich gerade besser ist. :thumbsup:

Aber vector hat ja noch ganz andere Vorteile, als die Performance. Allein die ganzen Hilfsfunktionen. Was, wenn du einen Bereich ansprechen willst, den es nicht gibt? vector hat dafür die schöne .at() Funktion, die dir auch Fehler auswirft, wenn was nicht passt. Mit lediglich dem [] operator wird das Programm abstürzen. Du könntest dir das jetzt natürlich selbst für dein Array schreiben, aber warum das Rad neu erfinden?:).

Edit: std::array hat das nebenbei auch. Das ist das schöne an der STL, alles verfolgt das gleiche Prinzip!
WIP Website: kevinheese.de

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »KeksX« (14.11.2013, 12:23)

ERROR

Alter Hase

  • »ERROR« ist der Autor dieses Themas

Beiträge: 417

Wohnort: Paderborn

Beruf: Informatik Student

  • Private Nachricht senden

19

14.11.2013, 12:25

Aber wie kann ich den Vector denn noch mehr optimieren?

Ich würde schon gerne die Vorteile des Vectors nutzen, nur dafür müsste er ja noch etwas schneller werden.

KeksX

Community-Fossil

Beiträge: 2 107

Beruf: Game Designer

  • Private Nachricht senden

20

14.11.2013, 12:34

Zitat von »ERROR«

Aber wie kann ich den Vector denn noch mehr optimieren?

Ich würde schon gerne die Vorteile des Vectors nutzen, nur dafür müsste er ja noch etwas schneller werden.


Okay, da habe ich mich jetzt etwas doof ausgedrückt: Hier ist der klare Unterschied, dass du einerseits auf dem Stack arbeitest beim Array und andererseits auf dem Heap mit dem Vector. Im Endeffekt sind beides arrays, der vector nur mit einem großen Bauwerk(die Hilfsfunktionen etc) drumrum. Wenn du jetzt beim array auch auf dem heap arbeiten würdest, würdest du wahrscheinlich immer noch keinen Unterschied merken. Aber mit normalen Arrays auf dem Heap zu arbeiten führt zu vielen Problemen, und wenn wir hier von einem nicht zu merkenden Performanceunterschied ausgehen, dann lohnt es sich alle male hier zum vector zu greifen.

Zur Optimierungsgeschichte:
Das könntest du machen, führt aber nur zu Komplikationen die du hier nicht brauchst. Es gibt da den schönen Spruch "Premature Optimization is the root of all evil", der hier auch zutrifft. Kümmer dich nicht zu viel darum, dass das schneller sein könnte.
Wir haben hier einen Fall gemessen, bei dem wir die Umgebung nicht kennen und sind zum Entschluss gekommen, dass das array hier tatsächlich spürbar schneller ist. Mögliche Gründe dafür sind bekannt, aber da müssten wir jetzt einen nächsten Test ransetzen um das zu überprüfen etc etc.

Darum ist es hier einfach zu sagen:
Am Ende haben wir ein array und ein array mit einem Kasten drum. Das führt dazu, dass das Array mit einem Kasten drum etwas langsamer ist, aber wennn wir mal ehrlich sind ist das erst spürbar wennn wir von >1 Milliarde Datensätze reden. Wenn du nicht gerade für die NSA arbeitest ist das also nicht relevant ;)

EDIT:
Kurz nochmal rumgegooglet. http://stackoverflow.com/questions/16446…ray-performance
Da sieht man, dass mit entsprechender Optimierung der vector tatsächlich schneller sein kann als das statische array.
WIP Website: kevinheese.de

Werbeanzeige

Ähnliche Themen