Was für containers benützt ihr?



  • hi,

    In einer Spielwelt müssen ja Objekte zur Laufzeit hinzugefügt und wieder zerstört werden. z.b. Geschosse, Gegner.

    ich würde noch so ne einblendbare Tabelle machen, welche Objekte im Spielfeld gerade befinden.

    Wird da nicht map oder set genommen, weil die sehr schnell sind oder?



  • kommt darauf an, wieviele objekte man hat, wieviele man davon braucht und nach welchen kriterien man sie auswaehlt.



  • Kommt sehr auf den Verwendungszweck an.
    Aber generell versuche ich knotenbasierte Typen zu vermeiden.



  • Um eine geeignete Datenstruktur zu wählen, überlegt man sich, welche Operationen darauf ausgeführt werden müssen.



  • hellihjb schrieb:

    kommt darauf an, wieviele objekte man hat, wieviele man davon braucht und nach welchen kriterien man sie auswaehlt.

    hm also es werden schon sehr viele Objekte sein (über 10.000) und dennoch muss man sie verwalten können, wie die Ebenen in Photoshops Ebenenfenster. also: sortiments frei gestaltbar. Indem man in der Tabelle auf sie draufdrückt und nach oben oder unten verschiebt.

    this->that schrieb:

    Kommt sehr auf den Verwendungszweck an.
    Aber generell versuche ich knotenbasierte Typen zu vermeiden.

    was sind knotenbasierte typen?



  • xBlackKnightx schrieb:

    hellihjb schrieb:

    kommt darauf an, wieviele objekte man hat, wieviele man davon braucht und nach welchen kriterien man sie auswaehlt.

    hm also es werden schon sehr viele Objekte sein (über 10.000) und dennoch muss man sie verwalten können, wie die Ebenen in Photoshops Ebenenfenster. also: sortiments frei gestaltbar. Indem man in der Tabelle auf sie draufdrückt und nach oben oder unten verschiebt.

    Entscheidend sind lediglich die Operationen AUF dem Container. Brauchst du oft Random Access? Wird oft eingefügt? Wo wird oft eingefügt? Musst du oft einzelne Objekte löschen usw. Gibt da schöne O-Notations Tabellen, die die Datenstrukturen vergleichen.

    this->that schrieb:

    was sind knotenbasierte typen?

    Alle Strukturen, die intern Knoten ("Zeiger") benutzen wie verkettete Listen, Bäume etc.



  • Und wenn kein Container so richtig passt kann man immer noch mehrere Container verwenden, oder gleich einen "multi index container" wie er z.B. in der Boost implementiert ist.


  • Mod

    welche operationen man auf einem container ausfuehrt, hat nicht unbedingt einen zusammenhang mit der O notation, denn die kann behaupten dass die komplexitaet O(log n) ist und die reale zeit kann trotzdem bei einem container mit O(n) schneller sein.
    bespiele?

    raytracer O(log n) vs rasterizer O(n)
    std::map mit einfuegen/loeschen O(log n) vs std::vector einfuegen O(1)oder O(n)/delete O(n) (z.b. bei particlesystemen)

    trotzdem nutzen spiele meist rasterizer und vectoren wenn's geht.

    aber grundsaetzlich ist es fallabhaengig, es haengt also vom koennen des programmierers ab, ob er fuer einen speziellen fall das beste waehlt.

    deswegen @xBlackKnightx, nimm das beste fuer deinen fall 🤡, manchmal ist es auch so gut wie egal was man nimmst;), es ist dann besser das langsamste zu nehmen als eine diskusion zu fuehren was zu nehmen ist.

    -rapso



  • Das ist eben der Nachteil der O-Notation, dass g Element O(f) mit g <= c*f erst ab einem n0 gelten muss, dass beliebig groß sein kann.

    Wieso hat ein Raytracer laut deiner Aussage eigentlich O(logn)?


  • Mod

    this->that schrieb:

    Das ist eben der Nachteil der O-Notation, dass g Element O(f) mit g <= c*f erst ab einem n0 gelten muss, dass beliebig groß sein kann.

    Und es kommt auch drauf an wie man einen container benutzt.

    Wieso hat ein Raytracer laut deiner Aussage eigentlich O(logn)?

    Weil mit (statischen) Polygonen (n=poly) aufgrund der hierarchischen baume, die laufzeit logaritschmisch steigt.
    Theoretisch ist also ein raytracer irgendwann schneller als ein rasterizer.



  • rapso schrieb:

    welche operationen man auf einem container ausfuehrt, hat nicht unbedingt einen zusammenhang mit der O notation, denn die kann behaupten dass die komplexitaet O(log n) ist und die reale zeit kann trotzdem bei einem container mit O(n) schneller sein.

    Ja, es kann sein und ich wollte es auch nicht ausgeschlossen haben. Dennoch ist die prinzipielle Vorgehensweise bei der Auswahl einer Datenstruktur immer noch die, dass man sich überlegt, welche Operationen darauf schnell ausgeführt werden können müssen... diese Regel hat sogar noch nicht mal was unbedingt mit der O-Notation zu tun.

    Der größte Fallstrick bei Big-O ist eh, dass man die Elementaroperation falsch bestimmt. Viele Leute haben mir schon gesagt "viel wichtiger als Big-O ist doch, dass alles in die Caches passt". Aber wenn die Caches so wichtig sind, dann muss man eben die Cache-Misses als Operation heranziehen. Nicht umsonst gibt es zum Beispiel B-Bäume für Datenbanken. Da findet viel I/O statt und die B-Bäume versuchen genau, diese Zugriffe zu verringern, um die Speicherhierarchie bestmöglich zu nutzen.

    btw. beim Rasterizen ist es doch auch so, dass man eine Raumunterteilung vornehmen kann, die meistens auf baumartigen Strukturen basiert. Weil ich von diesem Intel-gesponsortem Projekt auch schon mal so eine Aussage gehört hab à la "raytracen skaliert besser": Vielleicht sollte man die Gesamtzahl der Polygone einer virtuellen Welt als n heranziehen. Dann hab ich in beiden Fällen sowas wie log n. Raytracen ist vielleicht günstiger, wenn man alle Polygone sehen kann, aber das ist ja wohl in der Regel nicht der Fall. Ich kenn mich jetzt mit dem Raytracen nicht so aus. Ich habe nur ein Verständnisproblem damit, dass Raytracen laut O-Notation besser sein soll.


  • Mod

    Optimizer schrieb:

    rapso schrieb:

    welche operationen man auf einem container ausfuehrt, hat nicht unbedingt einen zusammenhang mit der O notation, denn die kann behaupten dass die komplexitaet O(log n) ist und die reale zeit kann trotzdem bei einem container mit O(n) schneller sein.

    Ja, es kann sein und ich wollte es auch nicht ausgeschlossen haben. Dennoch ist die prinzipielle Vorgehensweise bei der Auswahl einer Datenstruktur immer noch die, dass man sich überlegt, welche Operationen darauf schnell ausgeführt werden können müssen... diese Regel hat sogar noch nicht mal was unbedingt mit der O-Notation zu tun.

    jap, schnell im sinne der laufzeit, nicht der laufzeitkomplexitaet.

    Der größte Fallstrick bei Big-O ist eh, dass man die Elementaroperation falsch bestimmt. Viele Leute haben mir schon gesagt "viel wichtiger als Big-O ist doch, dass alles in die Caches passt". Aber wenn die Caches so wichtig sind, dann muss man eben die Cache-Misses als Operation heranziehen. Nicht umsonst gibt es zum Beispiel B-Bäume für Datenbanken. Da findet viel I/O statt und die B-Bäume versuchen genau, diese Zugriffe zu verringern, um die Speicherhierarchie bestmöglich zu nutzen.

    Das ist bereits enthalten, stell es dir als n*(operation+Cachemiss) vor, bei der O notation laesst man dann die konstanten weg wie du sicherlich weisst, ich will's nur noch mal betont haben 😉

    btw. beim Rasterizen ist es doch auch so, dass man eine Raumunterteilung vornehmen kann, die meistens auf baumartigen Strukturen basiert. Weil ich von diesem Intel-gesponsortem Projekt auch schon mal so eine Aussage gehört hab à la "raytracen skaliert besser": Vielleicht sollte man die Gesamtzahl der Polygone einer virtuellen Welt als n heranziehen. Dann hab ich in beiden Fällen sowas wie log n. Raytracen ist vielleicht günstiger, wenn man alle Polygone sehen kann, aber das ist ja wohl in der Regel nicht der Fall. Ich kenn mich jetzt mit dem Raytracen nicht so aus. Ich habe nur ein Verständnisproblem damit, dass Raytracen laut O-Notation besser sein soll.

    klar kannst du noch culling in rasteriser einbauen, jedoch geht man laut der Rechnung von Prof.Dr. Milchmaenchen 🤡 davon aus, dass du beim rasterisieren jedes dreieck anfasst (sprich, in screenspace transformierst und rasterisierst bis dir der zbuffer sagt ob das ding zu sehen ist oder nicht).
    Als beispielbild gibt es dann meist das feld mit sonnenblumen an, die alle 'highpoly' sind.
    Dass es besser geht, zeigt Crysis.


  • Mod

    @xBlackKnightx wenn du denkst dass das hier komplett von dem abweicht was dich interresiert, sag bescheid und ich splitte es ab 😉



  • Wieso hat ein Raytracer laut deiner Aussage eigentlich O(logn)?

    Weil mit (statischen) Polygonen (n=poly) aufgrund der hierarchischen baume, die laufzeit logaritschmisch steigt.
    Theoretisch ist also ein raytracer irgendwann schneller als ein rasterizer.

    Das ist schlecht zu vergleichen, denn O(log n) ist hier der Aufwand pro Strahl (bei einer Rekursionstiefe von 1 also der Aufwand pro Pixel) und damit wiederum abhaengig von der Aufloesung - der Pro-Pixel-Aufwand des Rasterizers ist primaer abhaengig vom Overdraw
    Daraus lernen wir also nur, dass bei einer Aufloesung von 1x1 Pixel ein hierarchischer Raytracer immer schneller ist...

    dass du beim rasterisieren jedes dreieck anfasst

    Dann muss man fuer den Raytracer aber auch schon brute-force annehmen...



  • hellihjb schrieb:

    Das ist schlecht zu vergleichen, denn O(log n) ist hier der Aufwand pro Strahl (bei einer Rekursionstiefe von 1 also der Aufwand pro Pixel) und damit wiederum abhaengig von der Aufloesung - der Pro-Pixel-Aufwand des Rasterizers ist primaer abhaengig vom Overdraw

    Ja und der Overdraw/z-fail liegt in O(n); n == Anzahl der Polygone im viewing frustum. Insofern ist das schon richtig gewesen. Es kann ja O(n/10000) sein, aber eben O(n).

    rapso schrieb:

    klar kannst du noch culling in rasteriser einbauen, jedoch geht man laut der Rechnung von Prof.Dr. Milchmaenchen 🤡 davon aus, dass du beim rasterisieren jedes dreieck anfasst (sprich, in screenspace transformierst und rasterisierst bis dir der zbuffer sagt ob das ding zu sehen ist oder nicht).

    Ja es stimmt schon. Das eigentliche Zeichnen ist wirklich O(Anzahl Polygone im Viewing Frustum), beim Raytracer nicht notwendigerweise. Wahrscheinlich ist die Idee, dass je mehr Polygone im Frustum sind, desto mehr werden verdeckt.

    btw. der Link zum Sonnenblumenfeld geht nicht 😞


  • Mod

    hellihjb schrieb:

    Wieso hat ein Raytracer laut deiner Aussage eigentlich O(logn)?

    Weil mit (statischen) Polygonen (n=poly) aufgrund der hierarchischen baume, die laufzeit logaritschmisch steigt.
    Theoretisch ist also ein raytracer irgendwann schneller als ein rasterizer.

    Das ist schlecht zu vergleichen, denn O(log n) ist hier der Aufwand pro Strahl (bei einer Rekursionstiefe von 1 also der Aufwand pro Pixel) und damit wiederum abhaengig von der Aufloesung

    diese Angabe bezieht sich auf den aufwand in relation zu der polygonzahl, fuer die aufloesung ist der aufwand O(n) (sofern man keine coherenzoptimierungen vornimmt)

    - der Pro-Pixel-Aufwand des Rasterizers ist primaer abhaengig vom Overdraw

    jein, bei extrem grossen polygonmengen zeichnen die meisten polys nichtmal einen pixel, der aufwand liegt dann constant pro poly das hinzukommt, also O(n). von diesem fall sprechen die Raytracing verfechter dann, denn logischerweise muss irgendwo ein raytracer mit O(log n) schneller sein als ein rasterizer mit O(n). natuerlich ist das ganze komplett praxisfern.

    Daraus lernen wir also nur, dass bei einer Aufloesung von 1x1 Pixel ein hierarchischer Raytracer immer schneller ist...

    das stimmt natuerlich auch 🙂

    dass du beim rasterisieren jedes dreieck anfasst

    Dann muss man fuer den Raytracer aber auch schon brute-force annehmen...

    nicht zwingend. man kann schon konstelationen finden bei denen ein raytracer theoretisch schneller sein wuerde. wenn eben milliarden an blumen sichtbar vor dir sind. ein rasterizer mueste im stumpfen fall alle rasterisieren. ein raytracer wuerde sich nur die richtigen polys 'rauspicken'.

    deren argumente sind faktisch nicht falsch, sie sind nur fuer bedingungen angegeben die in der realitaet niemand machen wuerde.



  • Ja und der Overdraw/z-fail liegt in O(n); n == Anzahl der Polygone

    Zeig mal bitte, warum der Overdraw eines Rasterizers linear mit der Anzahl der Polygone steigt.


  • Mod

    Optimizer schrieb:

    btw. der Link zum Sonnenblumenfeld geht nicht 😞

    wieso nicht? 404 oder hotlink protection? bei mir geht's (tm)

    vielleicht copy&paste http://blog.koehntopp.de/uploads/sunflowers.jpg 🙂



  • Hallo

    Ich bekomme immer Fehler 403:

    Forbidden

    You don't have permission to access /uploads/sunflowers.jpg on this server.

    chrische



  • Es war 403 aber mit c&p gings.


Log in to reply