Was für containers benützt ihr?



  • 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.



  • hellihjb schrieb:

    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.

    Warum denn nicht? Es kann nur ein Polygon das vorderste sein 😉

    Stell dir einen 1x1 Pixel Bildschirm vor. Zeichnest du 100 Polygone im Frustum, hast du 100 z-Tests mit jeweils einem Overdraw/Fail. Zeichnest du 1000, hast du 1000...

    Natürlich können sie bei einer höheren Auflösung auch nebeneinander liegen, aber das Sichtfeld wird ja nicht irgendwie immer weiter, je mehr Polygone es gibt (wir zeichnen wie gesagt die Polygone im Frustum). Das nebeneinander liegen macht also nur einen konstanten Faktor aus. Wo siehst du das Problem?



  • Stell dir einen 1x1 Pixel Bildschirm vor

    In der Praxis steigt der Overdraw wenn die Flaeche eines zu zeichnenden Polygons unter einen Pixel faellt, also mehrere Polygone pro Pixel zu zeichnen sind.
    In Deinem Spezialfall sind das natuerlich alle, denn es gibt nur ein Pixel - Dein Beispiel ist also nicht sonderlich praxistauglich und deckt sich mit meinem Antibeispiel:

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



  • Damit habe ich auch nur angefangen. Ich habe gezeigt, dass eine höhere Auflösung daran nichts ändert, außer einem konstanten Faktor. Wieviele Pixel ein Polygon einnimmt, ist außerdem egal. Eine höhere Auflösung bewirkt einfach nur, dass generell mehr Pixel zu zeichnen sind, aber das Verhältnis, welche Fläche wie oft überzeichnet wird, bleibt gleich.

    Es zählen die Screenkoordinaten. Daran dass sie auf -1 bis 1 normalisiert sind, siehst du ja schon, wie egal die Auflösung ist. 😉



  • rapso schrieb:

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

    nun, interessant ist es schon aber es ist für mich alles unbekannt und somit komplex

    ich werd mit einfachen container wie list und vector anfangen und ein bißchen mit Zeitstempel experimentieren lassen, um rauszufinden wie schnell die sind.

    Ist es auch ungewiss was für ein Containter der ObjektManager von Cinema4D benützt? Generell die ganzen 3D-Grafikprogramme. Die haben doch alle diese Objekt-Manager. Wenn man 3D-Objekte, Lichtquellen, Effekte usw hinzufügt sind sie alle in der Liste.



  • Wie gesagt, du musst zunächst einmal eine Anforderungsanalyse machen. Du musst dir genau überlegen, was wie oft auf diesen Containern ausgeführt wird. Zum Beispiel "in jedem Frame muss ich ends viele Objekte darin suchen" oder "in einer bestimmten Reihenfolge durchlaufen". Überlege dir auch, wie oft du Objekte hinzufügst und entfernst.

    Wenn du das bestimmt hast, helfen wir dir gerne, den richtigen Container auszuwählen (oder eine Kombination davon). Auf andere Programme zu schauen nützt dir nichts, wenn sie nicht fast gleiche Anforderungen haben. Du musst etwas suchen, was für deinen Fall geeignet ist.


Anmelden zum Antworten