O-Notation im Software-Design

Beim Umgang mit SOLID bin ich oft auf die Tatsache gestoßen, dass die Nichtbeachtung dieser Grundsätze zu Problemen führen kann. Probleme sind bekannt, aber schlecht formalisiert. Dieser Artikel wurde mit dem Ziel verfasst, typische Situationen zu formalisieren, die beim Schreiben von Code auftreten, mögliche Lösungen und die daraus resultierenden Konsequenzen. Wir werden darüber sprechen, warum wir mit schlechtem Code konfrontiert sind und wie Probleme mit dem Wachstum des Programms wachsen. Leider läuft die Bewertung in den meisten Fällen auf die Optionen „viele“ und „eins“ hinaus, die auf die Insolvenz der O-Notation hinweisen, aber selbst eine solche Analyse wird es ermöglichen, besser zu verstehen, welcher Code für die weitere Entwicklung des Systems wirklich gefährlich und welcher Code tolerant ist.

Definition


Wir sagen, dass eine Änderung im Programm "O" von f (n) Aktionen erfordert, wenn der Programmierer nicht mehr als f (n) logisch getrennte Änderungen im Programm vornehmen muss, um die Änderung auf einen konstanten Faktor genau umzusetzen, wobei n die Größe des Programms bedeutet.

Metriken


Betrachten Sie einige der Designmerkmale von Robert Martin und bewerten Sie sie anhand der O-Notation.
Ein Design ist schwierig, wenn eine einzelne Änderung eine Kaskade anderer Änderungen in den abhängigen Modulen verursacht. Je mehr Module Sie wechseln müssen, desto steifer ist das Design.
Der signifikante Unterschied besteht in den Änderungen von O (1) und O (n). Das heißt, Unser Design ermöglicht eine konstante Anzahl von Änderungen, oder wenn das Programm wächst, nimmt die Anzahl der Änderungen zu. Als nächstes sollten wir die Änderungen selbst betrachten - auch sie können sich mit einem gewissen asymptotischen Verhalten als starr herausstellen. Somit kann die Steifheit bis zu O (nm) komplex sein. Der Parameter m wird als Steifheitstiefe bezeichnet. Selbst eine grobe Schätzung der Steifheitstiefe in einer Konstruktion, die sogar die Steifheit O (n) zulässt, ist für eine Person zu kompliziert, da jede Änderung auf noch tiefere Änderungen überprüft werden muss.
Fragilität ist die Eigenschaft eines Programms, an vielen Stellen beschädigt zu werden, wenn eine einzelne Änderung vorgenommen wird. Oft treten neue Probleme in Teilen auf, die keinen konzeptionellen Zusammenhang mit dem geänderten haben.
Wir werden die Frage der logischen Verbindung der Module, in denen Änderungen auftreten, nicht berücksichtigen. Aus Sicht der Notation gibt es daher keinen Unterschied zwischen Fragilität und Steifheit, und die für die Steifheit gültigen Argumente gelten für die Fragilität.
Ein Entwurf ist inert, wenn er Teile enthält, die in anderen Systemen nützlich sein könnten, aber der Aufwand und die Risiken, die mit dem Versuch verbunden sind, diese Teile vom ursprünglichen System zu trennen, sind zu groß.
Die Risiken und Anstrengungen in dieser Definition können als die Anzahl der Änderungen interpretiert werden, die im Modul auftreten, wenn versucht wird, es vom ursprünglichen System zu abstrahieren, das mit zunehmender Größe des Moduls nicht konstant ist. Wie die Praxis zeigt, lohnt es sich jedoch immer noch, sie zu abstrahieren, da dies Ordnung in das Modul selbst bringt und es ermöglicht, es auf andere Projekte zu übertragen. Sehr oft erscheinen nach dem ersten Übertragen des Moduls auf ein anderes Projekt andere ähnliche.

