Ist Big O wirklich wichtig?

Im akademischen Ernstfall wird Big O über alles andere unterrichtet. Im Vergleich zu Raumkomplexität, Normalfallanalyse, Einfachheit über Komplexität usw.

Was ist besonders für die Spieleprogrammierung und die Industrie am wichtigsten und warum?

Referenzen wären sehr hilfreich.

Wie bei jeder anderen Frage zu "Was ist der Eine Wahre Weg" sind dies alle Werkzeuge in Ihrer Toolbox und es gibt Fälle, in denen Big-O alles übertrumpft und Orte, an denen es keine Rolle spielt (tm).

Sie würden "nie" einen Physik-Solver schreiben, ohne sich Gedanken über Big-O zu machen. Sie würden keinen Sortieralgorithmus implementieren (nur für die kleinsten Datensätze), ohne sich darum zu kümmern. Wenn Sie ein vernetztes Spiel schreiben, werden Sie sich mit der Art und Weise befassen, wie die Leistung und der Netzwerkverkehr pro Benutzer skaliert werden.

Du bist vielleicht nicht so besorgt über Big-O, wenn ich mir keine Zeit vorstellen kann, aber ich bin mir sicher, dass es einige gibt. :) Zum Glück skalieren die meisten Dinge, die wir in Spielen tun, linear. Sie möchten eine Datei von der Disc lesen? Es dauert eine Zeitspanne, die linear proportional zur Dateigröße ist (abzüglich des konstanten Suchfaktors und möglicher Auswirkungen der Sektorgröße).

Was ist jedoch, wenn Sie eine bestimmte Entität in der Entitätsliste suchen möchten? Dies ist jedes Mal eine lineare Suche. Wenn Sie den Spieler einmal für jede Entität auf der Welt finden müssen, werden Sie mit diesem Ansatz für alle bis auf die trivialsten Spiele umgebracht, und selbst dann lohnt es sich wahrscheinlich, diese Suche so zu optimieren, dass sie eine konstante Zeit darstellt (z. B. Speichern außerhalb des Index) oder ein Zeiger auf den Player, um Ihnen mehr Zeit zu geben, andere Dinge zu tun, die für den Player tatsächlich sichtbar sind.

Ich denke, das bringt es auf den Punkt. Immer wenn der Prozessor etwas tut, das für den Player nicht direkt darstellbar ist, wird Zeit verschwendet. Das Maximieren der Zeitspanne, in der der Prozessor Daten berechnet, die dem Player angezeigt werden, maximiert das WOW! Du gibst dem Spieler.

Meine Faustregel ist, dass Ihre anderen Probleme relevanter sind, es sei denn, Sie sind O (beängstigend).

Meine andere Faustregel ist, dass Daten König sind. Wenn Sie Ihren Code nicht mit einem realistischen Datensatz profilieren, machen Sie nur Vermutungen.

Bearbeiten: Um ein wenig genauer zu werden, ist Ihr großes O nicht so wichtig, da (zumindest nach meiner Erfahrung) die meisten Ihrer Datensätze relativ klein sind. Sie interessieren sich wahrscheinlich nicht für Ihre obere Leistungsgrenze, wenn Sie mit einer Datenstruktur mit weniger als ein paar hundert Elementen arbeiten. Und wenn Ihre Listen mehr als 100.000 Elemente enthalten, müssen Sie wirklich alle Aspekte Ihrer Algorithmen berücksichtigen. Dies und meiner Erfahrung nach ist der Speicher eher ein begrenzender Faktor als die CPU-Geschwindigkeit. Je nach Anwendungsfall ist ein schnellerer Algorithmus zum Speichern von Daten möglicherweise nicht so gut wie ein magerer, jedoch langsamer.

Big O spielt die meiste Zeit eine Rolle, aber manchmal stellt sich heraus, dass ein scheinbar "schlechter" Algorithmus in der Praxis viel schneller ist.

Schauen Sie sich ein großartiges Beispiel von Tony Albrecht an: http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html

