it-swarm-eu.dev

Ist big-O wirklich so relevant, wenn man in der Industrie arbeitet?

In jedem Interview, in dem ich war, wurde ich zur mathematischen Analyse der Komplexität, einschließlich der Big-O-Notation, befragt.

Wie relevant ist die Big-O-Analyse für die Entwicklung in der Industrie? Wie oft verwenden Sie es wirklich und wie notwendig ist es, eine ausgefeilte Denkweise für das Problem zu haben?

66
MM01

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

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

Wie oft verwenden Sie es wirklich und wie notwendig ist es, eine ausgefeilte Denkweise für das Problem zu haben?

Hängt davon ab, was Sie unter "wirklich verwenden" verstehen. Einerseits mache ich niemals formale Beweise für die Komplexität der Berechnungen für die Software, die ich schreibe. Andererseits muss ich mich an den meisten Tagen mit Anwendungen befassen, bei denen Skalierbarkeit ein potenzielles Problem darstellt, und Entwurfsentscheidungen umfassen die Auswahl (zum Beispiel) geeigneter Sammlungstypen basierend auf ihren Komplexitätsmerkmalen.

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

76
Stephen C

Der Grund dafür ist, dass es die Skalierbarkeit anzeigt.

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 von Funktionen auszuwählen und die Testleistung in die Produktionsleistung zu extrapolieren.


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

enter image description here

36
user1249

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 aufweist, der mit O (n ^ 2) skaliert, und Sie der Meinung sind, dass dies in Ordnung ist, da Ihr Server 1000 gleichzeitige Benutzer verarbeiten kann, scheint es Ihnen egal zu sein. Die Sache ist, um nur doppelt so viele zu verarbeiten (was vernünftigerweise wahrscheinlich über Nacht passiert), benötigen Sie die vierfache Rechenleistung. Idealerweise möchten Sie, dass Web-Apps mit O (n) skaliert werden, da Hardware bei einem vernünftigen konstanten Benutzer/Server-Verhältnis billig ist.

Im Allgemeinen wird in Apps, in denen Sie 100000 Objekte haben, ein großes O kommen und Sie essen. Sie sind enorm anfällig für Spitzen. Zum Beispiel arbeite ich derzeit an einem 3D-Spiel, einer App, die viele Daten verarbeitet. Abgesehen vom Rendering haben Sie Kollisionsprüfung, Navigation usw. Sie können es sich nicht leisten, nur den offensichtlichen Weg zu gehen. Sie benötigen effiziente Algorithmen, Sie benötigen 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 zusammenfügen, diese mit einigen Webdiensten verbinden und das war's, dann werden Sie nie Probleme mit der Komplexität haben. Weil die von Ihnen aufgerufenen Webdienste sich bereits darum kümmern.

32
back2dos

Ich habe die Regel in meinem Berufsleben nie formell angewendet.

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

Die Regel ist :

Sie sollten mit der O-Notation hinreichend vertraut sein, um für eine bestimmte Aufgabe bestimmen zu können, ob eine formelle Berechnung erforderlich ist oder ob sie gerade ausreicht, um sie intuitiv zu bewerten, oder ob Sie sie einfach ganz überspringen können. Genau wie viele andere grundlegende mathematische Konzepte.

22
Wizard79

Nun, vielleicht klärt dich eine kleine Geschichte auf, warum es ENDGÜLTIG ist IS notwendig:

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

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

10
user281377

Big-O-Leistung 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 Dinge effizienter sind, aber diese können normalerweise nach allgemeinen Prinzipien ausgewählt werden (und sind normalerweise in moderne Sprachen integriert). Es gibt einen Sinn für Algorithmen, die skalieren oder nicht skalieren.

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

8
David Thornley

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

