Geschwindigkeit von Assoziativen Arrays
-
Shade Of Mine schrieb:
erklaer mal wie du sie verwendest und vorallem wie sie implementiert sind - dann kann man sagen, ob es lahm ist, oder nicht.
verwendet werden soltlen sie in einem Texturepool in meiner testengine
Es wäre wohl map aus der STL gewesen
Aber ich habe nochmal drüber nachgedacht, und mir ist aufgefallen, dass ich diesen Pool auch genauso gut mit nummern ansprechen kann...
Trotzdem wäre es nett, wenn ihr mir sagen würdet, ob eine STL Map für den Einsatz in einer Engine nicht zu langsam wäre, wenn man sie in jedem Durchlauf der Mainloop einsetzen würde
Mfg Jerdan
-
eine std::map ist meistens als baum implementiert - das kann also uU nicht wirklich ideal sein.
ne hashmap waere bei dir uU besser.
die frage ist immer: wie verwendest du den container.
ich vermute du wirst am anfang den contaiener fuellen, und danach nur noch lookups machen - dann empfiehlt sich ein sortierter vector.
beschreib mal genau deine anforderungen.
-
Brauchst du es sortiert? Dann kommst du wohl kaum besser weg, als mit std::map. Willst du möglichst schnell mit einem index drauf zugreifen? Dann ist ein Hash nicht zu überbieten. Haben die Indizes eine Feste ordnung, sind also einfach durchnummeriert: Dann ist ein Vektor das beste, da dur im gegensatz zum Hash keinen Speicher vergeudest.
-
verwendet werden soltlen sie in einem Texturepool in meiner testengine
Soll es sowas sein wie index -> TexturePointer oder so ...
Für sowas kannst du ohne Probleme ne Map verwenden. Sicher ginge es hierbei mit nem Vector schneller, aber so langsam ist ne map nicht als das man sie nicht normal im Mainloop benutzen könnte. Wenn sie also Vorteile bringt und Notwendig ist sollte man sie durchaus benutzen. Richtig Performancerelevante Routinen brauchen meist eh keinen Map Zugriff.
-
Hi
Also, es geht darum, dass ich Überlege das Laden und Verwalten von Texturen in der Engine derart gestalten will, dass es eine Funktion gibt, durch die Objekte Texturen über Dateinamen anfordern können. Da es aber Schwachsinnig ist, die selbe Textur u.U. 1000 mal zu laden und im Speicher zu haben, möchte ich, dass die Funktion in diesen Container sieht, herausfindet ob eine Textur mit entsprechendem Dateinamen schon geladen wurde, und dann diese Textur zurückgibt, oder falls sie noch nicht geladen wurde, die Textur dann lädt, in den Container packt, und dann zurückgibt.
Es ist Sinn der ganzen Übung, dass es ja auch unterschiedliche Objekte die selbe Textur nutzen können. Und ich will eben diese Textur nicht 2000 mal laden und entsprechend oft im Speicher haben.
Bis jetzt habe ich es so gemacht, dass es eine Klasse Image gibt, die die Bilddaten enthält, in diesem ein SDL_Surface.
Wenn ich nun im Quellcode bemerke, dass verschiedene Objekte die selbe Textur haben, z.B. Sterne, die im Moment noch alle gleich aussehen, erhält die Imageklasse für das Sternobjekt den Befehl, sich die Textur mit einer anderen Imageklasse zu teilen. Bis dahin ist das ja auch kein Problem.
Doch was mache ich, wenn das Objekt, das jetzt tatsächlich die Textur enthält, gelöscht wird? Dann wird ja, wenn man den Aufwand gering halten möchte, auch die Textur gelöscht. Dann sind aber die Objekte, die sich die Textur mit dem nun gelöschten Objekt geteilt haben, plötzlich ohne Textur, und das ganz ohne etwas davon zu wissen. Und was passiert, wenn diese Objekte dann versuchen, die gelöschte Textur zu verwenden? Genau, Sigsev!
Es wäre zwar möglich, die Objekte, mit der ein Objekt sich die textur teilt, in diesem Objekt zu speichern, aber da würde dann der Aufwand doch recht groß.Um nochmal auf den Container zurückzukommen:
Sie würde also jedesmal angesprochen werden, wenn ein Objekt neu erzeugt wird, das heisst unter Umständen mehrere Male pro Schleifendurchlauf.
Meint ihrich könnte dann die Map verwenden?Es ist also das der Gedanke:
Objekt fordert Textur über Dateiname -> Check ob Textur schon geladen ->
a) Textur schon geladen -> Textur wird an Objekt zurückgegeben
b) Textur noch nicht geladen -> Textur laden -> Platzierung im Container -> weiter bei a)So, und dieser Container sollte dann logischerweise auch nicht die Daten der Textur selber beinhalten, sondern einen Pointer auf diese Textur.
BtW: Natürlich speichert die Funktion auch die geladenen Texturen irgendwo ab, damit sie beim Beenden des Programms auch wieder gelöscht werden.
MfG Jerdan
P.S.: Ich hoffe das war verständlich ^^
-
deine anforderung an den container ist also:
schneller insert
schneller lookuploeschen und durchiterieren sowie insert an bestimmten stellen sind dir nicht wichtig?
dafuer eignet sich eine hashmap wohl am besten.
ideal waere es, wenn du fuer die einzelnen texturen die hashfunktion einmal berechnen laesst.du weisst zur compiletime ja schon welche texturen es gibt.
also schreibst du nicht mehr
hashmap["texture.001"]
sondern
hashmap[texture001]wobei texture001 das resultat des bereits gehashten "texture.001" ist. welches natuerlich nur einmal beim programmstart - oder falls moeglich - schon zur compilezeit passiert.
das ganze liefert dir dann einen unglaublich schnellen lookup. nur beim insert, muss texture001 erst wieder in "texture.001" umgewandelt werden. das kostet dann natuerlich etwas mehr - da du ein lookup mehr hast (naemlich in der liste die texture001 mit "texture.001" assoziert)
alles in allem ist das verdammt schnell. du brauchst nur ne gute hashfunktion.
-
Shade Of Mine schrieb:
du weisst zur compiletime ja schon welche texturen es gibt.
Nein, das weiß ich nicht, da ich vorhatte die Level Spielwelten, Level oder was auch immer nicht fest zu integrieren, sondern so etwas über ein Script aufbauen zu lassen, dass dann nur bestimmte Funktionen des Programms aufruft.
Vielliecht ändert sich das ja nochmal, aber die Welten sollen auf keinen Fall fest im Quellcode stehen, daher weiss ich das zur Compiletime noch nicht...
Aber das mit der Hashmap ist ne schlecht
MfG Jerdan
-
Jerdan schrieb:
Nein, das weiß ich nicht
ok, dann geht diese optimierung natuerlich nicht.
aber eine hashmap ist trotzdem wahrscheinlich das beste.
-
Jerdan schrieb:
Wenn ich nun im Quellcode bemerke, dass verschiedene Objekte die selbe Textur haben, z.B. Sterne, die im Moment noch alle gleich aussehen, erhält die Imageklasse für das Sternobjekt den Befehl, sich die Textur mit einer anderen Imageklasse zu teilen. Bis dahin ist das ja auch kein Problem.
Doch was mache ich, wenn das Objekt, das jetzt tatsächlich die Textur enthält, gelöscht wird?Ich habe für die Liste der geladenen Resourcen einen Container mit boost::weak_ptrs (http://www.boost.org) genommen und jedem Objekt, das so eine Resource benutzt, einen boost::shared_ptr auf die Resource gegeben. Wenn nun ein Objekt erstellt wird, guckt es erst, ob irgendein weak_ptr schon auf die entsprechende Resource zeigt und übernimmt diese ggf., ansonsten lädt es sie und trägt sie in den Container ein. Der Container besteht nur aus weak_ptrn, damit er die Resourcen nicht unnötig lange am Leben erhält. Eventuell ist Caching die bessere Lösung, aber das wird dann komplizierter
Jerdan schrieb:
Um nochmal auf den Container zurückzukommen:
Sie würde also jedesmal angesprochen werden, wenn ein Objekt neu erzeugt wird, das heisst unter Umständen mehrere Male pro Schleifendurchlauf.
Meint ihrich könnte dann die Map verwenden?Ich kann mir beim besten Willen nicht vorstellen, dass mehrere Map-Lookups pro Tick _irgendeinen_ Unterschied machen.
-
Wenn ich nun im Quellcode bemerke, dass verschiedene Objekte die selbe Textur haben, z.B. Sterne, die im Moment noch alle gleich aussehen, erhält die Imageklasse für das Sternobjekt den Befehl, sich die Textur mit einer anderen Imageklasse zu teilen. Bis dahin ist das ja auch kein Problem.
Doch was mache ich, wenn das Objekt, das jetzt tatsächlich die Textur enthält, gelöscht wird?Such mal nach 'nem Text über Referenz-Counting. Das behandelt genau das Problem.
Aber für mich sieht das trotzdem nach 'ner globalen hash_map aus.
map bietet eine suche mit O(n log n), hash_map eine mit O(1). du siehst, vor allem bei großen Mengen an Texturen bringt dir der Hash einen unglaublichen Vorteil.