Ist big-O bei der Arbeit in der Industrie wirklich so relevant?

In jedem Interview, in dem ich mitgewirkt habe, habe ich mich mit der mathematischen Analyse der Komplexität einschließlich der Big-O-Notation befasst.

Wie relevant ist die Big-O-Analyse für die Entwicklung in der Industrie? Wie oft benutzt du es wirklich und wie wichtig ist es, eine geschärfte Denkweise für das Problem zu haben?

Meine Frage ist, wie relevant dieser Test für die Entwicklung in der Industrie ist.

Ein solides Verständnis der Theorie der rechnerischen Komplexität (z. B. Big-O-Notation) ist für den Entwurf skalierbarer Algorithmen, Anwendungen und Systeme unerlässlich. Da die Skalierbarkeit in der Industrie für das Computing von großer Bedeutung ist, gilt dies auch für die Big-O-Notation.

Wie oft setzen Sie es wieder ein und wie wichtig ist es, eine ausgefeilte Denkweise für das Problem zu haben?

Kommt darauf an, was du mit "wiederverwenden" meinst. Einerseits führe ich für die Software, die ich schreibe, niemals formale Beweise für die Komplexität der Berechnungen durch. Andererseits muss ich mich an den meisten Tagen mit Anwendungen befassen, bei denen die Skalierbarkeit ein potenzielles Problem darstellt, und zu den Entwurfsentscheidungen gehört die Auswahl (beispielsweise) geeigneter Sammlungstypen auf der Grundlage ihrer Komplexitätsmerkmale.

(Ich weiß nicht, ob es möglich ist, skalierbare Systeme ohne ein solides Verständnis der Komplexitätstheorie konsistent zu implementieren . Ich würde eher glauben, dass dies nicht der Fall ist.)

Der Grund dafür ist, dass dies auf Skalierbarkeit hinweist .

Ein Prozess, der O (n ^ 2) ist, skaliert schlechter als einer, der O (n log n) ist, aber besser als einer in O (n ^ 3) oder sogar O (n!).

Wenn Sie die Unterschiede nicht kennen und wenn sie zutreffen, sind Sie weniger geeignet, die richtigen Implementierungen der Funktionalität auszuwählen und die Testleistung in die Produktionsleistung zu extrapolieren.

BEARBEITEN: Ein Vergleich von 48n mit n ^ 3 von http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (was wiederum von Programming Pearls stammt)

Es hängt davon ab, was Sie tun.

Für Webentwickler (wie mich) ist dies normalerweise sehr wichtig. Sie möchten, dass Web-Apps skaliert werden. Wenn Ihre App einen Engpass hat, der mit O (n ^ 2) skaliert, und Sie denken, dass dies in Ordnung ist, weil Ihr Server 1000 gleichzeitige Benutzer verarbeiten kann, scheint es, dass Sie sich nicht darum kümmern müssen. Die Sache ist, um nur doppelt so viele zu handhaben (was wahrscheinlich nur über Nacht passiert), werden Sie das Vierfache der Rechenleistung benötigen. Idealerweise möchten Sie, dass Web-Apps bei O (n) skaliert werden, da Hardware bei einem vernünftigen konstanten Benutzer / Server-Verhältnis billig ist.

Im Allgemeinen wird Big O in Apps, in denen Sie über 100.000 Objekte verfügen, Sie verzehren. Sie sind enorm anfällig für Spitzen. Zum Beispiel arbeite ich gerade an einem 3D-Spiel, einer App, die viele Daten verarbeitet. Abgesehen vom Rendern haben Sie Kollisionsprüfung, Navigation usw. Sie können es sich nicht leisten, einfach den offensichtlichen Weg zu gehen. Sie benötigen effiziente Algorithmen und viel Caching, damit sich die weniger effizienten amortisieren. Und so weiter.

