In welchen Bereichen der Programmierung ist die Laufzeit von Algorithmen tatsächlich ein wichtiges Thema?

Manchmal höre ich Leute sagen, dass aufgrund der Geschwindigkeit der Prozessoren und der verfügbaren Speicherkapazität die Effizienz des Algorithmus und die Laufzeit in der Praxis keine große Rolle spielen.

Ich stelle mir jedoch vor, dass es noch Bereiche gibt, in denen solche Überlegungen von größter Bedeutung sind. Zwei, die mir in den Sinn kommen, sind der algorithmische Handel, bei dem Tausende von Transaktionen in Bruchteilen von Sekunden ausgeführt werden müssen, und die Programmierung eingebetteter Systeme, bei denen Speicher und Leistung häufig knapp sind. Habe ich recht mit diesen Beispielen? und welche anderen bereiche wären auch beispiele?

Geschwindigkeit ist immer gefragt. Ich denke du hast recht. Hier einige Beispiele, bei denen saubere Algorithmen gefragt sind:

1. Kryptographie

2. Suche in großen Datenbanken

3. Sortieren und Zusammenführen

4. Textsuche (nicht indiziert), einschließlich Platzhalter

5. Mathematische Probleme mit intensiven Berechnungen

6. Simulation

7. Data Mining-Anwendungen

8. Animation

9. AI

10. Computer Vision

Es gibt einige Fälle, in denen die Laufzeit von Algorithmen möglicherweise keine große Rolle spielt, da wir den Punkt erreicht haben, an dem Sie einfach einen Algorithmus mit längerer Laufzeit und leistungsfähigerer Hardware durchspielen können. Aber es gibt definitiv einige Orte, an denen eine Beschleunigung unabdingbar ist.

Im Allgemeinen ist alles, was große Datenmengen verwendet, ein Problem. Wenn Sie etwas haben, das schlecht mit n skaliert, und dann eine wirklich große Zahl machen, haben Sie ein Problem. Ich vermute, wenn Sie zur Betaseite von Computational Science gehen und ein bisschen herumstöbern, könnten Sie viele Probleme finden, die bessere, schnellere Algorithmen erfordern. Einige Bereiche, in die ich gestoßen bin:

• Besonders komplexe statistische Auswertung. Eine Kombination ineffizienter Algorithmen und großer Datenmengen kann zu massiven Verlangsamungen führen. Für einige Studien ist das vielleicht nicht wichtig, aber was ist, wenn Sie versuchen, etwas mit schneller Umkehr zu tun? "Es kommt in einem Monat vom Server" ist wahrscheinlich eine schlechte Sache, wenn Sie ein Überwachungssystem für chemische / nukleare / biologische Bedrohungen betreiben.
• Data Mining für große Datenmengen.
• Simulationen mit vielen Variablen.

Im Allgemeinen scheint wissenschaftliches Rechnen ein Bereich zu sein, in dem die Komplexität des Programmierten die Möglichkeit zu ernsthaften Verlangsamungen bietet, wenn Ihr Algorithmus träge ist (viele von ihnen leiden unter sehr großen n). Und wie Sie bereits sagten, gibt es finanzielle Anwendungen. Wenn Millisekunden bestimmen können, ob Sie mit einem Trade Geld verdienen oder verlieren, werden Algorithmen, die "gut genug" sind, dies nicht verhindern, wenn es etwas Besseres gibt, das getan werden kann.

Manchmal höre ich Leute sagen, dass aufgrund der Geschwindigkeit der Prozessoren und der verfügbaren Speicherkapazität die Effizienz des Algorithmus und die Laufzeit in der Praxis keine große Rolle spielen.

Nimm es mit einem Körnchen Salz. Mehr Rechenleistung bedeutet im Grunde nur, dass Ihr n viel größer werden kann, bevor es erheblich langsamer wird. Für die meisten alltäglichen Probleme ist dieses n jetzt groß genug, dass Sie sich nicht mehr darum kümmern müssen. Sie sollten jedoch die Komplexität Ihrer Algorithmen kennen.

