STL ungeeignet für Spieleprogrammierung?
-
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.
-
Trienco schrieb:
ich denke jeder merkt einem algo. auch so an, ob er effizient ist oder nicht
ich kann das nicht
dazu müsste ich den algo ja erst analysieren... und selbst dann kann ich nicht viel sagen - denn wie will ich cache misses oder ähnliches vernünftig feststellen (ohne zu testen - ich kann ja nicht gut 1mio algos testen (irgendwann sollte ich ja auch das programm weiter entwickeln) um einen guten zu finden).
-
Ja, es gibt Fälle wo die Konstanten so groß sind, daß sie wirklich ins Gewicht fallen. Aber die sind sehr sehr selten. Die O-Notation ist zumeist ein sehr guter Anhaltspunkt für die Effizienz eines Algorithmus. Du darfst natürlich nicht hergehen und irgendeinen schlampig implementierten Baum mit nem ordentlich gebauten Array vergleichen. Natürlich darfst Du nachher noch die Konstanten drucken (sollte man auch), aber in aller Regel hat der mit der besseren Komplexität die Nase vorn. Wenn er das nicht hat, dann würde ich erstmal nach nem groben Schnitzer in der Implementierung suchen... und dann, wenn ich dann nix finde könnte man überlegen, ob es vielleicht wirklich an den Konstanten liegt.
Ein viel wichtigerer Punkt ist in meinen Augen die Implementierungszeit. Wenn ein Algo mit O(n) so kompliziert ist, daß ich inklusive Debugging etc. 1 Woche am implementieren bin, O(n*logn), oder auch O(n²) aber einfach runtertippen kann, dann ist das ne echte Überlegung.
So und zum Abschluß noch ein Beispiel wo die Konstanten zählen: Unifikation (vergleich von Termen in der Logik), geht mit dem Algorithmus von Robinson in exponentieller Zeit. Man hat inzwischen wohl einen polynomialen Algo gefunden. Der ist allerdings schweinekompliziert und die Konstanten sind so riesig, daß (fast) immer der normale Algo mit exponentieller Laufzeit genommen wird.
MfG Jester
-
Jester schrieb:
Natürlich darfst Du nachher noch die Konstanten drucken (sollte man auch),
wenn es denn geht. manchmal läßt sich sowas nicht oder nur mit viel aufwand machen. z.b. den baum beim nächsten anlauf als array zu speichern, zeiger-jadgen durch bit-shifts ersetzen etc. macht das ding zwar deutlich schneller, aber funktioniert zum einen nur in sonderfällen und zum anderen ist der code alles andere als schön.
die frage ist dann wohl nur: reicht es einem, wenn etwas "meistens" gut funktioniert? ein virenscanner wird auch in der regel verhindern, daß etwas passiert, aber deswegen surft keiner ungehemmt mit ie auf pornoseiten oder öffnet wild sämtliche mails in outlook. wenn ich vorher schon nicht weiß, ob ich einen regelfall oder sonderfall habe, wieso riskieren auf die nase zu fallen?
letztlich zählt man mit dem ding nur die arbeitsschritte, die nötig werden, aber für mich ist die größe dieser schritte zu wichtig, um sie erstmal zu ignorieren. dann noch der cache dazu, der einen riesigen unterschied machen kann und ich hab solche dinge lieber von anfang an im hinterkopf. und mal ehrlich, wann hat hier einer das letzte mal erst die komplexität in o-notation hinschreiben müssen, um zu merken "hm, na so prall klingt der ansatz aber nicht"?
-
dann noch der cache dazu, der einen riesigen unterschied machen kann und ich hab solche dinge lieber von anfang an im hinterkopf.
Premature Optimization...
Meine Güte, gleich von Anfang an einen schlechteren Algorithmus zu nehmen, weil der vielleicht weniger cache misses dann verursacht ist doch genauso schlecht. cache-probleme bekämpft man am besten, indem man seine Datenstruktur anders aufbaut und/oder einen Heap verwendet, der nicht fragmentiert.Auf jeden Fall ist es keine gute Idee, gleich von Anfang an deswegen einen prinzipiell ungünstigeren Algorithmus zu nehmen.
-
Trienco schrieb:
letztlich zählt man mit dem ding nur die arbeitsschritte, die nötig werden, aber für mich ist die größe dieser schritte zu wichtig, um sie erstmal zu ignorieren. dann noch der cache dazu, der einen riesigen unterschied machen kann und ich hab solche dinge lieber von anfang an im hinterkopf.
*schlauenSpruchMach*
Premature optimization is the root of all evilBye, TGGC (Für echte Fans)
-
Da bist du jetzt aber reichlich spät dran mit diesem Spruch. :p
-
TGGC schrieb:
*schlauenSpruchMach*
Premature optimization is the root of all evilROTFL...
/me würde auch gern 'nen schlauen Spruch machen... fällt aber keiner ein...
*frischenkaffeehol*
Zum Thema:
Irgendwie glaub' ich redet ihr aneinander vorbei...
Aber egal.
Naja, selbst wenn man nicht schon low-level auf Cache-Misses und -Hits achtet, ist ein vermeintlich schneller Algo nicht unbedingt besser.- Implementierungszeit und Wartbarkeit wurde schon gesagt (angedeutet)
Die komplexen _schnellen_ Algos sind meistens sauschwer zu implementieren (ein pissels QuickSort ist das erst der Anfang) - Viel Overhead. Durch Erstellen von irgendwelchen Priority-Queues und/oder dem Aufhacken von Problemen (Divide- bzw. Decrease-&-Conquer) geht viel Zeit bei drauf, die bei kleinen n keine Vorteile mehr bringen (ganz im Gegenteil).
So könnte man einen "schnellen" Merge- oder QuickSort z.B. nur solange laufen lassen, bis jeweils noch k Elemente da sind, und diese dann mit dem (für so kleine n besseren) InsertionSort oder whatever sortieren lassen. - Falls die "Schnelligkeit" nicht direkt mit der thteoretischen Ausführungszeit gleichzusetzen ist.
Man nehme z.B. einen fetten Prozzi der gigantische Mengen sortieren muß, der Bottleneck ist allerdings die I/O, die ein riesiges Bandlaufwerk ist oder eine sau-lahme Platte aus der Vorkriegszeit (aus irgendeinem Grund).
Hier würde sich u.U. der laaahme SelectionSort deutlich besser rentieren als z.B. QuickSort, da der erstere jedes Element maximal genau einmal (!) umherschiebt.
Just my half cent
- Implementierungszeit und Wartbarkeit wurde schon gesagt (angedeutet)
-
Ack!
Nur eine Kleinigkeit zu der Sache mit den Plattenzugriffen... dort ist es so, daß die Plattenzugriffe viel viel Zeit stehlen. Also bestimme ich die Plattenzugriffe in O-Notation.
-
Optimizer schrieb:
Auf jeden Fall ist es keine gute Idee, gleich von Anfang an deswegen einen prinzipiell ungünstigeren Algorithmus zu nehmen.
es ist aber genauso keine gute idee, sich viel streß und arbeit zu machen, um einen vermeintlich schnelleren alg. zu implementieren, der dann am ende doch nichts bringt.
ich schreibe bestimmt nicht erst den baum und hinterher die brute force methode, ergo wäre "premature optimization" wohl eher, einen alg. zu implementieren, nur weil er in o besonders gut aussieht, obwohl er im zweifelfall komplizierter und damit fehleranfälliger ist.
-
Das kannst du aber vorher nicht wissen. Ich habe dir gesagt, dass man cache-probleme lieber anders bekämpft, als mit einem anderen Algorithmus (der wohl auch nicht immer dafür verantwortlich gemacht werden kann).
Jetzt geht es auf einmal um "komplizierter und fehleranfälliger". Irgendwie willst du es nicht so recht einsehen...
Natürlich ist das eine Frage des Aufwands. Ich bin mal davon ausgegangen, dass wir von Hotspots unserer Programme reden und nicht von einmaligen unkritischen Initialisierungen...
-
muss mich auch mal einklinken
Was hat der Cache mit einer effizienz des algorithmus zu tun? oder mit der implementierung? waren algorithmen nicht sprachen/computerunabhängig? Und selbst wenn der Algorithmus jetzt an der limitierung des Caches scheitert, heisst das nicht, dass er bei anderen systemen, deren cache größere dimensionen hat, nicht abgeht wie schmitz Katze ;). Genau das gleiche seh ich auch in der implementierung. Eine langsame implementierung ist systemabhängig, es kommt wie immer darauf an, worauf das system optimiert wurde. Deshalb halte ich von der Diskussion relativ wenig, da das ganze stark situationsabhängig ist. Wenn das system eine extrem effektive bitblast funktion hat, dann kann unter umständen ein algorithmus, der viel kopiert effektiver sein, als ein algorithmus, der wenig kopiert. Dass etwas jetzt nicht gut funktioniert, heisst nicht, dass es niemals gut funktioniert.
-
otze schrieb:
muss mich auch mal einklinken
Was hat der Cache mit einer effizienz des algorithmus zu tun? oder mit der implementierung? waren algorithmen nicht sprachen/computerunabhängig? Und selbst wenn der Algorithmus jetzt an der limitierung des Caches scheitert, heisst das nicht, dass er bei anderen systemen, deren cache größere dimensionen hat, nicht abgeht wie schmitz Katze ;). Genau das gleiche seh ich auch in der implementierung. Eine langsame implementierung ist systemabhängig, es kommt wie immer darauf an, worauf das system optimiert wurde. Deshalb halte ich von der Diskussion relativ wenig, da das ganze stark situationsabhängig ist. Wenn das system eine extrem effektive bitblast funktion hat, dann kann unter umständen ein algorithmus, der viel kopiert effektiver sein, als ein algorithmus, der wenig kopiert. Dass etwas jetzt nicht gut funktioniert, heisst nicht, dass es niemals gut funktioniert.Der Meister hat gesprochen.