Wenn Sie beispielsweise eine mobile App erstellen, indem Sie eine grafische Benutzeroberfläche in einem Interface-Designer zusammenfassen, diese mit einigen Webdiensten verknüpfen und das war's dann werden Sie nie Probleme mit der Komplexität haben. Denn die von Ihnen angerufenen Web-Services kümmern sich bereits darum.

Ich habe die Regel in meinem Arbeitsleben nie förmlich angewandt.

Sie müssen jedoch mit diesem Konzept vertraut sein und es jedes Mal, wenn Sie einen Algorithmus entwerfen, intuitiv anwenden.

Die Regel ist:

Sie sollten mit der O-Notation vertraut genug sein, um für eine bestimmte Aufgabe bestimmen zu können, ob sie formal berechnet werden muss oder ob sie nur zur intuitiven Bewertung ausreicht oder ob Sie sie ganz überspringen können. Genau wie viele andere mathematische Grundbegriffe.

Nun, vielleicht klärt Sie eine kleine Geschichte darüber auf, warum es definitiv notwendig ist:

In einem Projekt, an dem ich gearbeitet habe, gab es ein Programm, das für das Drucken aller Arten von Dokumenten (Etiketten, Kommissionierlisten usw.) zuständig war. Dieses Programm bestand aus zwei Teilen, von denen einer alle erforderlichen Daten aus der Datenbank las und sie in eine Datenbank schrieb Datei im INI-Stil und ein weiterer Teil, der diese Dateien liest und in die Vorlagen einfügt. Dies funktionierte recht gut für Etiketten und kleine Listen (mit nur wenigen Feldern), lief jedoch fast 10 Minuten, als eine "große" Liste von ~ 20 Seiten gedruckt werden musste. Weil der Zugriff auf diese Ini-Dateien zu O (n²) Zugriffszeiten führte, wobei n die Anzahl der zu druckenden Felder ist.

Wenn die ursprünglichen Programmierer dieses Programms die O-Notation verstanden hätten, hätten sie es niemals so gemacht. Das Ersetzen dieser Dummheit durch eine Hash-Tabelle machte es soooooooo viel schneller.

Die Leistung von Big-O ist wichtig, wurde jedoch weitgehend verinnerlicht.

Die Big-O-Leistung beim Sortieren und Suchen spielt keine Rolle, da die Benutzer im Allgemeinen die vom System bereitgestellten verwenden und diese so gut wie möglich sind (vorausgesetzt, sie müssen allgemein nützlich sein). Es gibt Datenstrukturen, die für verschiedene Zwecke effizienter sind, die jedoch in der Regel nach allgemeinen Grundsätzen ausgewählt werden können (und in der Regel in moderne Sprachen integriert sind). Es gibt einige Algorithmen, die skalieren oder nicht skalieren.

Das Ergebnis ist, dass die formalen Fragen in der Praxis selten auftauchen, aber die Praxis auf denselben Prinzipien beruht.

IMHO viele Informatik-Programme lassen viele Studenten dort unten im Unkraut wandern. Diese Programme vermitteln nie ganz das Gesamtbild dessen, worum es bei der Wissenschaft des Rechnens geht. Die Studenten betreten die Branche und setzen sich mit der Anwendung der erlernten Konzepte auseinander. Sie haben wenig Einblick in ihre Beziehung zur realen Welt.

Ich würde sagen, dass das Herz der Wissenschaft des Rechnens die Fähigkeit ist, über das Rechnen zu argumentieren. Und Sie lernen verschiedene Methoden und Techniken, um dies zu tun, und wenden sie auf abstrahierte Probleme an, die prototypische Grundelemente sind, die in vielen Problemen der realen Welt zu finden sind. Der Trick besteht darin, diese prototypischen Grundelemente in der realen Welt zu erkennen und dann über Dinge wie Korrektheit, Komplexität, Zeit usw. nachzudenken. Einblick in das Verhalten der Teile, gibt Ihnen häufig Einblick in das Verhalten des Ganzen. Und die gleichen allgemeinen Methoden und Techniken können auch auf das Ganze angewendet werden, nur nicht mit der gleichen Strenge, die auch für kleinere, gut abstrahierte, gut definierte Teile gilt. Aber am Ende gibt Ihnen die Wissenschaft der Berechnung die Fähigkeit, vernünftig zu machen Entscheidungen darüber, wie Ihre Berechnung angeordnet werden soll, mit wirklichem Einblick, wie sie sich unter verschiedenen Bedingungen verhält.

