Wann ist 'Code optimieren' == 'Daten strukturieren'?

Ein kürzlich veröffentlichter Artikel von ycombinator listet einen Kommentar mit den Prinzipien eines großartigen Programmierers auf.

#7. Guter Programmierer: Ich optimiere Code. Besserer Programmierer: Ich strukturiere Daten. Bester Programmierer: Was ist der Unterschied?

Subjektive und umstrittene Konzepte anerkennen - hat jemand eine Position dazu, was dies bedeutet? Das tue ich, aber ich möchte diese Frage später mit meinen Gedanken bearbeiten, um die Antworten nicht zu prädisponieren.

In neun von zehn Fällen wird die Optimierung offensichtlich, wenn Sie Ihren Code / Ihre Modelle gut strukturieren. Wie oft haben Sie ein Hornissennest gesehen und es als völlig suboptimal empfunden, wobei bei der Umstrukturierung viele Redundanzen äußerst offensichtlich wurden.

Ein Designer weiß, dass er Perfektion erreicht hat, nicht wenn nichts mehr hinzuzufügen ist, sondern wenn nichts mehr wegzunehmen ist. - Antoine de Saint-Exupéry

Ein gut strukturiertes System wird minimaler Natur sein und aufgrund seiner minimalen Natur wird es optimiert, da die geringe Menge direkt damit zusammenhängt, wie wenig es tut, um sein Ziel zu erreichen.

Bearbeiten: Um den Punkt zu erläutern, den andere davon entfernt haben, ist es auch völlig korrekt, die Aussage als Identifizierung der Beziehung zwischen Code und Daten zu betrachten. Diese Beziehung lautet also: Wenn Sie die Struktur Ihrer Daten ändern, müssen Sie Ihren Code ändern, um die geänderte Struktur zu berücksichtigen. Wenn Sie Ihren Code optimieren möchten, müssen Sie wahrscheinlich die Struktur Ihrer Daten ändern, damit Ihr Code die Daten optimaler verarbeiten kann.

Das heißt, es gibt eine völlig andere Möglichkeit, die hier ausgeschlossen wurde, und das wäre, dass dieser Kerl, der Beziehungen zu YCombinator hat, sich möglicherweise auf Code-AS-Daten in der LISP-Tradition der Homoikonizität bezieht. Es ist eine Strecke, dies als die Bedeutung in meinem Kopf zu vermuten, aber es ist YCombinator, also würde ich nicht ausschließen, dass das Zitat einfach sagt, dass LISPer die "besten Programmierer" sind.

Ich denke, der Autor deutet an, dass jede Umstrukturierung der Daten zu einer Umstrukturierung des Codes führt. Wenn Sie die Daten mit dem Ziel der Optimierung Ihres Systems umstrukturieren, müssen Sie daher auch Ihren Code optimieren. Dies führt zu der Meldung "Was ist der Unterschied?". Antwort.

Beachten Sie, dass ein "überaus ausgezeichneter Programmierer" möglicherweise auf "Was ist der Unterschied?" Antwortet. Es gibt noch einen Unterschied: Wenn Sie sich an die Optimierung für eine verbesserte Nutzung des CPU-Caches wagen, können Sie das Layout Ihrer Datenstrukturen beibehalten, aber die Reihenfolge ändern, in der Sie darauf zugreifen, kann viel bewirken Unterschied.

Betrachten Sie das offensichtlichste Beispiel dafür: "Die Suche nach Benutzerdaten ist zu langsam!"

Wenn Ihre Benutzerdaten nicht indiziert oder zumindest sortiert sind, führt eine Umstrukturierung Ihrer Daten schnell zu einer höheren Codeleistung. Wenn die Daten richtig strukturiert sind und Sie nur die Sammlung durchlaufen (anstatt die Indizes zu verwenden oder so etwas wie eine binäre Suche durchzuführen), führt das Ändern des Codes zu einer höheren Codeleistung.

Programmierer sind Problemlöser. Es ist zwar nützlich, zwischen Algorithmen und Datenstrukturen zu unterscheiden, sie können jedoch häufig nicht isoliert existieren. Die besten Programmierer wissen das und isolieren sich nicht unnötig.