Sie finden dies überall in der Spieleentwicklung, wo die Anzahl der Elemente in der Operation entweder so groß ist, dass ein ganz anderer Algorithmus schneller ist, oder so klein, dass ein dümmerer Algorithmus ausreicht (oder so gut in den Cache passt, dass die Effizienz außer Kraft gesetzt wird) des besseren Algorithmus).

Das Problem bei Big O ist, dass es sich um eine allgemeine Bezeichnung für die Komplexität der Aufgabe handelt, die die Komplexität moderner Zielhardware nicht berücksichtigt und keinen Einblick in den Einrichtungsaufwand bietet.

In vielen Fällen ist die beste optimale Lösung zwei Schritte. In der Praxis tendieren Spieleentwickler tendenziell zu Algorithmen mit niedrigem O-Wert, stehen jedoch den Kosten für die zeitliche Entwicklung oder das Debuggen gegenüber. Sobald Sie eine vernünftige Lösung gefunden haben, müssen Sie immer darauf achten, wie die Hardware die Aufgabe abwickelt und wie Sie mehr Hardware in kürzerer Zeit erledigen können.

Wenn ich in-Motor bin Codierung, bin ich oft nur mit einem festen besorgt n: Ich habe bereits eine räumliche Teilung die Anzahl der Objekte zu begrenzen empfängt update(), physics()und render()auf etwa diejenigen auf dem Bildschirm und die umliegenden Gebiete. Die maximale Stapelgröße ist normalerweise pro Spiel ziemlich genau definiert, obwohl sie immer etwas größer ist, als Sie es geplant haben.

In diesem Fall beschäftige ich mich weniger mit Big-O als mit dem konstanten Faktor-Multiplikator und Termen niedrigerer Ordnung. Für eine Funktion mit Laufzeit wie a*n^2 + b*n + c(was ist O(n^2)), bin ich oft viel mehr mit dem Reduzieren aund möglicherweise Eliminieren beschäftigt c. Einrichtungs- oder Abbaukosten ckönnen proportional groß zu einem kleinen werden n.

Dies bedeutet jedoch nicht, dass Big-O (oder insbesondere Big-Theta ) ein guter Code-Geruchsindikator ist. Sehen Sie sich O(n^4)irgendwo oder noch schlimmer eine O(k^n)geometrische Zeit an und stellen Sie sicher, dass Sie andere Optionen in Betracht ziehen.

Ich mache mir im Allgemeinen viel mehr Sorgen um die Big-O-Optimalität und springe durch die Rahmen, um Algorithmen mit niedrigerem Big-O zu finden, wenn ich mit Datenerstellungswerkzeugen arbeite. Während die Anzahl der Objekte in einem bestimmten Level / Streaming-Bereich im Allgemeinen genau definiert ist, kann es sein, dass die Gesamtanzahl der Objekte / Kunstobjekte / Konfigurationsdateien / usw. in einem gesamten Spiel nicht genau definiert ist. Es ist auch eine viel größere Zahl. Selbst wenn wir ein paralleles Daten-Make ausführen, warten wir immer noch in der Größenordnung einer Minute (ich weiß, Winseln - Daten-Make für Konsolen kann Stunden dauern - wir sind meist kleine Handheld-Spiele), um einen jam data-clean && jam dataZyklus zu durchlaufen .

Um ein konkretes Beispiel zu nennen: Ein Streaming-Algorithmus für Kacheln im Hintergrund, der 8x8 Kacheln mit 256 Farben streamt, ist völlig außer Kontrolle geraten. Es ist nützlich, Streaming-Puffer zwischen Hintergrund- "Ebenen" zu teilen, und wir können bis zu 6 von ihnen in einer bestimmten Ebene haben, die denselben Puffer teilen. Das Problem ist, dass die Schätzung der Größe des benötigten Puffers auf den möglichen Positionen aller 6 Ebenen basiert - und wenn es sich um eine Breite / Höhe / Bildlaufrate von Primzahlen handelt, beginnen Sie schnell mit einer umfassenden Suche - welche beginnt sich zu nähernO(6^numTiles)- die in vielen Fällen in der Kategorie "länger als das Universum sein wird" ist. Glücklicherweise sind die meisten Fälle nur 2-3 Schichten, aber selbst dann haben wir eine Laufzeit von über einer halben Stunde. Momentan untersuchen wir eine sehr kleine Teilmenge dieser Möglichkeiten und erhöhen die Granularität, bis eine festgelegte Zeitspanne verstrichen ist (oder wir haben die Aufgabe abgeschlossen, die für kleine Doppelschichtkonfigurationen auftreten kann). Wir erhöhen diese Schätzung ein wenig, basierend auf früheren Statistiken darüber, wie oft wir uns als falsch erwiesen haben, und fügen dann ein wenig zusätzliche Polsterung hinzu, um eine gute Maßnahme zu treffen.

