STL ungeeignet für Spieleprogrammierung?
-
@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.
-
Trienco schrieb:
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.Dem gingen Aussagen über unglaublich praxisfremde Studenten und Spielzeugen von theoretischen Informatikern voraus.
*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.
Richtig, das hat nichts damit zu tun, ob ein Algorithmus besser oder schlechter ist. Bei einem Baum hast du sowieso grundsätzlich das caching-problem, genauso wie bei einer Linked-List. Ob du jetzt z.B. Tiefen- oder Breitensuche verwendest, tut da vom caching her gar nichts zur Sache. Selbst wenn du es in deinem Fall mit einem anderen Suchalgorithmus verbessern konntest, ist das keine Bestätigung, weil das auch mal ganz anders aussehen kann, wenn du den Baum oder die Äste in einer anderen Reihenfolge anlegst.
Falls du mir aber nur sagen willst, dass ein Baum jetzt generell für deinen Zweck aufgrund des cachings ungünstig ist, so hat dies ebenfalls nichts mit irgendwelchen Ordnungen von Algorithmen zu tun, oder das ein O(n^2) besser sein kann als O(n * log n).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".
Es gibt keine absoluten Wahrheiten, aber um die Effizienz eines Algorithmus zu bewerten, bist mit nichts besser dran als mit der O-Notation.
Es ging um nichts anderes, als darum, wie man einen Algorithmus bewertet. Willst du jetzt sagen "Hey, der Algo ist schlechter als der andere, weil ich nur 512kb L2-Cache habe" ?liegt vielleicht daran, daß ich mittlerweile lang genug selbst studiere
Vielleicht liegts ja daran, aber das gibt dir trotzdem nicht das Recht dazu, dich selber zum Experten zu erheben und anerkanntes Wissen in Frage zu stellen.
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".
Das ist jetzt nicht in den Zusammenhang passendes Geblubber. Es gibt solche und solche Dipl. Informatiker und bzgl. unserer Meinungsverschiedenheit sagt das jetzt nichts aus, außer dass du mich evtl. auch für "so einen" hältst. Das bringt uns beide nicht voran und hat auch nichts mit dem Thema zu tun.
Schon während der ganzen Diskussion krieg ich jetzt Aussagen in diese Richtung zu hören, falls du mir damit irgendwas mitteilen willst, dann sag es doch bitte direkt.
-
Optimizer schrieb:
Falls du mir aber nur sagen willst, dass ein Baum jetzt generell für deinen Zweck aufgrund des cachings ungünstig ist, so hat dies ebenfalls nichts mit irgendwelchen Ordnungen von Algorithmen zu tun, oder das ein O(n^2) besser sein kann als O(n * log n).
aber damit, daß durch cache misses und andere kleinigkeiten der mal als uninteressant weggeworfene faktor eben DOCH eine wichtige rolle spielt. was nutzt mir ein in der theorie unglaublich genialer algo., wenn er sich einfach nicht effizient implementieren läßt?
mein problem mit dem ding ist, daß es leute gibt, die sich einfach "blind" darauf verlaufen, daß ein algo. mit geringerer komplexität automatisch schneller ist, in der praxis aber z.b. die "naive" implementierung eines baums lahm genug ist, um jeden theoretischen vorteil zu zerlegen.
klar, WENN ich den baum für das spezielle problem für den cache hinprügeln kann, dann ist der toll und schnell, aber am ende habe ich zwei algos. von denen einer lahmer ist als brute force und einer schneller, laut o-notation schenken die sich aber nichts. sorry, ich denke jeder merkt einem algo. auch so an, ob er effizient ist oder nicht und das degradiert die notation nur noch zu einer bequemen möglichkeit es knapp zu formulieren, statt 2min über die verschachtelten schleifen zu reden. der "kern" wird aber buchstäblich unter den tisch gekehrt.
Es gibt keine absoluten Wahrheiten, aber um die Effizienz eines Algorithmus zu bewerten, bist mit nichts besser dran als mit der O-Notation.
Es ging um nichts anderes, als darum, wie man einen Algorithmus bewertet. Willst du jetzt sagen "Hey, der Algo ist schlechter als der andere, weil ich nur 512kb L2-Cache habe" ?
nein, aber der o-notation fehlen dafür möglichkeiten zu sagen "der ist schlechter, weil er sich trotz aller theorie nicht effizient implementieren läßt". anderes simples beispiel vom raytracen: in der theorie ist es schneller, wenn schon besuchte knoten markiert werden, um sie nicht zweimal zu prüfen. in der praxis reicht dieses krümelige if schon aus, um es insgesamt langsamer zu machen als die knoten sinnlos immer wieder zu prüfen.
Es gibt solche und solche Dipl. Informatiker und bzgl. unserer Meinungsverschiedenheit sagt das jetzt nichts aus
natürlich gibts die, aber ich wage dreist zu behaupten, daß die "guten" diejenigen sind, die sich auch privat damit beschäftigen und das meiste vielleicht während, aber außerhalb des studiums lernen. aber ich geb gern zu, daß der punkt "nur weil einer studiert hat, muß er noch lange keine ahnung haben" oft extremer rüberkommt. speziell am semesterbeginn, wenn mal wieder sowieso nur 4-5 interessante vorlesungen stattfinden und sich alle so überschneiden, daß man höchstens 2 ernsthaft hören kann.