Ich stimme der oben erwähnten Aussage nicht zu, zumindest ohne Erklärung. Ich sehe, dass Codierung die Aktivität ist, bei der einige Datenstrukturen verwendet werden. Datenstrukturen würden im Allgemeinen die Codierung beeinflussen. Meiner Meinung nach gibt es also einen Unterschied zwischen den beiden.

Ich denke, der Autor hätte den letzten Teil als "Bester Programmierer: Ich optimiere beide" schreiben sollen .

Es gibt ein großartiges Buch (zumindest in der Veröffentlichung) mit dem Titel: Algorithmen + Datenstrukturen = Programme .

Das Optimieren von Code kann die Geschwindigkeit manchmal um den Faktor zwei und gelegentlich um den Faktor zehn oder sogar zwanzig verbessern, aber das war es auch schon. Das mag sich nach viel anhören, und wenn 75% der Ausführungszeit eines Programms in einer Routine mit fünf Zeilen verbracht werden, deren Geschwindigkeit leicht verdoppelt werden kann, kann sich eine solche Optimierung durchaus lohnen. Andererseits kann die Auswahl von Datenstrukturen die Ausführungsgeschwindigkeit um viele Größenordnungen beeinflussen. Ein moderner hyperoptimierter Multithread-Prozessor, der superoptimierten Code zum Nachschlagen von Daten nach Schlüsseln in einer linear verknüpften Liste mit 10.000.000 Elementen im RAM ausführt, wäre langsamer als ein viel langsamerer Prozessor, der eine eher einfach codierte verschachtelte Hash-Tabelle ausführt. In der Tat, wenn man die Daten richtig angelegt hätte, sogar ein 1980er '

Allerdings erfordert das Entwerfen effizienter Datenstrukturen häufig komplexere Kompromisse als das Optimieren von Code. In vielen Fällen sind beispielsweise die Datenstrukturen, mit denen auf Daten am effizientesten zugegriffen werden kann, weniger effizient zu aktualisieren (manchmal um Größenordnungen) als diejenigen, die schnelle Aktualisierungen ermöglichen, und diejenigen, die die schnellsten Aktualisierungen ermöglichen, können den langsamsten Zugriff ermöglichen. Ferner können in vielen Fällen Datenstrukturen, die für große Datensätze optimal sind, mit kleinen vergleichsweise ineffizient sein. Ein guter Programmierer sollte sich bemühen, diese konkurrierenden Faktoren mit der Zeit des Programmierers in Einklang zu bringen, die für die Implementierung und Pflege verschiedener Datenstrukturen erforderlich ist, und in der Lage sein, ein angemessenes Gleichgewicht zwischen ihnen herzustellen.

Datenstrukturen bestimmen die Leistung in hohem Maße. Ich denke, wir können Probleme mit einer vorgefassten Vorstellung von der idealen Datenstruktur intensiv und lang betrachten und in diesem Kontext des Denkens sogar Beweise (oft durch Induktion) für die Optimalität erstellen. Wenn wir beispielsweise eine sortierte Liste in ein Array einfügen und beispielsweise die Kosten für das Einfügen eines Elements bewerten, müssen wir im Durchschnitt entscheiden, dass wir für jedes Einfügen die Hälfte des Arrays verschieben müssen. Für jede binäre Suche können wir in log n Schritten ein passendes Element finden (oder nicht).

Wenn wir alternativ unsere Entscheidung über die Datenstruktur verschieben ( vorzeitige Optimierung vermeiden ) und die eingehenden Daten und den Kontext untersuchen, in dem wir sie verwenden, wie groß sie sind, welche Latenzen auftreten und welche für Benutzer wichtig sind, wie viel Speicher wir haben würde mit Datendarstellungen verwenden, die wir kennen oder entwickeln können.