Ein weiteres lustiges Beispiel: Vor einiger Zeit experimentierte der leitende Ingenieur bei einem PC-Spiel eine Weile mit Sprunglisten . Der Speicheraufwand führt letztendlich zu mehr Cache-Effekten, wodurch die gesamte Angelegenheit um einen nicht konstanten Multiplikator erweitert wird. Für kleine Unternehmen sind sie also keine gute Wahl n. Für größere sortierte Listen, in denen häufig gesucht wird, bieten sie jedoch Vorteile.

(Ich stelle oft fest, dass der naive Algorithmus einen höheren Big-O-Wert aufweist, bei kleineren Datenmengen schneller und einfacher zu verstehen ist. Die interessanteren / komplexeren Algorithmen (z. B. Patricia Trie) sind für die Benutzer schwieriger zu verstehen und zu verwalten, bei größeren jedoch eine höhere Leistung Datensätze.)

Es kann praktisch sein, aber es kann auch irrelevant sein. Nehmen wir zum Beispiel mein letztes Spiel, das so etwas wie ein Smash-TV-Klon ist. Top-down-Spiel, Monster strömen von den Seiten herein, du schießt auf sie.

Jetzt gibt es viele clevere Möglichkeiten, Kollisionen zu bestimmen. Sie können KDtrees verwenden, um den Raum aufzuteilen, damit Sie keine Kugeln gegen Monster testen, die sie möglicherweise nicht treffen könnten. Und natürlich hätte ich klug sein können und das hätte ich auch tun können.

Aber ich fühlte mich faul und verglich einfach jede Kugel mit jedem Monster. Selbst in den hektischsten Situationen beanspruchte der Kollisionscode mit 60 fps weit weniger als 10% der Spiel-CPU. Big-O: unwichtig.

Ebenso hatte ich ein Spiel im 4x-Stil, in dem du Städte auf Inseln gebaut hast, und manchmal wurden die Städte zerstört. Ich hätte klug sein und versuchen können, das Einkommen der zerstörten Stadt von den Einkommensvariablen abzuziehen. Aber ich habe es nicht getan. Ich habe das Einkommen einfach ausgelöscht und es jedes Mal neu berechnet, wenn sich etwas änderte. Völlig irrelevant in Bezug auf die CPU.

Big-O ist in Spielen genauso wichtig wie in allem anderen: Das heißt, absolut unwichtig, bis es kritisch wird.

Schreib etwas Code. Wenn es zu langsam ist, dann profiliere es.

Die Big-O-Analyse ist wichtig, aber es ist nicht das erste, woran man bei der Spieleentwicklung denken muss. Da das Erstellen von Spielen viel komplizierten Code beinhaltete, empfehle ich immer Code Simplicity als erstes Kriterium für einen Algorithmus. Algorithmen mit komplizierter Buchhaltung verschwenden nur Ihre Zeit.

Ich finde es sehr wichtig, dass dein Spiel während der Entwicklung immer mit 60 fps läuft. Wenn Sie darunter tauchen, führen Sie als Erstes einen Profiler aus. Sobald Sie den Engpass gefunden haben, greifen Sie ihn an. Die meiste Zeit müssen Sie nicht-codierende Dinge tun, z. B. sagen Sie Level-Designern, dass sie weniger Dinge in einem Bereich ablegen sollen (und geben Sie ihnen Werkzeuge dafür).