Ich würde sagen, dass das Herz der Berechnungswissenschaft die Fähigkeit ist, über Berechnungen nachzudenken. Dazu lernen Sie verschiedene Methoden und Techniken 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, die, wie Sie vielleicht zustimmen, echte Probleme sind, über die Sie sich Sorgen machen müssen. Einsicht in das Verhalten der Teile gibt Ihnen häufig Einblick in das Verhalten des Ganzen. Dieselben allgemeinen Methoden und Techniken können auch auf das Ganze angewendet werden, nur nicht mit der gleichen Strenge, die kleinere, gut abstrahierte, genau definierte Teile bieten. Aber am Ende gibt Ihnen die Wissenschaft der Berechnung die Möglichkeit, vernünftige Entscheidungen darüber zu treffen, wie Ihre Berechnung angeordnet werden soll, und einen echten Einblick in das Verhalten unter verschiedenen Bedingungen zu erhalten.

7
Ziffusion

Notiz an mich selbst!:

Ich und viele andere stellen sich 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 obsolet werden. Sie können es möglicherweise nicht direkt täglich anwenden, aber Sie werden es unbewusst verwenden 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 von Bibliotheken und Tools von Drittanbietern gekapselt werden und immer mehr Entwicklern zur Verfügung stehen, müssen Sie dieses Wissen kennen, um sich von anderen zu unterscheiden und neue Probleme zu lösen.

5
Conor

Nicht wirklich. Grundsätzlich denke ich nur beim Zugriff auf die Datenbank darüber nach. Normalerweise schaue ich mir den Code an und sage: "Das macht n + 1 Abfragen, Sie sollten ihn so ändern, dass er 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 gering wie möglich zu halten, bis der Unterschied zwischen einem linearen und einem O (n ^ 2) -Algorithmus groß ist unerheblich.

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

5
Greg

Drei Fragen, die Sie gestellt haben, und ich denke, Kurzantworten könnten die bisher vorgebrachten längeren Argumente unterstützen.

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

Abhängig von der Branche.

Überall dort, wo Codegeschwindigkeit oder Code-Speicherplatz ein Problem darstellen, ist dies für die betroffene Branche völlig relevant. Oft müssen Sie wissen, wie lange eine Routine dauert oder wie viel Speicher (on/offline) sie benötigt.

Wie oft benutzt du es wirklich?

Abhängig von der Branche.

Wenn Leistung und Skalierung für den jeweiligen Job von geringer Bedeutung sind, dann nur selten, wenn ein schwerwiegender Leistungsmangel vorliegt. Wenn Sie ein Ingenieur für ein häufig verwendetes kritisches System sind, wahrscheinlich jeden Tag.

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

Völlig notwendig.

Möglicherweise müssen Sie es jeden Tag oder nur unter schlimmen Umständen verwenden. aber manchmal wird es benötigt. Am besten während des Entwurfs, bevor ein Problem auftritt, als ein Drosselsystem verzweifelt zu profilieren.

3
Orbling

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 auswendig gelernt für bestimmte Datenstrukturen und Algorithmen, und wir wählen die schnellsten für eine bestimmte Verwendung aus. Es ist hilfreich, eine Bibliothek zu haben, die alle Optionen enthält, z. B. die Java Sammlungsbibliothek oder die C++ STL. Sie verwenden implizit und natürlich big-O jeden Tag = wenn Sie sich dafür entscheiden, einen Java.util.HashMap (O(1) Lookup) anstelle eines Java.util.TreeMap (O(lg n) Lookup) zu verwenden und sicher keine Linear auszuführen Suchen Sie in einem Java.util.LinkedList (O(n) Lookup) nach etwas, für das Sie keinen sortierten Zugriff benötigen.

Wenn jemand eine suboptimale Implementierung auswählt und jemand, der es besser weiß, vorbeikommt 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.

3
Ken Bloom

Ja

Möglicherweise müssen Sie keine formalen Analysen durchführen, aber zumindest ein genaues Verständnis der Reihenfolge der Algorithmuskomplexität - und des Vergleichs zweier Algorithmen - ist entscheidend, wenn Sie nicht triviale Arbeit leisten möchten und sich als gut herausstellen möchten.