Memo to self !:

Ich und viele andere stellen mir diese Frage regelmäßig.

Ich denke, der wahre Grund, warum wir das fragen, ist, dass wir faul geworden sind.

Dieses Wissen wird niemals datiert oder veraltet sein. Sie können es nicht täglich direkt anwenden, aber Sie werden es unbewusst anwenden und es wird sich positiv auf Ihre Entwurfsentscheidungen auswirken. Eines Tages können Sie oder andere Stunden und Tage der Codierung sparen.

Da immer mehr Probleme in Bibliotheken und Tools von Drittanbietern enthalten sind und immer mehr Entwicklern zur Verfügung stehen, müssen Sie über dieses Wissen verfügen, um sich von anderen zu unterscheiden und neue Probleme zu lösen.

Nicht wirklich. Grundsätzlich ist das einzige Mal, dass ich darüber nachdenke, der Zugriff auf die Datenbank. Normalerweise schaue ich mir den Code an und sage: "Das macht n + 1-Abfragen, Sie sollten es so ändern, dass es nur 1 oder 2 macht."

Da alle meine Daten aus einer Datenbank gelesen und dem Benutzer angezeigt werden, versuche ich, die Datenmenge, mit der ich arbeite, so weit zu minimieren, dass der Unterschied zwischen einem linearen und einem O (n ^ 2) -Algorithmus ziemlich groß ist unerheblich.

Wenn es ein Problem gibt, werden wir es später profilieren und beheben.

Drei Fragen, die Sie gestellt haben, und ich denke, dass kurze Antworten die längeren Argumente unterstützen könnten, die bisher vorgebracht wurden.

Wie relevant ist dieser Test für die Entwicklung in der Industrie?

Kommt auf die Branche an.

Überall dort, wo Codegeschwindigkeit oder Code-Speicherplatz eine Rolle spielen, ist dies für die betreffende Branche von großer Bedeutung. Oft muss man wissen, wie lange eine Routine dauert oder wie viel Speicher (on / offline) benötigt wird.

Wie oft benutzt du es wirklich?

Kommt auf die Branche an.

Wenn Leistung und Skalierung für den jeweiligen Auftrag keine Rolle spielen, ist dies nur selten der Fall, wenn ein schwerwiegender Leistungsmangel vorliegt. Wenn Sie ein Ingenieur für ein häufig verwendetes kritisches System sind, dann wahrscheinlich jeden Tag.

Wie wichtig ist es, eine ausgefeilte Denkweise für das Problem zu haben?

Völlig notwendig.

Möglicherweise müssen Sie es täglich oder nur unter schwierigen Umständen verwenden. aber manchmal wird es gebraucht. Vorzugsweise während des Entwurfs, bevor ein Problem auftritt, als ein Drosselsystem verzweifelt zu profilieren.

Ich würde sagen, es ist sehr häufig. Wir beweisen im Allgemeinen nicht, dass etwas ein bestimmtes Big-O hat, aber wir haben die Idee verinnerlicht und die Big-O-Garantien für bestimmte Datenstrukturen und Algorithmen auswendig gelernt / kennen gelernt, und wir wählen die schnellsten für eine bestimmte Verwendung aus. Es ist hilfreich, eine Bibliothek mit allen Optionen zu haben, wie die Java-Auflistungsbibliothek oder die C ++ - STL. Sie verwenden implizit und natürlich jeden Tag big-O, wenn Sie eine java.util.HashMap( O(1)Suche) anstelle einer java.util.TreeMap( O(lg n)Suche) verwenden und auf jeden Fall keine lineare Suche über eine java.util.LinkedList( O(n)Suche) nach etwas ausführen, für das Sie keinen sortierten Zugriff benötigen.