Manchmal identifizieren Sie tatsächlich Code, der beschleunigt werden muss. Ich finde das macht Spaß Engineering! Ich wünschte, ich hätte mehr Möglichkeiten dazu. Und natürlich möchten Sie das Ändern einer Sache nach der anderen wiederholen und die Leistung messen. Die typischen Probleme, die ich finde, sind:

1. Stellen Sie sicher, dass Sie nicht jeden Frame neu aufrufen oder malloc (dies ist immer das Problem Nr. 1)
2. Reduzieren Sie die Arbeit: weniger Raycasts, weniger Leute usw.
3. Probleme mit dem Big-O-Algorithmus
4. Cache-Kohärenz: Ordnen Sie die Daten in Arrays ein und nicht in verstreutem Speicher
5. Verwenden Sie STL nicht im Debug-Modus. (und Sie möchten immer, dass der Debug-Modus funktioniert)

Big-O-Notation ist per Definition asymptotische Komplexität - dh sie zeigt, wie die Zeit skaliert, wenn N (oder welche Variablen auch immer Sie haben) "sehr" groß wird. Um Tetrads Kommentar (den ich überarbeitet habe) noch einmal zu wiederholen: "data is king". Wenn N in Ihrer spezifischen Situation "sehr groß" ist, spielt es eine Rolle, wenn N "sehr klein" ist, spielt es keine Rolle. Erfahrung und Praxis vermitteln Ihnen ein Gespür für die Quantifizierung von "sehr groß" und "sehr klein".

Profilieren Sie immer zuerst und optimieren Sie zuletzt (es sei denn, Sie führen eine Machbarkeitsstudie für Features durch).

Die Bedeutung von Big-O in Ihrer Software ist O (N ² ). Wenn N wächst, wächst die Wichtigkeit, den richtigen Algorithmus zu haben, noch mehr. :)

Big-O ist nur eine Richtlinie - etwas, das Ihnen sagt, welche grobe Leistung Sie von einem Algorithmus erwarten können - und wie Sie erwarten sollten, dass die Leistung skaliert, wenn Sie den Datensatz vergrößern . In Bezug auf Big-O müssen Sie zwei Hauptpunkte beachten:

1) Wenn Sie zwei Algorithmen haben, die meistens dasselbe tun, aber einen besseren O-Wert haben, sollten Sie sich (offensichtlich) für diesen Algorithmus entscheiden.

2) Big O befasst sich mit der asymptotischen Analyse . Big-O kommt nur dann wirklich ins Spiel, wenn n groß ist . Zum Beispiel kann ein O (n) -Algorithmus hinsichtlich der Leistung einem O (n ^ 2) -Algorithmus für kleine n sehr ähnlich sein . Wenn Sie über einen Algorithmus sprechen, der n ^ 2 Operationen pro Vertex erfordert, aber n = 2 oder n = 3, dann gibt es keinen großen Unterschied zwischen einem O (n ^ 2) -Algorithmus (4 und 9 Operationen bzw.) und ein O (n) ein (2 bzw. 3 ops). Wenn jedoch n = 9 ist, dann sprechen Sie plötzlich von 81 Operationen für den O (n ^ 2) -Algorithmus und nur von 9 für den O (n) -Einsen - ein größerer Unterschied - und wenn n = 100, dann sind Sie es es geht um 100 ops gegen 10000 - ein viel größerer Unterschied.

Sie müssen Big-O also immer in diesem Licht betrachten: Es ist dazu gedacht, Algorithmen zu vergleichen, die auf der Grundlage der Leistung im ungünstigsten Fall dasselbe tun, wenn n groß wird . Die Unterschiede zwischen den Algorithmen können so gut wie vernachlässigbar sein, wenn n sehr klein ist.