In einem Bereich wie Sortieren und Suchen gibt es viel zu wissen. Wirklich großartige Programmierer haben lange daran gearbeitet. Es ist nützlich, diese Probleme gut zu verstehen, und es ist eine großartige Sache, wenn Sie mehr Methoden kennen als nach Abschluss der Undergrad-Datenstrukturklasse. Binäre Bäume können eine überlegene Leistung für Einfügungen im Austausch für eine höhere Speichernutzung bieten. Hash-Tabellen bieten noch größere Verbesserungen, aber noch mehr Speicher. Ein Radixbaum und eine Radixsortierung können noch weitere Verbesserungen bringen.

Die kreative Strukturierung der Daten kann dazu beitragen, ein Problem neu zu definieren und neue Algorithmen zu öffnen, die harte Anwendungen schneller und manchmal unmöglich machen.

Um meine beste Vermutung darüber zu formulieren, was der Artikel bedeutet, gehe ich von einem unausgesprochenen Untertext aus (der im Artikel zu fehlen scheint), den jeder Programmierer über Optimierung verstehen sollte:

• Die Optimierung erfolgt erst, nachdem Sie das Programm ordnungsgemäß eingerichtet und ausgeführt haben:
  • Lass es richtig laufen, dann lass es schnell laufen
  • Dieses Prinzip ist der Punkt von Knuths Maxime: "Vorzeitige Optimierung ist die Wurzel allen Übels."
• Wenn Sie festgestellt haben, dass die Optimierung nicht verfrüht ist, müssen Sie sie zuerst richtig messen, um festzustellen, was tatsächlich optimiert werden muss, und während der Optimierung immer wieder feststellen, welche Auswirkungen Ihre Optimierungsversuche haben.
  • Wenn Ihr Code in der Entwicklung ausgeführt wird, ist der Profiler Ihr Freund.
  • Wenn Ihr Code in der Produktion ausgeführt wird, müssen Sie Ihren Code instrumentieren und sich stattdessen mit Ihrem Protokollierungssystem anfreunden.

Nun, dann: Ihre Messungen zeigen Ihnen, wo in Ihrem Code die Maschine die meisten Zyklen brennt. Ein "guter" Programmierer wird sich darauf konzentrieren, diese Teile des Codes zu optimieren, anstatt Zeit damit zu verschwenden, die irrelevanten Teile zu optimieren.

Sie können jedoch häufig größere Gewinne erzielen, indem Sie das System als Ganzes betrachten und einen Weg finden, der Maschine weniger Arbeit zu ermöglichen. Häufig erfordern diese Änderungen eine Überarbeitung der Organisation Ihrer Daten. Daher wird ein "besserer" Programmierer häufig Daten strukturieren.

Der "beste Programmierer" verfügt über ein gründliches mentales Modell der Funktionsweise der Maschine, eine gute Grundlage im Algorithmus-Design und ein praktisches Verständnis ihrer Interaktion. Dies ermöglicht es ihm, das System als integriertes Ganzes zu betrachten - er wird keinen Unterschied zwischen der Optimierung des Codes und der Daten sehen, da er sie auf architektonischer Ebene bewertet.

Bester Programmierer: Was ist der Unterschied?

Bester Programmierer? Mieser Programmierer. Ich gehe davon aus, dass das Wort "Optimierung" die Dinge bedeutet, die Programmierer normalerweise zu optimieren versuchen, Speicher oder CPU-Zeit. In diesem Sinne widerspricht die Optimierung fast jeder anderen Software-Metrik. Verständlichkeit, Wartbarkeit, Testbarkeit usw.: Diese sind alle kurz, wenn Optimierung das Ziel ist - es sei denn, man versucht, die menschliche Verständlichkeit, Wartbarkeit, Testbarkeit usw. zu optimieren. Ganz zu schweigen von den Kosten. Das Schreiben eines optimalen Geschwindigkeits- / Raumalgorithmus kostet erheblich mehr Entwicklerzeit als das naive Codieren des Algorithmus, wie er in einem Text oder einer Zeitschrift dargestellt wird. Ein mieser Programmierer kennt den Unterschied nicht. Ein guter tut es. Der beste Programmierer weiß genau, was optimiert werden muss, und tut dies mit Bedacht.