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!
Werbeanzeige
Administrator
C-/C++-Quelltext |
|
1 2 3 4 |
void Bullet::draw() { drawSprite(x, y, resourceManager.get("Bullet.png")); } |
Administrator
(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).
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).
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?
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.
Solange es keine Hashkollisionen gibt, ist der Zugriff auf die unordered_map §O(1)§.
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".
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...
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 erklären) - so dass der Worst-Case mit 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
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?
Zitat
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?
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.
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »drakon« (31.01.2014, 13:57)
Werbeanzeige