Ich habe keine Referenzen, aber Big O ist zumindest nützlich, um sich bei der Analyse eines Problems und der Diskussion dessen bewusst zu sein. Auf der anderen Seite ist es natürlich ein strittiger Vergleich, wenn die O (log n) -Version eine viel größere Rolle spielt als die O (n) -Version. Und wie bei allem gibt es immer einen Kompromiss. Raumkomplexität könnte ein Problem sein, obwohl dies auch allgemein in O ausgedrückt werden könnte. Normalfallanalyse ... weniger, da auch Ausreißer nicht ansteigen sollen. Einfachheit über Komplexität ist meiner Meinung nach in der Spieleentwicklung relativ nutzlos, da Geschwindigkeit fast immer ein Problem ist. Wenn die Einfachheit nicht zu einer Beschleunigung führt (aber dann bedeutet das, dass Ihr komplexer Fall aus den falschen Gründen falsch war), muss die Einfachheit verschwinden aus dem Fenster zu Gunsten der Geschwindigkeit. Aber Big O ist definitiv nützlich,

Wenn Sie eine Spielfunktion oder einen Aspekt eines Spiels als Prototyp erstellen, sollten Sie sich nicht darum kümmern, sie überhaupt zu optimieren .

Während des Prototyping und des Erlernens der Besonderheiten dieser Funktionalität werden die notwendigen Optimierungen offensichtlich und fließen die meiste Zeit in das endgültige Design wie 2nd nature ein.

Schwitzen Sie nicht.

Es sollte nicht das A und O sein. Es hilft jedoch dabei, offensichtliche Probleme zu lösen, die Leistungseinbußen verursachen können. Warum etwas in O (n ^ 2) Zeit verwenden, wenn Sie dasselbe in O (log n) Zeit tun können?

Ich denke, es gilt für Spiele mehr als für die meisten anderen Branchen, da der Markt derjenige ist, der Geschwindigkeitsprobleme am meisten bemerkt. Jemand, der ein Textverarbeitungsprogramm verwendet, ist es egal, ob es eine Verzögerung von einer halben Sekunde für die Ausführung von Aktion X gibt, aber die Spieler werden wahrscheinlich sagen, dass Spiel Y so langsam ist, dass es ewig dauert, bis Aktion Z ausgeführt wird.

In der Spielentwicklung (und den meisten anderen) jammern wir über eine zusätzliche Operation, die pro Schleife ausgeführt wird:

for (int i = 0; i < array.length; i ++) { /* ... */ }

gegen

for (int i = 0, l = array.length; i < l; i ++) { /* ... */ }

Die meisten modernen Spiele haben Physik, und Sie werden das Problem der n-Körpersimulation finden. In einem naiven Algorithmus ist es O (n ^ 2), aber es gibt eine Optimierung, die es zu O (n log n) macht (aber etwas Genauigkeit einbüßt).

Man könnte sagen, Sie programmieren keine Schwerkraft- und Partikelinteraktionen, aber was ist mit dem Teamverhalten einer Armee (von Zombies), in der sie sich abhängig von anderen Orten bewegt (genauer gesagt: Schwärmen)?

In einem herkömmlichen Kollisionserkennungsalgorithmus ist die Zeitkomplexität wie der n-Körper O (n ^ 2). Es gibt jedoch einen besseren Weg: Teilen Sie die Welt in viele kleine Teile auf, damit nur Objekte innerhalb desselben Teils kollisionserfasst werden. Siehe http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php .

Wenn Ihr Spiel skriptfähig ist, lassen Sie den Scripter NICHT O (n ^ 2) (und höher) Algorithmen zum Zerquetschen von Zahlen in das Skript schreiben, z. B. das Durchsuchen der Tasche des Benutzers. Erstellen Sie stattdessen eine integrierte Funktion im Code.

In der realen Welt zählt nur die rohe Leistung. Das Big-O eines Algorithmus kann als erster Hinweis auf die Verwendung dienen. Abhängig von der Hardware kann die Implementierung jedoch äußerst ineffizient sein. Beispielsweise kann eine lineare Suche oft schneller als eine binäre Suche sein, da Sie einen linearen Speicherzugriff und keine Verzweigungen erhalten.

Aufgrund der aktuellen Ausrichtung in Multithread-Plattformen und -Architekturen verliert Big-O viel an Bedeutung, da es nur die vertikale Skalierbarkeit von Speicher- oder Datenberührungen pro Operation berücksichtigt, anstatt auch zu berücksichtigen, wie der Algorithmus arbeitet skaliert mit einer größeren Anzahl von Threads.