Viskosität
Angesichts der Notwendigkeit, Änderungen vorzunehmen, findet der Entwickler normalerweise mehrere Möglichkeiten, dies zu tun. Einige bewahren das Design, andere nicht (das heißt, sie sind im Wesentlichen ein „Hack“). Wenn designerhaltende Ansätze schwieriger zu implementieren sind als ein Hack, ist die Viskosität des Designs hoch. Das Problem zu lösen ist einfach falsch, aber richtig ist schwierig. Wir möchten unsere Programme so gestalten, dass es einfach ist, Änderungen vorzunehmen, die das Design bewahren.
Die folgende Viskosität kann als Kurzsichtigkeit in Bezug auf die O-Notation bezeichnet werden. Ja, zuerst hat der Entwickler wirklich die Möglichkeit, eine Änderung von O (1) anstelle von O (n) vorzunehmen (aufgrund von Steifheit oder Zerbrechlichkeit), aber häufig führen solche Änderungen zu noch mehr Steifheit und Zerbrechlichkeit, d. H. Erhöhen Sie die Steifigkeitstiefe. Wenn Sie eine solche „Glocke“ ignorieren, können nachfolgende Änderungen möglicherweise nicht mehr mit einem „Hack“ gelöst werden, und Sie müssen Änderungen in Bezug auf die Steifheit vornehmen (möglicherweise mehr als vor der „Glocke“) oder das System in einen guten Zustand bringen. Das heißt, wenn die Viskosität erkannt wird, ist es besser, das System sofort richtig umzuschreiben.
Es passiert so: Ivan muss einen Code schreiben, der seinen kleinen Fuß kräuselt. Er klettert zu verschiedenen Teilen des Programms, wo, wie er vermutet, die Bokryade mehr als einmal geraucht wurde, und findet ein geeignetes Fragment. Es kopiert es, fügt es in sein Modul ein und nimmt die erforderlichen Änderungen vor.

Aber Ivan weiß nicht, dass der Code, den er mit der Maus extrahiert hat, Peter dort platziert hat und ihn aus dem von Sveta geschriebenen Modul entnommen hat. Sveta war die erste, die ein wenig Bordstein rauchte, aber sie wusste, dass dieser Prozess dem Rauchen von Murmeltieren sehr ähnlich war. Sie fand irgendwo einen Code, den Karmyachit Karmaglot, kopierte ihn in ihr Modul und modifizierte ihn. Wenn derselbe Code immer wieder in leicht unterschiedlichen Formen erscheint, verlieren Entwickler die Idee der Abstraktion.
In dieser Situation wird deutlich, dass diese Änderung an n Stellen vorgenommen werden sollte, wenn die Grundlage der ausgegrabenen Aktion geändert werden muss. Angesichts der Möglichkeit eindeutiger Änderungen in jedem Kopier- und Einfügebereich kann dies auch zu logisch nicht zusammenhängenden Änderungen führen. In diesem Fall besteht die Möglichkeit, die Änderung an einem anderen Ort einfach zu vergessen, da in der Kompilierungsphase kein Schutz besteht. Dies kann also auch zu O (n) -Testiterationen führen.

Anwendung Über SOLID Notation


SRP (Single Responsibility Principle). Eine Softwareeinheit sollte nur einen Grund für eine Änderung haben (Verantwortung). Mit anderen Worten, zum Beispiel sollte die Klasse nicht der Geschäftslogik und Zuordnung folgen, weil Wenn wir eine Haftung ändern, müssen wir sicherstellen, dass wir keine andere Verantwortung beschädigt haben. Das heißt, die Inkonsistenz mit dem SRP-Prinzip führt zu Steifheit und Zerbrechlichkeit. Das Befolgen dieses Prinzips hilft auch dabei, die Trägheit zu beseitigen und Module mit einer möglicherweise geringeren Anzahl von Abhängigkeiten von einem Programm in ein anderes zu übertragen.

Das asymptotische Verhalten der Veränderungen bleibt grundsätzlich das gleiche wie ohne das Prinzip zu befolgen, aber der konstante Faktor nimmt signifikant ab. In beiden Fällen sollten wir den gesamten Inhalt der Klasse und im Falle einer Änderung der Schnittstelle der Entität die Stellen überprüfen, an denen sie mit dieser Entität interagieren. Nur das Befolgen von SRP trägt dazu bei, die Schnittstelle und die Wahrscheinlichkeit ihrer Änderung sowie den Umfang der internen Implementierung zu verringern, die sich nach der Änderung als fehlerhaft herausstellen kann. Eine ähnliche Argumentation, die auf die Diskussion von Schnittstellen abgeschnitten ist, gilt für ISP (Interface Segregation Principle).

OCP (Open Close-Prinzip). Software-Entitäten (Klassen, Module, Funktionen usw.) müssen zur Erweiterung geöffnet und zur Änderung geschlossen sein. Dies sollte so verstanden werden, dass wir das Verhalten des Moduls ändern können, ohne dessen Quellcode zu beeinflussen. Typischerweise wird dies durch Vererbung und Polymorphismus erreicht. Da eine Verletzung des LSP-Prinzips eine Verletzung von OCP darstellt und DIP ein Mittel zur Aufrechterhaltung von OCP ist, kann das Folgende sowohl auf LSP als auch auf DIP angewendet werden. Die Nichteinhaltung des Grundsatzes der Offenheit und Nähe zwingt dazu, Änderungen in allen Einheiten vorzunehmen, die in Bezug auf diese Änderung nicht geschlossen sind.