Wenn jemand eine suboptimale Implementierung auswählt und jemand, der es besser weiß, kommt und seinen Code sieht, ist es Teil unseres Vokabulars, sie zu korrigieren. "Ihre Implementierung benötigt quadratische Zeit, aber wir können dies auf n-log-n-Zeit reduzieren, indem wir dies tun auf diese weise "stattdessen so natürlich und automatisch, wie wir die englische sprache verwenden würden, um eine pizza zu bestellen.

Ja

Möglicherweise müssen Sie keine formalen Analysen durchführen, aber zumindest ein eingehendes Verständnis der Reihenfolge der Komplexität von Algorithmen - und wie man zwei Algorithmen damit vergleicht - ist von entscheidender Bedeutung, wenn Sie nicht-triviale Arbeit leisten möchten und sie sich als gut herausstellen möchten.

Ich habe an zwei verschiedenen Systemen gearbeitet, die in der frühen Entwicklung gut ausgesehen haben, aber die Hardware bei Produktionstests in die Knie gezwungen haben, weil jemand einen O (n ^ 2) -Algorithmus verwendet hat. In beiden Fällen handelte es sich um eine geringfügige Änderung eines O (n) -Algorithmus.

Es wird wahrscheinlich an Orten verwendet, an denen APIs für den Verbrauch entwickelt werden. Die C ++ STL ist eine der wenigen APIs, deren Algorithmen Komplexitätsbeschränkungen unterliegen. Aber für den alltäglichen Arbeitsprogrammierer / Senior-Programmierer / Designer / Architekt fällt ihnen nicht viel ein.

Ich fand es nicht so wichtig, außer um Ideen zu kommunizieren, und ich arbeite in leistungskritischen Bereichen (Raytracing, Bild- und Netzverarbeitung, Partikelsysteme, Physik-Engines usw.) und musste viele proprietäre Algorithmen und Datenstrukturen entwickeln bei der Arbeit in F & E. In diesen Bereichen kann eine Handvoll sehr effizienter Datenstrukturen und Algorithmen zu völlig neuen Spitzenprodukten führen, während die gestrigen Algorithmen vorhandene Produkte überflüssig machen, sodass stets eine effizientere Arbeitsweise angestrebt wird. Aus Sicherheitsgründen habe ich noch nie Artikel zu den von mir entwickelten Algorithmen veröffentlicht. Sie waren alle Eigentum. Wenn ich das tun würde, würde ich die Hilfe eines Mathematikers brauchen, um Beweise und so weiter zu formulieren.

Meiner Meinung nach ist die Menge an Rechenarbeit pro Iteration jedoch oft von unmittelbarerem Interesse als die Skalierbarkeit des Algorithmus, es sei denn, der Algorithmus skaliert wirklich schlecht. Wenn sich jemand ein innovatives Raytracing-Verfahren einfallen lässt, interessieren mich eher Computertechniken wie die Darstellung und der Zugriff auf Daten als die algorithmische Komplexität, da in diesem wettbewerbsorientierten und innovativen Szenario eine angemessene Skalierbarkeit bereits gegeben ist. Sie können nicht wettbewerbsfähig sein, wenn Sie Algorithmen entwickeln, die sich nicht skalieren lassen.

Wenn Sie die quadratische Komplexität mit der linearen vergleichen, ist das natürlich ein großer Unterschied. Aber die meisten Leute auf meinem Gebiet sind kompetent genug, um die Anwendung eines quadratischen Komplexitätsalgorithmus auf einen epischen Eingang zu vermeiden. Die Skalierbarkeit ist also oft tiefgreifend impliziert, und die aussagekräftigeren und interessanteren Fragen lauten: "Haben Sie GPGPU verwendet? SIMD? Wird es parallel ausgeführt? Wie haben Sie die Daten dargestellt? Haben Sie sie für cachefreundliche Zugriffsmuster neu organisiert? Wie viel Speicher benötigt es? Kann es diesen Fall robust behandeln? Verschieben Sie eine bestimmte Verarbeitung oder erledigen Sie alles auf einmal? "