Wenn mehr Ressourcen zur Verfügung stehen, müssen möglicherweise später mehr Daten verarbeitet werden. Heute müssen Sie eine 10-MB-Protokolldatei mit 100.000 Zeilen analysieren. In einem Jahr haben Sie möglicherweise eine 100-GB-Protokolldatei mit 1.000.000.000 Zeilen. Wenn die Datenmenge schneller wächst als die Ressourcenleistung, treten später Probleme auf.

Mit mehr verfügbaren Ressourcen werden mehr Schichten übereinander gestapelt. Betriebssystem, Betriebssystem-Framework, Framework von Drittanbietern, Sprachinterpreter und schließlich Ihr eigenes Tool. Alle unnötigen Ineffizienzen in allen verschiedenen Schichten multiplizieren sich. Morgen läuft Ihr Tool möglicherweise auf einem neuen Betriebssystem mit mehr Schnickschnack, das selbst mehr Zyklen und mehr Speicher benötigt und weniger Zeit für Sie übrig lässt.

Um Ihre Frage zu beantworten, müssen Sie sich immer noch darum kümmern, wo immer mehr Daten komprimiert werden müssen (genügend Beispiele in den anderen Antworten) und wo Sie nicht das endgültige Tool, sondern eine weitere Abstraktionsebene für andere Tools bereitstellen.

Vor ein paar Jahren musste ich einen Algorithmus schreiben, mit dem auf nRacks angeordnete Reagenzgläser in zwei verschiedene Partitionen sortiert wurden : dh eine Teilmenge der Röhrchen wurde 'ausgewählt' und der Rest wurde 'nicht ausgewählt' und das Endergebnis wäre, dass kein Rack vorhanden ist würde sowohl ein "ausgewähltes" als auch ein "nicht ausgewähltes" Rohr haben (es gab einige zusätzliche Anforderungen wie Komprimierung). Jedes Rack enthielt maximal 100 Röhrchen.

Mit dem Algorithmus sollte ein Röhrensortierroboter in einem pharmazeutischen Labor angesteuert werden.

Als mir die ursprüngliche Spezifikation gegeben wurde, wurde mir im Bereich von 1 Minute Berechnungszeit das Sortieren von etwa 2000 Röhren zugeteilt, da wir der Meinung waren, dass die Benutzerfreundlichkeit nicht allzu schmerzhaft war. Es bestand die Anforderung, dass die Anzahl der Bewegungen über alle möglichen Kombinationen hinweg minimal sein sollte, da der Roboter selbst langsam war .

Die implizite Annahme war, dass die Komplexität mit der Anzahl der Röhren exponentiell sein würde. Bei der Arbeit am Algorithmusdesign habe ich jedoch festgestellt, dass es einen schnellen O(n)Algorithmus gibt, bei dem ndie Anzahl der Racks eine optimale Aufteilung der Röhren ermöglicht. Das Ergebnis war, dass die Sortierzeit des Algorithmus sofort war, sodass die Sortieranzeige in Echtzeit aktualisiert wurde, wenn der Benutzer seine Sortieroperation konfigurierte.

Für mich war der Unterschied zwischen dem Benutzer, der nach jeder Änderung eine Minute sitzt und eine sofort reagierende Benutzeroberfläche hat, der Unterschied zwischen einer Software, die funktionell ausreicht, und einer Software, die Spaß macht.

Andere Bereiche umfassen viele Arten von Echtzeit-Signalverarbeitung, Rückkopplungskontrollsysteme, Entfaltung der Ölerkundung, Videokomprimierung, Raytracing und Film-Frame-Rendering, Virtual-Reality-Systeme, Spiele, bei denen eine hohe Bildrate einen erheblichen Wettbewerbsvorteil darstellen könnte, sowie Smartphones und andere Apps für Mobilgeräte, bei denen eine große Anzahl von CPU-Zyklen die Akkulaufzeit des Benutzers verkürzt.

Ich bin ziemlich überrascht, dass diese Frage überhaupt gestellt werden würde, da es für jeden Top-500-Supercomputer, der jemals gebaut wurde, wahrscheinlich eine Warteliste von Forschern gibt, die alles ausschöpfen können und sich mehr Rechenleistung oder bessere Algorithmen wünschen, um ein Problem zu lösen (Falte Protein, um Krebs zu entziffern usw.), bevor sie in Rente gehen.