Eine ziemlich triviale Situation ist zum Beispiel das Vorhandensein einer Kette von Wenns, die den Variablentyp in der Liste der untergeordneten Klassen bestimmen. Solche Strukturen können mehrmals im Programm erscheinen. Und wenn Sie eine neue untergeordnete Klasse hinzufügen, sollten Sie in jeder dieser Ketten die entsprechenden Änderungen vornehmen. Ähnliche Situationen können nicht nur bei Kinderklassen auftreten, sondern auch bei der Berücksichtigung nicht aller möglichen Sonderfälle [Dies bezieht sich auf Fälle, die nicht zum Zeitpunkt des Schreibens, sondern allgemein vorliegen. Fälle können später erscheinen].

Betrachten Sie nun die Situation, in der wir m Änderungen des gleichen Typs vornehmen, die aufgrund der Diskrepanz mit dem Prinzip der Offenheit-Nähe n Operationen von uns erfordern. Wenn wir dann alles so lassen, wie es ist, die Architektur für die Berücksichtigung von Sonderfällen unterstützen und nicht verallgemeinern, erhalten wir die Gesamtkomplexität für alle Änderungen O (mn). Wenn wir alle m Stellen in Bezug auf diese Änderung schließen, nehmen nachfolgende Änderungen O (1) anstelle von O (m) an. Somit wird die Gesamtkomplexität auf O (m + n) reduziert. Dies bedeutet, dass das Starten einer OCP nie zu spät ist.

Martin sagt über diese Situation, dass Sie nicht raten sollten (wenn Sie natürlich nicht genau wissen), wie Sie nach der ersten Änderung schließen sollen, aber nach der ersten Änderung lohnt es sich, sie zu schließen, da die erste Änderung ein Zeichen dafür war, dass das System nicht unbedingt im aktuellen Zustand bleiben wird. Dies ist logisch, da wir O (1 * n) -Aktionen aufgrund von Nicht-Nähe ausführen und dann O (m) -Aktionen, um uns vor nachfolgenden Änderungen zu schützen. Insgesamt erhalten wir die Gesamtkomplexität O (n + m), aber gleichzeitig führen wir alle Aktionen genau dann aus, wenn sie notwendig werden, und tun nichts im Voraus, ohne zu wissen, ob sie benötigt werden.

Muster und O-Notation


Eine weitere Analogie kann zwischen der O-Notation in der Computertheorie und der O-Notation im Design gezogen werden. Es besteht in der Tatsache, dass wir die Anzahl der Berechnungen mithilfe von Algorithmen und Datenstrukturen wie Suchbäumen und Haufen reduzieren, die typische Probleme schneller lösen als "frontale" Lösungen, und die Anzahl der Operationen eines Programmierers mit einem guten Design, in dem er auch gute typische Lösungen verwenden kann Designmuster genannt. Sie können die Wirkung von Mustern im Kontext der Prinzipien von SOLID und damit im Kontext der O-Notation bewerten.

Beispielsweise verhindert die Mediator-Vorlage die Möglichkeit, beim Ändern der Interaktionslogik zwischen zwei Objekten etwas im Programm zu beschädigen, da sie diese vollständig kapselt und die konstante Komplexität einer solchen Änderung garantiert.

Mit der Adaptervorlage können wir Entitäten mit verschiedenen Schnittstellen verwenden (lesen, hinzufügen), die wir für einen gemeinsamen Zweck verwenden. Mit dieser Vorlage können Sie ein neues Objekt mit einer inkompatiblen Schnittstelle für die Anzahl der Vorgänge in das System einbetten, die nicht von der Größe des Systems abhängt.

Da Datenstrukturen einige Operationen mit guter Asymptotik und einige mit schlechten unterstützen können, verhalten sich Muster in Bezug auf einige Änderungen flexibel und in Bezug auf andere starr.

Angemessene Grenzen


Wenn wir uns mit der O-Notation befassen und an einem Optimierungsproblem arbeiten, müssen wir uns daran erinnern, dass nicht immer der Algorithmus mit der besten Asymptotik am besten zur Lösung des Problems geeignet ist. Es versteht sich, dass das Sortieren nach einer Blase für eine Anordnung von 3 Elementen schneller als das Pyramidensortieren funktioniert, obwohl das Pyramidensortieren eine bessere Asymptotik aufweist. Für kleine Werte von n spielt ein konstanter Faktor eine wichtige Rolle, die die O-Notation verbirgt. Die O-Notation im Design funktioniert genauso. Bei kleinen Projekten ist es nicht sinnvoll, viele Vorlagen einzäunen, da die Kosten für deren Implementierung die Anzahl der Änderungen übersteigen, die aufgrund eines „schlechten Designs“ vorgenommen werden sollten.

Source: https://habr.com/ru/post/de428928/


All Articles