STL ungeeignet für Spieleprogrammierung?
-
Kane schrieb:
Einfach mal die std::vector-Docu lesen und man wird feststellen dass "floats" sich durch das push_back jedes mal neuen Speicher allokieren muß.
aber auch nur, wenn der vector von einem blindgänger implementiert wurde, der nichtmal soweit denkt, daß man vielleicht schonmal MEHR als nur platz für den einen float zusätzlich anfordern sollte. da dürfte es üblicher sein, den speicher bei jeder anforderung zu verdoppeln.
-
genau das ist das problem der stl. niemand weiß bei welcher implementierung man sich auf was verlassen kann. wovon man ausgehen kann das es selbstverständlich ist und für welchen sonderfall man was anderes annehmen muss.
stl ist halt eine allgemeine lösung für immerwieder kehrende probleme die zwar natürlich an sich möglichst performant gecodet wird, aber genauso wie man sich arbeit abnehmen lässt, nimmt man sich jegliche möglichkeit ein kontrolle zu haben wie sie optimiert wird.
ich würde z.b. gerne mal ne schleife schreiben wie while(container.size()!=0)... ist aber sehr viel langsammer als while(!container.empty())... was ist nun aber wenn ich while(container.size()>10) schreiben möchte? schon hört es auf mit der performance oder der abnahme der arbeit beim implementieren... (btw. ich hab diese erkenntnis dass empty schneller ist schmerzhaft selbst gemacht, aber sowas steht natürlich auch in "effective c++")
die stl ist an sich hochgeeignet für spieleprogrammierung solange man weiß wie und wofür sie genau verwendet werden darf, und wofür das nicht der fall ist.
in deinem beispiel hätte ich einen vector genummen und über myVector[bla%myVectorsizeOfThisCoolSnake] darauf indiziert, wobei bla dann der aktuelle logicdurchgang ist. geht's einfach und effektiver?
rapso->greets();
-
@rapso:
Dass steht schon genau fest welcher Aufruf wie lange (zumindest theoretisch braucht). Also O(1), O(n) etc.
Und dass std::list::size() O(n), also linear, ist und damit natürlich langsamer als std::list::empty() habe ich auch mal in irgend einer Doku gelesen.Btw guter Link zu dem Thema:
http://www.tantalon.com/pete/gdc2001roundtablereport.htm
-
Nachtrag wegen Performance:
http://www.codecreator.net/stl_table.gif
-
Kane schrieb:
@rapso:
Dass steht schon genau fest welcher Aufruf wie lange (zumindest theoretisch braucht). Also O(1), O(n) etc.
Und dass std::list::size() O(n), also linear, ist und damit natürlich langsamer als std::list::empty() habe ich auch mal in irgend einer Doku gelesen.Btw guter Link zu dem Thema:
http://www.tantalon.com/pete/gdc2001roundtablereport.htmSo logisch, wie das auf den ersten Blick scheint, ist das nicht. Die O-Notation gilt für große n, weil man nur dann konstante Faktoren vernachlässigen. In unserem Fall ist aber n = 0, was nicht sehr groß ist.
-
ahh.. meine beliebte o-notation, die zwar ganz nett ist, aber einem oft irgendwie so gar nichts weiterhilft. O(n) ist besser als O(n^2)? für theoretiker schon, wenn in der praxis aber einmal der faktor 1000 und einmal der faktor 1 vorhanden wären, dann wirds in vielen "realen" fällen schon unsinnig.
soweit ich das im hinterkopf habe, ist bei der stl nichtmal vorgeben, für welchen container welche interne repräsentation als standard benutzt werden soll (aber wenigstens läßt sich das zur sicherheit sowieso angeben).
daß size allerdings so langsam ist verblüfft mich ein wenig. eigentlich hätte ich gedacht, daß size sowieso als wert im container liegt und nur bei änderung aktualisiert wird, aber nicht, daß bei jedem aufruf wieder relativ sinnlos neu nachgezählt wird. vor allem wäre empty dann ganz faul als return !_size implementiert *fg*
-
Die Implementierung ist zwar nicht vorgeschrieben, aber sehr wohl die Zeitkomplexität, die von den Implementierungen nicht überschritten werden darf.
size wird in aller Regel schon vorrätig gehalten, bei verketteten Listen verzichtet man allerdings oft darauf, um schneller splicen zu können.Dein Faktor 1 und 1000 nebeneinander ist wohl eher Unsinn. Die O-Notation ist in aller Regel schon ein guter Anhaltspunkt. Nur bei n = 0 halt vielleicht nicht gerade. ;/
-
Optimizer schrieb:
Dein Faktor 1 und 1000 nebeneinander ist wohl eher Unsinn. Die O-Notation ist in aller Regel schon ein guter Anhaltspunkt. Nur bei n = 0 halt vielleicht nicht gerade. ;/
und auch bei vielen anderen n nicht und spätestens bei "kritischen" stellen kann mans sowieso knicken. da dürften einige mit der gleichen komplexität wie bresenham eine linie pinseln und können trotzdem 10x schneller sein. von besonders großem n ausgehen und faktoren wegwerfen mag ja z.b. bei datenbanken noch ok sein, aber sobald n recht überschaubar wird ist der faktor in meinen augen zu wichtig, um den einfach unter den tisch zu kehren.
-
Na, wenn du das meinst, bitteschön.
Eine Sortierung mit n*log(n) ist mir trotzdem lieber als mit n^2. Wenn man den 2er Logarithmus (ungünstigster Fall) zugrunde legt und noch mal ganz allgemein den n*log(n) mit Faktor 4 "bestraft" (keine Ahnung wofür), lohnt er sich trotzdem schon bei nur 16 Elementen.
Aber du wirst es schon wissen...
Glaubst du die O-Notation ist ein Hirngespinnst?
-
Optimizer schrieb:
Aber du wirst es schon wissen...
Glaubst du die O-Notation ist ein Hirngespinnst?nein, ich denke die o-notation ist das typische spielzeug theoretischer informatiker, die nur zu gerne vergessen, daß sie bestenfalls eine grobe einschätzung erlaubt, weil sie einfach mal auf annahmen aufbaut, die man in der praxis vielleicht oft, aber bestimmt nicht immer vorfindet.
lohnt er sich trotzdem schon bei nur 16 Elementen.
eben, und wenn ich einen fall habe, bei dem ich schon vorher weiß, daß es nie mehr als 10 elemente sein werden? dann kann mal eben ein für große n unbrauchbarer algo deutlich besser geeignet sein. so wie man mit seinem baum fürs culling tierisch auf die schnauze fliegt, wenn man merkt, daß bis zu x-tausend tests brute-force jeden patch zu testen schneller ist. warum? reichlich overhead für den baum und ein komplexerer test, der fälle berücksichtigen muß, die einem sonst egal wären. da kann der quadtree von mir aus auch gerne log(log(n)) haben, solangs mit n trotzdem schneller läuft.
-
eben, und wenn ich einen fall habe, bei dem ich schon vorher weiß, daß es nie mehr als 10 elemente sein werden?
Wenn ich 10 Elemente habe, dann kann ich die Elemente auch so lange zufällig durchmischen, bis sie sortiert sind.
Jetzt wird dir gerade durch den Kopf schießen "ja lol die 10 war doch nur ein Beispiel, es kann ja auch bei 1000 noch besser sein", aber das ist in aller Regel nicht der Fall.
Die Unterschiede sind bei verschiedenen Ordnungen gigantisch und wenn du nicht gerade sehr kleine n's unter 100 und unrealistische Faktoren mit weit über 1000 annimmst (wo soll bitte Overhead herkommen, der alles aus Prinzip schon 1000mal langsamer macht?), bist du mit einer besseren Ordnung immer besser dran.nein, ich denke die o-notation ist das typische spielzeug theoretischer informatiker
Ja, du hast keine Theorie mehr nötig. Mit deiner großen Praxiserfahrung bist der absolute Experte jetzt.
-
Um nochmal zur Frage zurück zu kommen: die STL ist schnell genug für die Schlange...
Bye, TGGC (Dem beste BdT)
-
Und theoretische Informatiker haben ganz andere Spielzeuge...
frag doch mal elise.
-
Optimizer schrieb:
Jetzt wird dir gerade durch den Kopf schießen "ja lol die 10 war doch nur ein Beispiel, es kann ja auch bei 1000 noch besser sein", aber das ist in aller Regel nicht der Fall.
bis zu dem beispiel mit dem baum hast du wohl nicht gelesen? und das war ein baum, der noch ausreichend optimiert wurde, iterativ durchlaufen mit vorreserviertem speicher. vorher war das ding noch langsamer und JA, das war im tausender bereich. und in so einem fall denk ich mir nicht "aber in der regel wärs so", oder "aber laut komplexität kann das ja gar nicht sein", sondern "hoppla, was nu los?"
Ja, du hast keine Theorie mehr nötig. Mit deiner großen Praxiserfahrung bist der absolute Experte jetzt.
man muß kein experte sein, um zu merken wo die theorie einen nicht weiterbringt und ich traue sogar den meisten programmierern zu einen guten und einen schlecht algo. zu erkennen, auch ohne jemals von o-notation gehört zu haben.
-
Egal, vergiss es. Ich geh jetzt wieder spielen...
Jester schrieb:
Und theoretische Informatiker haben ganz andere Spielzeuge...
frag doch mal elise.Und wahrscheinlich ist selbst das kein Spielzeug, sondern nur an mir vorbei gegangen.
-
Optimizer schrieb:
Egal, vergiss es. Ich geh jetzt wieder spielen...
was denn? nichtmal ein "ist doch nicht die o-notation schuld, wenn du zu blöd für nen baum bist"? auch gut.
-
Sowas liegt mir fern. Vielleicht willst du mich reizen, aber das wird dir nicht gelingen.
Ich werde ja nicht dafür bezahlt, dir etwas zu vermitteln.
-
Optimizer schrieb:
Vielleicht willst du mich reizen,
stimmt, ich bin ja der, der großzügig mit augenrollen und annahmen über erfahrung/kompetenz des gegenübers um sich wirft. ich seh schon die studis in datenbanken "was, der prof hat behauptet, daß die normalformen in der echten welt kaum eine sau braucht geschweige denn benutzt? der kann doch keine ahnung haben"
-
LOL, du bist so witzig.
btw. habe ich eben genau nichts direkt über deine Kompetenz ausgesagt, das ist nur das, was du erwartest hast mit deinem "ist doch nicht die o-notation schuld, wenn du zu blöd für nen baum bist".Der einzige, der es hier wirklich nötig hat, über andere (vorzugsweise Studenten, die alle überhaupt keine Praxiserfahrung haben) herzuziehen, bist ja scheinbar du. Und ob du es wahrhaben willst oder nicht, die O-Notation ist absolut ausschlaggebend für die Effizienz eines Algorithmus. Selbst der (sehr unrealistische) Faktor 1000 bei einem Algortihmus mit besserer Ordnung spielt schon bei recht kleinen n keine Rolle mehr, wie man leicht nachrechnen und auch nachprüfen kann.
Vergleich doch mal Bubblesort O(n*n) mit z.B. Quicksort(n * log n), dann siehst du es schon selbst. Kannst ja Quicksort ein Array mit 500 Elementen (was wenig ist) 3mal sortieren lassen und Bubblesort nur 1mal.
Auch dein Baum macht hier keine Ausnahme.Immer gescheit daherreden und überhaupt nichts begründen.
"was, der prof hat behauptet, daß die normalformen in der echten welt kaum eine sau braucht geschweige denn benutzt? der kann doch keine ahnung haben"
Ich hab sowieso überhaupt keine Ahnung, wie du zu deinen Ansichten kommst. Du musst dich ja echt für den Übergott halten und Studenten müssen alle saublöd sein.
-
Optimizer schrieb:
LOL, du bist so witzig.
btw. habe ich eben genau nichts direkt über deine Kompetenz ausgesagt, das ist nur das, was du erwartest hast mit deinem "ist doch nicht die o-notation schuld, wenn du zu blöd für nen baum bist".ah richtig.. kommentare wie
"Aber du wirst es schon wissen..."
oder
"Mit deiner großen Praxiserfahrung bist der absolute Experte jetzt."
waren reine einbildung und keinesfalls grundlage für die erwartung weiterer kommentare.Auch dein Baum macht hier keine Ausnahme.
*lol* alles klar, dann hab ich mir die zahlen also den ganzen nachmittag nur eingebildet und das penetrant am cache vorbeilesen hatte überhaupt nichts damit zu tun.
Immer gescheit daherreden und überhaupt nichts begründen.
welchen grund willst du noch? da oben ist ein wunderbares beispiel, ein n=4000 betrachte ich mal nicht als klein und trotzdem war der baum im besten fall grade mal gleich schnell. overhead und am cache vorbei und schon sagt mir die notation "hey, ignorier einfach, daß es nur halb so schnell läuft, in der theorie ist es grade um ein vielfaches schneller".
Du musst dich ja echt für den Übergott halten und Studenten müssen alle saublöd sein.
liegt vielleicht daran, daß ich mittlerweile lang genug selbst studiere und u.a. mal den unterschied gesehen habe, zwischen der gleichen vorlesung einmal bei einem prof, der nie was anderes als unis gesehen hat (und sich ein volles semester an eben jenen normalformen aufhängt) und einem, der vorher jahrzehnte wirklich in dem bereich gearbeitet hat und die dinger mit einem "sollte man mal gesehen haben und kann sie danach auch gleich wieder vergessen" im schnelldurchlauf abhandelt.
und wenn du erstmal genug leute siehst, die mit info. dipl. abhauen, außer grundlagen in java alles vermieden haben und zwar genau wissen, was ein "gutes" os ausmacht, aber trotzdem weder mit windows geschweige denn linux umgehen können, dann verstehst du vielleicht auch schnell, warum in manchen betrieben immer helle freude ausbricht, wenn es heißt "das ist ihr neuer vorgesetzter, dipl. inf. bla blub". allein das schon grund, warum ich mein diplom nicht an den großen nagel hängen werde. denn da draußen heißts nicht "oh wow, der hat studiert, der bestimmt voll ahnung" sondern "oh schande, ein studierter, wieder so ein klugscheißer". man kann vielleicht _während_ dem studium viel lernen, aber was man _im_ studium lernt kann man nach der prüfung zum großteil schnell wieder vergessen.
