spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi, um Grafiken, Sounds etc. zu handhaben, habe ich Wrapper-Klassen drumrum geschrieben, die das Laden und Freigeben managen. Um nun nicht jedes mal, wenn ich eine bestimmte Ressource benötige, diese wieder zu laden, cacht die Klasse (z.B. die Image-Klasse) alle Ressourcen dieser Art (z.B. die zugehörige SDL_Surface) und indiziert sie anhand ihrer Dateinamen (std::string). Nun überlege ich, ob meine gewählte Datenstruktur (std::map, d.h. assoziatives Array) dafür geeignet ist, oder es eine bessere Datenstruktur für diese Anwendung gibt. std::map hat laut cppreference für Einfügen, Lesen und Löschen jeweils O(log n) - afaik ganz gut. Erachtet ihr den Einsatz in diesem Fall als sinnvoll?

Mir kam noch folgende Idee: Man nehme eine Hashfunktion, die jeden String auf eine der n Positionen abbildet und ein stetiges Array mit n Elementen. Wenn wir vom linearem Hashing ausgehen, müsste das Array entsprechend eine Menge von String-Resource-Tupeln haben, so dass die Laufzeit (wegen des stetigen Arrays) von der Hashfunktion und der Anordnung innerhalb der Tupel-Menge abhängig ist. Komme ich mit dem Ansatz zu einem sinnvollen Ergebnis, oder ist das zu viel um die Ecke gedacht und unnötig?

Vielleicht noch etwas zu Größenordnung von n: Effektiv geht es um ein 2D-Spiel mit Tiles und Sprites. Also sollte ich vermutlich eher Tilesets und Spritesets als einzene Tiles und Spritegrafiken verwenden, um n kleiner zu halten, richtig? Analog brauche ich dann natürlich zu jeder Grafik Offset und Size um die entsprechend Teilgrafik rauszuschneiden xD Sollte aber laufzeittechnisch kein Problem darstellen ....

Falls ich mir eurer Meinung nach zu viele Gedanken mache: sagt es ruhig Im Grunde könnte ich das Caching auch so lassen und ändern sobald es zu Problemen führt - ich habe es ja eigentlich gut gekapselt ... Trotzdem liegt mir das ganze gerade auf dem Herzen

LG Glocke

Die Ressourcen werden i.d.R. nur beim Erstellen der Map und beim erstellen von Objekten auf der Map (was interessanter ist) geholt und die (z.B. Image-)Instanz in der Map bzw. im Objekt gehalten, bis die es nicht mehr braucht. Intern hält das Image dann einen Zeiger auf die eigentliche Resource (z.B. SDL_Surface), d.h. es kann mehrere Images geben, die sich eine Surface teilen. Das hat den Vorteil, dass ich Bedenkenlos ein Image deleten kann, ohne die Resource zu zerstören, die ggf. noch andersweitig verwendet wird. (Dabei zählen Konstruktor und Destruktor mit wie oft eine Ressource verwendet wird, so dass sie erst nach dem "Tod" der letzten Image-Instanz - die sie verwendete - freigegeben wird).

Die unordered_map wäre prinzipiell eine Idee, da mir die Struktur eigentlich egal ist. Mir ist wichtig, dass ich vor allem schnell Suchen kann - Einfügen und Löschen vernachlässige ich hier mal. Allerdings sehe ich den Vorteil beim Suchen nicht ganz:

• Wenn std::map mittels balanciertem binärem Suchbaum implementiert ist, habe ich ja im WorstCase §\mathcal{O}(\log{n})§ Schritte (Divide & Conquer).
  
• Wenn std::unorderer_map mittels verketteter Liste implementiert ist, habe ich im WorstCase §\mathcal{O}(n)§ Schritte (lineare Suche).
  

Beides passt auf die angegebenen Laufzeiten. Jetzt hatte dot schon die (dabei) vernachlässigten Konstanten erwähnt. Wenn ich das ganze aus Sicht der "Algorithmen & Datenstrukturen"-Vorlesung (die ich zur Zeit noch habe) betrachte, erscheint mit std::map "schneller" ... je mehr Ressourcen ich cache, desto besser ist doch die std::map? (z.B. für 100 Ressourcen maximal 7 vs. 100 Schritte). Selbst wenn ich den Average-Case der unordered_map nehme, habe ich da knapp 50 Schritte. Wo liegt mein Denkfehler?

LG Glocke

Zitat von »David Scherfgen«

Ob das so gut ist?
Stell dir mal vor, du hast immer mal wieder eine einzige Instanz von einem Objekt, die nicht lange lebt, z.B. eine Explosionsanimation.
Würden die Bilder der Explosion dann nicht ständig neu geladen und wieder freigegeben?
Da gibt's auf jeden Fall bessere Verfahren, z.B. alles im Speicher behalten, bis er knapp wird (RAM bringt nichts, wenn man ihn nicht benutzt!) und dann etwas freigeben, was lange nicht mehr gebraucht wurde. So wie ein Betriebssystem das auch tut.

Joa, das scheint echt die bessere Variante - die Änderung macht aber keinen großen Implementierungsaufwand

Zitat von »dot«