Sogar ein linearithmischer Algorithmus kann einen linearen Zeitalgorithmus übertreffen, wenn der erstere beispielsweise in einem optimaleren Muster auf den Speicher zugreift oder besser für Multithreading und / oder SIMD geeignet ist. Manchmal kann sogar ein linearer Algorithmus aus diesen Gründen einen logarithmischen Algorithmus übertreffen, und natürlich übertreffen Algorithmen mit linearer Zeit logarithmische Algorithmen für Teeny-Eingaben.

Was für mich wichtiger ist, sind die sogenannten "Mikrooptimierungen", wie z. B. Datendarstellungen (Speicherlayouts, Zugriffsmuster mit Hot / Cold-Field-Splitting usw.), Multithreading, SIMD und gelegentlich GPGPU. In einem Bereich, in dem jeder bereits kompetent genug ist, um stets aktuelle Algorithmen für alles zu verwenden und neue Artikel zu veröffentlichen, liegt Ihr Wettbewerbsvorteil gegenüber den Algorithmus-Assistenten nicht in der Verbesserung der algorithmischen Komplexität, sondern vielmehr in der Direktheit Recheneffizienz.

Mein Fachgebiet wird von brillanten Mathematikern dominiert, aber nicht immer von solchen, die den Rechenaufwand für das, was sie tun, oder viele Tricks auf niedrigerer Ebene kennen, um den Code zu beschleunigen. Das ist normalerweise mein Vorteil, wenn es darum geht, schnellere und präzisere Algorithmen und Datenstrukturen zu entwickeln, obwohl ich viel weniger ausgefeilt bin. Ich spiele mit dem, was die Hardware mag, auf Bits und Bytes zu und mache jede Arbeitsiteration viel billiger, selbst wenn ich ein paar Iterationen mehr arbeite als der wirklich ausgefeilte Algorithmus - die Arbeit in meinem Fall ist drastisch billiger. Der Code, den ich schreibe, ist auch viel einfacher. Wenn die Leute denken, dass mikrooptimierte Versionen von einfachen Algorithmen und Datenstrukturen schwer zu verstehen und zu warten sind,

Als grundlegendes Beispiel habe ich eine einfache Gitterstruktur entwickelt, die einen KD-Baum in unserem Unternehmen für die Kollisionserkennung und das Entfernen redundanter Punkte übertrifft. Mein dummes Rohgitter war algorithmisch so viel weniger ausgefeilt und ich bin mathematisch und algorithmisch viel dümmer als der Typ, der den KD-Baum mit seiner neuartigen Methode zum Finden des Medianpunkts implementiert hat, aber ich habe gerade die Speichernutzung und Zugriffsmuster meines Gitters optimiert und das war genug, um etwas viel raffinierteres zu übertreffen.