Ich habe an zwei verschiedenen Systemen gearbeitet, die in der frühen Entwicklung in Ordnung zu sein schienen, aber die Hardware in Produktionstests in die Knie gezwungen haben, weil jemand einen O (n ^ 2) -Algorithmus verwendet hat. In beiden Fällen war das Update eine triviale Änderung eines O(n) - Algorithmus).

3
Bob Murphy

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 Programmierer/Senior-Programmierer/Designer/Architekten fällt ihnen nicht viel ein.

1
sashang

Ich fand es nicht so wichtig, außer 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 können oft eine Handvoll sehr effizienter Datenstrukturen und Algorithmen zu völlig neuen Produkten führen, während die Algorithmen von gestern vorhandene Produkte überflüssig machen. Daher wird immer versucht, die Dinge effizienter zu gestalten. Als Einschränkung habe ich jedoch noch nie Artikel über die von mir entwickelten Algorithmen veröffentlicht. Sie waren alle proprietär. Wenn ich das tun würde, würde ich die Hilfe eines Mathematikers brauchen, um Beweise zu formulieren und so weiter.

Meiner Meinung nach ist der Umfang der Rechenarbeit pro Iteration jedoch häufig von unmittelbarem Interesse als die Skalierbarkeit des Algorithmus, es sei denn, der Algorithmus skaliert wirklich schlecht. Wenn jemand eine hochmoderne Raytracing-Technik entwickelt, interessieren mich eher die Computertechniken wie die Darstellung und der Zugriff auf Daten als die algorithmische Komplexität, da in diesem wettbewerbsorientierten und innovativen Szenario bereits eine angemessene Skalierbarkeit gegeben ist. Sie können nicht wettbewerbsfähig sein, wenn Sie Algorithmen entwickeln, die nicht skalierbar sind.

Wenn Sie die quadratische Komplexität mit der linearithmischen vergleichen, ist das natürlich ein großer Unterschied. Aber die meisten Leute in meinem Bereich sind kompetent genug, um die Anwendung eines quadratischen Komplexitätsalgorithmus auf eine epische Eingabe zu vermeiden. Daher ist die Skalierbarkeit oft stark impliziert, und die aussagekräftigeren und interessanteren Fragen lauten wie folgt: "Haben Sie GPGPU verwendet? SIMD? Läuft es parallel? Wie haben Sie die Daten dargestellt? Haben Sie sie für Cache-freundlich reorganisiert?" Zugriffsmuster? Wie viel Speicher benötigt es? Kann es diesen Fall zuverlässig behandeln? Verschieben Sie bestimmte Verarbeitungen oder erledigen Sie alles auf einmal? "

Sogar ein linearithmischer Algorithmus kann einen linearen Zeitalgorithmus übertreffen, wenn der erstere in einem optimaleren Muster auf den Speicher zugreift, z. B. 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 lineare Zeitalgorithmen logarithmische Algorithmen für Teeny-Eingaben.

Für mich ist es wichtiger, was manche Leute als "Mikrooptimierungen" bezeichnen, wie Datendarstellungen (Speicherlayouts, Zugriffsmuster mit heißer/kalter Feldaufteilung usw.), Multithreading, SIMD und gelegentlich GPGPU. In einem Bereich, in dem jeder bereits kompetent genug ist, um für alles, was ständig neu veröffentlicht wird, anständige und hochmoderne Algorithmen zu verwenden, wird Ihr Wettbewerbsvorteil beim Sieg gegen die algorithmischen Assistenten nicht durch Verbesserungen der algorithmischen Komplexität, sondern durch direktere Ergebnisse erzielt Recheneffizienz.