Ich denke, Suchmaschinen wie Google und Bing sind einer der größten Bereiche, in denen komplexe Algorithmen verwendet werden, und sie spielen eine Schlüsselrolle bei der Beschleunigung der Ergebnisse mit Relevanz (Page-Ranking), was den Nutzern mehr Nutzen bringt.

Die Effizienz von Algorithmen ist heutzutage kein großes Problem, da wir effiziente Algorithmen verwenden. Wenn Sie einen O (n!) - Algorithmus verwenden, ist dieser auf jeder Art von Hardware langsam.

Die Komplexität von Algorithmen wird mit zunehmender Datenmenge immer wichtiger. Glücklicherweise sind effiziente generische Lösungen für häufig auftretende Programmierprobleme (hauptsächlich Suchen und Sortieren) in der Standardbibliothek jeder modernen Programmiersprache enthalten. Daher muss sich ein Programmierer normalerweise nicht viel darum kümmern. Der Nachteil ist, dass viele Programmierer überhaupt nicht wissen, was unter der Haube vor sich geht und welche Eigenschaften die von ihnen verwendeten Algorithmen haben.

Dies ist besonders problematisch, da viele Anwendungen nicht ausreichend auf Stress getestet werden: Die Leute schreiben Code, der für kleine Testdatensätze gut geeignet ist, aber wenn sie mit ein paar tausend Mal mehr Daten konfrontiert werden, kommt der Code zum Erliegen. Etwas, das für zehn Datensätze gut funktioniert, explodiert schnell, wenn der Datensatz wächst. Beispiel aus der Praxis: Ein Teil des Codes, der Elemente bereinigen sollte, die keiner Kategorie mehr zugeordnet waren, verwendete eine verschachtelte Schleife mit drei Ebenen, nämlich O (n ^ 3). Mit nur 10 Datensätzen in der Testdatenbank bedeutete dies 1000 Überprüfungen - perfekt durchführbar und ohne merkliche Verzögerung. Die Produktionsdatenbank füllte sich jedoch schnell mit ungefähr 1000 Zeilen, und plötzlich führt der Code jedes Mal eine Milliarde Überprüfungen durch.

Also: Nein, Sie müssen nicht über die Vor- und Nachteile der Implementierung aller Arten von Algorithmen Bescheid wissen, und Sie müssen nicht in der Lage sein, Ihre eigenen zu erfinden. Sie benötigen jedoch einige Grundkenntnisse über gängige Algorithmen Stärken und Schwächen sind, wann und wann sie nicht verwendet werden sollen, und Sie müssen die möglichen Auswirkungen der algorithmischen Komplexität berücksichtigen, damit Sie entscheiden können, welcher Komplexitätsgrad akzeptabel ist.

Es ist keine Frage, welche Anwendungsdomänen für die Laufzeit relevant sind. Jedes Programm hat überall eine Mindestleistung, unter der es effektiv wertlos ist. Die Komplexität des Algorithmus hängt davon ab, wie er mit zunehmender Eingabegröße variiert. Mit anderen Worten, die Bereiche, in denen Geschwindigkeit besonders wichtig ist, sind diejenigen, in denen Sie nicht nur Ihre aktuelle Problemgröße, sondern auch die Größenordnung überschreiten müssenvon Ihrer aktuellen Problemgröße. Wenn Sie die Steueranträge der Bürger eines französischen Departements bearbeiten, ist die Aufgabe zwar groß, aber es ist unwahrscheinlich, dass sich die Bevölkerungszahl oder die Komplexität der Bearbeitung eines Datensatzes je um das Zehn- oder Hundertfache erhöht, was auch immer funktioniert Sie werden jetzt wahrscheinlich weiterarbeiten. Wenn Sie jedoch versuchen, etwas zu erstellen, das sich bei Internetvolumina auszahlt, ist die Komplexität des Algorithmus von entscheidender Bedeutung: Alles, was mehr als linear oder logarithmisch von der Eingabegröße abhängt, wird sehr schnell sehr viel teurer, und die Prozessorgeschwindigkeit kann es schließlich einfach nicht Schritt halten mit dem Wachstum.

