STL ungeeignet für Spieleprogrammierung?

Jester

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

Trienco

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.

TGGC

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 evil

Bye, TGGC (Für echte Fans)

Da bist du jetzt aber reichlich spät dran mit diesem Spruch. :p

Sgt. Nukem

TGGC schrieb:

*schlauenSpruchMach*
Premature optimization is the root of all evil

ROTFL...

/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

Jester

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.

Trienco

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

otze

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.

Ahvolon*F-Bytes*

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.

TGGC

Wenn man die STL nimmt, erübrigt sich Fehlerfreiheit und komplizierte Implementierung sowieso. Und darum ging es hier.

Bye, TGGC Deine Unterstützung wird gebraucht!

Trienco

Optimizer schrieb:

Jetzt geht es auf einmal um "komplizierter und fehleranfälliger".

irgendjemand hat das thema ja auch auf premature optimization gelenkt und DA spielt fehleranfälligkeit und komplizierte implementierung wohl durchaus eine rolle, oder? in der phase ist ein theoretisch super-effizenter aber komplizierter alg. ja sogar noch uninteressanter und wenn es wirklich ans optimieren geht, dann zählt die in der realen welt schnellste methode mehr als die schnellste methode auf dem papier. und wenn dabei rauskommt, daß log n unmöglich so implementiert werden kann, daß es schneller ist als n, dann.. pfeif ich gediegen auf die theorie und benutze das, was auch funktioniert.

wir hatten mittlerweile ein paar beispiele, damit bewiesen, daß die notation oft, aber nicht immer weiterhilft. eine methode, von der ich erst hinterher wissen kann, ob sie für meinen speziellen fall anwendbar ist oder nicht betrachte ich als sehr eingeschränkt nützlich.

ergo ist mein gedankengang "hmm, drei verschachtelte schleifen sind nicht gut, aber der kern läßt sich gut optimieren und mehr als x objekte werdens wohl nicht.. oder nur eine schleife, aber dafür viel rumkopieren, schreibende zugriffe und ein ineffizenter kern".. und eben nicht "ok o(n^3), o(n), ich nehm den zweiten".

rgendjemand hat das thema ja auch auf premature optimization gelenkt

Richtig, nämlich du. Lies nochmal ein bisschen zurück, dann wirst du feststellen, dass du angefangen hast nach dem Motto "wenn man das [caching] im vornherein schon berücksichtigt..."

dann zählt die in der realen welt schnellste methode mehr als die schnellste methode auf dem papier.

seufz.

eine methode, von der ich erst hinterher wissen kann, ob sie für meinen speziellen fall anwendbar ist oder nicht betrachte ich als sehr eingeschränkt nützlich.

Krass, du tust ja jetzt gerade so, als wäre das ein Ausnahmefall, wo ein Algorithmus, der effizienter ist, sich implementieren lässt. Das ist fast immer der Fall, man.

Naja ich klink mich jetzt dann mal aus. Wie du das interpretierst, ist mir relativ egal, jetzt haben dir wirklich genug Leute gesagt, dass der Algorithmus mit der besseren Ordnung fast immer vorzuzuiehen ist (wohlgemerkt, wir reden von Hotspots im Programm). Und wenn man vielleicht auch noch den einen oder anderen Algo in der STL findet, sowieso.