Mein Fachgebiet wird von brillanten Mathematikern dominiert, aber nicht immer von denen, die die Rechenkosten ihrer Arbeit oder viele der Tricks auf niedrigerer Ebene kennen, um den Code zu beschleunigen. Das ist normalerweise mein Vorteil, wenn es darum geht, schnellere und engere Algorithmen und Datenstrukturen zu entwickeln, obwohl meine viel weniger ausgefeilt sind. Ich spiele mit dem, was die Hardware mag, mit Bits und Bytes und mache jede Iteration der Arbeit viel billiger, selbst wenn ich ein paar Iterationen mehr Arbeit mache 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 der Meinung sind, dass mikrooptimierte Versionen einfacher Algorithmen und Datenstrukturen schwer zu verstehen und zu warten sind, versuchen Sie, eine Sammlung exotischer netzbezogener Algorithmen und Datenstrukturen zu verstehen und zu pflegen, die in der Branche noch nie zuvor gesehen wurden. 20-seitige Artikel beschreiben ihre Schritte mathematisch .

Als grundlegendes Beispiel habe ich eine einfache Gitterstruktur entwickelt, die einen KD-Baum in unserem Unternehmen hinsichtlich Kollisionserkennung und Entfernung redundanter Punkte übertrifft. Mein dummes grobes Gitter 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 nur die Speichernutzung und die Zugriffsmuster meines Gitters und angepasst das war genug, um etwas viel Anspruchsvolleres zu übertreffen.

Ein weiterer Vorteil, den ich habe, der es mir ermöglicht, in einem Bereich zu überleben, der 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 unmittelbar mit den Benutzerinteressen übereinstimmen. Als grundlegendes Beispiel versuchen die meisten Menschen, Dinge wie die Kollisionserkennung durch räumliche Indizierung zu beschleunigen. Ich habe vor fast ein paar Jahrzehnten eine einfache karrierebildende Beobachtung für organische Modelle gemacht, bei der beispielsweise eine räumliche Indexierungsstruktur Knoten aufteilen und teure Aktualisierungen vornehmen müsste, wenn ein Charakter seine Hände auf sein Gesicht legt dann nahm er seine Hand von seinem Gesicht. Wenn Sie stattdessen auf der Grundlage von Konnektivitätsdaten und nicht auf Scheitelpunktpositionen partitionieren, erhalten Sie möglicherweise eine stabile hierarchische Struktur, die sehr schnell aktualisiert wird und den Baum niemals teilen oder neu ausgleichen muss (es müssen nur die Begrenzungsrahmen in jedem Frame der Animation aktualisiert werden). .. Dinge wie diese - Algorithmen, die ein Kind ohne großen mathematischen Hintergrund entwickeln könnte, wenn es nur das Grundkonzept versteht, aber solche, die sich den Mathematikern entziehen, da sie die Dinge nicht so nah an die Benutzer denken arbeiteten und dachten zu viel über die Eigenschaften der Geometrie nach und nicht darüber, wie Geometrie üblicherweise verwendet wurde. Ich verstehe mich gut genug, indem ich mich mehr auf allgemeines Computer- und Benutzerwissen als auf algorithmische Zauberei stütze. Ich fand es sowieso nicht so wichtig, mich auf die algorithmische Komplexität zu konzentrieren.

1
user204677

Ich denke nie an großes O in einer mathematischen Perspektive, ich denke überhaupt nicht an großes O, es sei denn, ich werde gefragt. Ich sehe nur einen Algorithmus in meinem Kopf, und ich kann erkennen, 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 eine große O-Notation übersetzen, aber es fällt mir leichter, nur zu wissen, wie der Algorithmus/Container mit dem Speicher funktioniert, als über eine mathematische Perspektive nachzudenken.

0
Coder

Ja, Komplexität ist in der Branche wichtig. Wenn Sie am Ende etwas entwerfen, bei dem ein kritischer Pfad als N-Quadrat skaliert wird (durch Verdoppelung der Anzahl von etwas wird das System viermal so geladen), werden Sie Ihren Skalierungsengpass viel schneller treffen, als wenn Sie etwas haben, das bei N skaliert.

Es wird jedoch normalerweise nicht als richtiger, formaler Beweis dafür erbracht, dass sich etwas in einer bestimmten Komplexität befindet. Daher ist es ein guter Anfang, eine gute Vorstellung davon zu haben, welche Komplexität ein Operationsmuster aufweist.

0
Vatine