In meinem Bereich (VFX, der Dinge wie Pfadverfolgung, Computeranimation, Partikelsimulation, Fluiddynamik, Bildverarbeitung usw. abdeckt) ist die algorithmische Komplexität von grundlegender Bedeutung. Es gibt keine Möglichkeit, dass etwas, das in schlechterer Zeit als linearithmisch arbeitet, bei Eingaben, die normalerweise Millionen von Scheitelpunkten, Polygonen, Voxeln, Partikeln und Texeln erreichen, in einer angemessenen Zeit abgeschlossen werden kann, insbesondere wenn viele dieser Dinge viele Male pro Sekunde abgeschlossen werden müssen Interaktives Echtzeit-Feedback.

Trotzdem ist die algorithmische Komplexität in Diskussionen, die normalerweise unter Kollegen geführt werden, nicht so stark ausgeprägt, vielleicht weil sie etwas Selbstverständliches und eher "rudimentär" ist. Wenn Sie einen Pfad-Tracer schreiben, wird im Allgemeinen davon ausgegangen, dass er in logarithmischer Zeit oder besser arbeitet und dass Datenstrukturen wie die Begrenzung von Volumenhierarchien bekannt und für den Leser relativ trivial zu implementieren sind. Ich hatte sogar einen erfahrenen Kollegen, der immer wieder sagte, dass Multithreading und SIMD wichtiger sind als Algorithmen, und ich glaube nicht, dass er dies in dem Sinne meinte, dass man von der Parallelisierung einer Blasensorte viel erwarten kann. Ich denke, er sagte, weil er es für selbstverständlich hielt, dass wir vernünftige Algorithmen anwenden würden,

Heutzutage liegt der Schwerpunkt häufig darauf, viele dieser bekannten Algorithmen besser auszunutzen und die zugrunde liegenden Eigenschaften der Hardware wie CPU-Cache, SIMD-Register und -Anweisungen, GPUs und mehrere Kerne besser auszunutzen. Zum Beispiel hat Intel eine neue Methode entwickelt, um das bekannte alte BVH aufzugreifen und das Konzept der "Strahlenpakete" zu entwickeln. Dabei wurden im Grunde genommen mehrere kohärente Strahlen gleichzeitig mit einer rekursiven Art von Baumdurchquerung getestet (was so klingen könnte) Dies ist mit einem Teil der Komplexität und des Overhead verbunden, außer dass dies mehr als nur durch die Tatsache kompensiert wird, dass diese Strahlen nun gleichzeitig durch SIMD-Anweisungen und -Register auf Ray / AABB- und Ray / Triangle-Schnittpunkte getestet werden können.

Ähnliches gilt für die Catmull-Clark-Unterteilung, die in der Computergrafik sehr rudimentär ist. Heutzutage sind GPU-Implementierungen, die sich der CC-Unterteilung mit Gregory Patches annähern, wie sie von Charles Loop und später von Pixar übernommen wurden, wettbewerbsfähig, heiß und äußerst effizient. Die einfachere CPU-Implementierung ist mittlerweile ziemlich veraltet, nicht unbedingt, weil sie hinsichtlich der algorithmischen Komplexität ersetzt wurde, sondern weil sie durch etwas ersetzt wurde, das mit der GPU gut funktioniert.

Und das ist in der Regel eine große Herausforderung heutzutage darin, den besten Algorithmus nicht in einer Weise zu entwickeln, die relativ unabhängig von den zugrunde liegenden Eigenschaften der Hardware ist. Tatsächlich habe ich mich in der Branche durch eine neuartige Beschleunigungsstruktur etabliert, die die Kollisionserkennung für die Animation von Zeichen und anderen weichen Körpern in den 90er Jahren mithilfe eines hierarchischen Segmentierungsansatzes erheblich beschleunigte, im Gegensatz zu einem räumlichen Index, der mir sehr viel gebracht hat Stellenangebote, aber heutzutage ist es nicht mehr so ​​beeindruckend, seit ich es veröffentlicht habe, lange bevor wir so beeindruckende CPU - Caches und Mehrfachkerne und programmierbare GPUs hatten und was nicht, und heutzutage benutze ich einen völlig anderen Ansatz aufgrund der signifikanten Änderungen an der zugrunde liegende Hardware.