Ein weiterer Vorteil, den ich habe und der es mir ermöglicht, in einem Umfeld zu überleben, das von Menschen dominiert wird, die viel schlauer sind als ich, besteht darin, wirklich zu verstehen, wie der Benutzer arbeitet, da ich die Software verwende, die ich auf die gleiche Weise entwickle. Das gibt mir Ideen für Algorithmen, die wirklich sehr schnell mit den Benutzerinteressen übereinstimmen. Als grundlegendes Beispiel versuchen die meisten Menschen, Dinge wie die Kollisionserkennung mithilfe der räumlichen Indizierung zu beschleunigen. Ich habe vor fast ein paar Jahrzehnten eine einfache karriereprägende Beobachtung für organische Modelle gemacht, wonach beispielsweise eine räumliche Indexstruktur, wenn ein Charakter seine Hände auf sein Gesicht legt, Knoten aufteilen und teure Aktualisierungen vornehmen müsste, wenn der Charakter dann nahm er die Hand vom Gesicht. Wenn Sie stattdessen anhand von Konnektivitätsdaten und nicht anhand von Scheitelpunktpositionen partitionieren, Sie können eine stabile hierarchische Struktur erhalten, die sehr schnell aktualisiert wird und niemals den Baum teilen oder neu ausbalancieren muss (nur die Begrenzungsrahmen müssen in jedem Bild der Animation aktualisiert werden) Das könnte sich einfallen lassen, wenn sie nur das Grundkonzept verstehen, aber diejenigen, die sich den Mathematikern entziehen, da sie die Dinge nicht so genau betrachten, wie die Benutzer arbeiten, und zu viel über die Eigenschaften der Geometrie nachdenken und nicht über die Geometrie wurde allgemein verwendet. Ich komme gut genug zurecht, indem ich mich mehr auf allgemeine Computer- und Benutzerkenntnisse als auf algorithmische Zauberei stütze. Ich fand es sowieso nicht wirklich wichtig, mich auf die algorithmische Komplexität zu konzentrieren.

Ja, Komplexität spielt in der Branche eine Rolle. Wenn Sie am Ende etwas entwerfen, bei dem ein kritischer Pfad als N-Quadrat skaliert (wenn Sie die Anzahl von Elementen verdoppeln, wird das System viermal so geladen), wird der Skalierungsengpass schneller erreicht als bei N-Skalierungen.

Es ist jedoch in der Regel kein richtiger, formaler Beweis dafür, dass sich etwas in einer bestimmten Komplexität befindet. Daher ist es ein guter Anfang, eine gute Intuition für die Komplexität eines Operationsmusters zu haben.

Ich denke aus mathematischer Sicht nie an ein großes O, ich denke überhaupt nicht an ein großes O, es sei denn, ich werde gefragt. Ich sehe nur einen Algorithmus in meinem Kopf und kann feststellen, ob er schlecht ist, weil er für jedes N mehrere Schleifen durch den Speicher führt oder ob er sich teilt und erobert oder so etwas. Bei Bedarf kann ich das in wenigen Sekunden in große O-Notation übersetzen, aber es ist einfacher für mich, nur zu wissen, wie der Algorithmus / Container mit dem Speicher funktioniert, als über die mathematische Perspektive nachzudenken.

Die Fragen, die in Interviews gestellt werden, sollen herausfinden, ob Sie Dinge erklären und logisch denken können . Der Interviewer versucht auch herauszufinden, ob Sie das , was Sie wissen, einsetzen können , um ein damit zusammenhängendes Problem zu lösen .

Jeder, der sich mit Software-Engineering befasst hat, ist auf „Big O“ gestoßen. Um eine gute Frage zu „Big O“ zu beantworten, müssen Sie auch mit Standarddatenstrukturen und -algorithmen vertraut sein.

Wenn Sie für einen Mitarbeiter ein Vorstellungsgespräch führen, suchen Sie jemanden, der den Job schnell erlernen kann, und nicht jemanden, der bereits über bestimmte Detailkenntnisse verfügt. Daher kann es sehr schwierig sein, Fragen zu wählen, die sowohl für den Interviewer als auch für den Interviewten ein gemeinsames Verständnis haben von.

Fragen zu „Big O“ können daher für den Interviewprozess sehr relevant sein.

Während meiner langen Zeit als Computerprogrammierer musste ich mindestens jedes Jahr Code korrigieren, der langsam war, weil jemand die richtigen Datenstrukturen und Algorithmen nicht verstand. Sie können diese Probleme jedoch lösen, ohne ein detailliertes Verständnis von Big O zu haben. Menschen, die Big O tent verstehen, meiden diese Probleme jedoch überhaupt nicht.