Solange es keine Hashkollisionen gibt, ist der Zugriff auf die unordered_map §O(1)§.

Ah, das Hashing habe ich dabei komplett vernachlässigt Also arbeitet die unordered_map weniger mit einer verketteten Liste sondern mehr mit einem stetigen Array? (das würde die §O(1)§ erklären) - so dass der Worst-Case mit §O(n)§ den Fall beschreibt, dass alle n Elemente an einer Array-Position landen (und dann dort als verkettete Liste sitzen)? Das ist ja schon ein Most-Evil-Worst-Case Klar, dass ich den dann nicht mit dem §O(\log{n})§ vergleichen sollte xD

Zitat von »dot«

Abgesehen davon ist das Problem eben, dass du in deinen Überlegungen nur die Anzahl der "Schritte" berücksichtigst, nicht aber, wie teuer so ein "Schritt" eigentlich ist; wie man es in der typischen Vorlesung zu Algorithmen & Datenstrukturen eben so macht: Man betrachtet die asymptotische Laufzeit, wobei konstante Faktoren vernachlässigt werden. So lange man es mit hinreichend kleinen §n§ zu tun hat, ist das asymptotische Verhalten aber nicht sehr aussagekräftig, denn 100 extrem billige "Schritte" können immer noch wesentlich schneller sein als 7 extrem teure "Schritte".

Ja, das hat mir schon immer Bauchschmerzen bereitet - ich glaube inzwischen hatte ich mich schon damit abgefunden xD
Aber ich gebe dir vollkommen recht!

Zitat von »dot«

Und im Falle der std::map haben wir es in der Regel mit relativ teuren "Schritten" zu tun. So ein Suchbaum liegt nicht kompakt im Speicher...auf einer modernen CPU ist aber praktisch immer die Speicherlatenz das Bottleneck. Das Traversieren eines Baumes oder einer verlinkten Liste ist im Vergleich zum Durchlaufen eines simplen Arrays extrem langsam, weil der Cache solche Strukturen überhaupt nicht mag. Daher wird std::vector z.B. sehr oft schneller sein als std::list oder std::map...

Der Hauptunterschied zwischen std::vector und std::list ist afaik, dass std::vector ein stetiges Array ist (alles im Speicher also linear dahinter liegt und die Speicheradresse jeder Zelle in konstanter Zeit berechenbar ist) und std::list ein unstetiges Array ist (also eine verkettete Liste wo hier und da mal was im Speicher liegt und wir, um die Zelle zu erreichen, uns mittels next-Pointer durch die Liste hangeln müssen), richtig?
Die Implementierung eines binären Suchbaums sollte ja dann analog zur verketteten Liste funktionieren, nur dass wir bei jedem Schritt zusätzlich die Entscheidung treffen müssen, ob wir den linken oder rechten Knoten betreten. Von daher sollte ich mit Hashfunktion und einem stetigen Array (das was ihr mit der unordered_map angedeutet hattet?) besser fahren - vorausgesetzt die Laufzeit bei Kollisionen macht mir keinen Strich durch die Rechnung ... hab ich das jetzt besser erfassst?

LG Glocke

Okay, danke. Ich denke ich habe jetzt eine ganz gute Orientierung Ich werde mal schauen wie weit ich mit std::map komme und später ggf. auf std::unordered_map wechseln. Da ich das Ressource-Management imho hat gut gekapselt habe (siehe unten), ist der Umstieg kein Problem.
Btw will ich die Resource-Struktur auch für eine Art Wörterbuch verwenden, um die Lokalisierung für Textausgaben (Button-Captions, Quest-Dialoge etc.) darüber zu realisieren; d.h. ich initialisiere ein Wörterbuch mit Key-Value-Paaren (Key z.B. TITLE_QUIT_BTN, Value z.B. "Spiel verlassen") und sammle diese in der Ressourcen-Struktur an, so dass ich nur noch mit einer Methode die Übersetzung für TITLE_QUIT_BTN erfassen und als Caption verwenden muss. Mal schauen wie es läuft

Zitat von »drakon«

Ich denke Heutzutage kannst du getrost alle Resource mal in den Speicher laden und Verweise darauf rumreichen, wenn sie effektiv benutzt werden soll. Da irgendwie ein System mit laden/entladen zu machen lohnt sich kaum für kleinere bis mittlere Projekte.

Der Hauptgrund, dass ich überhaupt einen ResourceManager mit Caching verwenden will, ist, dass ich das ganze Laden/Cachen von Ressourcen kapseln möchte. Dazu habe ich den ResourceManager mit Typparameterern (für Key und Value) implementiert, so dass ich - wenn ich z.B. einen FontManager (auf Basis von z.B. SDL_ttf) schreibe - nur noch eine fetch- (und release-Methode, wenn ich das Löschen mal mit dazubetrachte) implementieren muss. Schließlich habe ich einen Getter, der mir die Ressource liefert - egal ob er sie nun direkt aus der Datei geladen oder aus dem RAM geholt hat. Ich denke durch die Wiederverwendbarkeit der Manager-Struktur lohnt sich sowas auch schon für kleinere Projekte

LG Glocke