Ich bin einmal auf ein Problem gestoßen, bei dem ein Algorithmus normalerweise in O (n) lief, aber in seltenen und äußerst unwahrscheinlichen Fällen O (n ^ 3) Zeit benötigt - die "seltenen" Umstände waren ein Verzeichnis, das Dateien mit Namen enthielt, in denen gültig war ein Betriebssystem, aber nicht in einem anderen.

Niemand ist jemals auf Probleme gestoßen. Dann hat ein Kunde eine Strategie angewendet, um Dateien zu benennen, die systematisch in den O (n ^ 3) -Fall laufen würden, und mit einigen 100 Dateien kam das System zum virtuellen Stillstand. Ergebnis war, dass der Algorithmus geändert werden musste.

Drei weitere, die nicht erwähnt wurden:

1) Viele Echtzeit-Strategiespiele. Schauen Sie sich diejenigen an, deren Einheiten keine Position teilen können. Beobachten Sie, was mit der Wegfindung passiert, wenn sich eine große Gruppe von Einheiten durch unwegsames Gelände bewegt. Ich habe bisher noch kein Spiel ohne ein wesentliches Problem damit, weil einfach nicht genug CPU-Leistung zur Verfügung steht.

2) Viele Optimierungsprobleme. (Bearbeiten: Seit ich diese Antwort geschrieben habe, habe ich eine getroffen. Mein Ziel war es, redundante Pfade zu beschneiden, damit alle Knoten mit dem minimalen Gewicht der Verbindungspfade verbunden bleiben. Mein ursprünglicher Ansatz funktionierte ziemlich gut, bis ich mehr vom Beschneiden entfernt habe Nach dieser Routine wurde mir klar, dass es 2 ^ n war. Jetzt ist es n ^ 2, obwohl dies manchmal zu einem leicht nicht optimalen Ergebnis führen kann.)

3) Dinge, die mit großen Datenmengen in Echtzeit arbeiten müssen. Betrachten Sie eine DVD: Sie erhalten normalerweise 2 Stunden Video in 4,7 GB. Stellen Sie sich eine typische Videodatei mit der gleichen Auflösung vor: Diese 2 Stunden Video fallen normalerweise unter 1 GB. Der Grund dafür ist, dass Sie als die DVD-Spezifikation festgelegt wurde, keinen günstigen DVD-Player herstellen konnten, der die moderneren Formate schnell genug entschlüsseln konnte.

Nun, jede Anwendung, die normalerweise auf einem Supercomputer ausgeführt wird ( Liste der größten Computer ) , ist geeignet . Diese sind vielfältig, aber eine große Unterklasse sind Physiksimulationen:

• Physiksimulationen:
  • Wettervorhersage
  • Klimasimulationen
  • Simulationen explodierender Sterne etc.
  • Simulationen explodierender Atomwaffen
  • Aerodynamische Simulationen von Autos / Flugzeugen / Zügen usw.
  • ...
• Berechnen von Bildern aus Radioteleskopdaten
• Biologische Anwendungen:
  • Zeug mit DNA-Sequenzen (ich bin nicht wirklich in diese)
  • Biochemisches Zeug wie Proteinfaltung
  • Simulationen, wie Nervenzellen zusammenarbeiten, um Informationen zu verarbeiten
  • Simulationen anderer komplexer Wechselwirkungen wie Ökosysteme
  • ...
• ...

Dies sind nur die Top-Themen in meinem Kopf, aber lesen Sie einfach die Liste der verschiedenen Supercomputer und stellen Sie fest, dass jeder einzelne davon so konstruiert ist, dass er eine oder mehrere Arten von Berechnungen ermöglicht, die ohne solch gigantische Maschinen nicht möglich wären.

Und sobald Sie sehen, dass wir diese Maschinen tatsächlich benötigen, können Sie feststellen, wie viel Kosten gespart werden können, indem Sie diese Anwendung um 10% beschleunigen . Jede Optimierung dieser Codes erhöht direkt die Menge der Ergebnisse, die wir aus diesen Maschinen herausholen können.