Beziehung zwischen Objektorientierung und Algorithmen

Während ich einige Algorithmenlehrbücher lese, sind sie voller cleverer Verfahren für einige Probleme (Sortieren, kürzester Weg) oder einige allgemeine Methoden (rekursive Algorithmen, Teilen und Erobern, dynamische Programmierung ...). Ich habe dort nur wenige Spuren objektorientierter Programmierung gefunden; (Warum sind sie eher prozessorientiert?).

Dann dachte ich:

• Welche Beziehung besteht zwischen Algorithmen und OOP? Sind das zwei unabhängige Themen?
• Gibt es einige Probleme, die nur von OOP dargestellt und gelöst werden können?
• Wie kann OOP Algorithmen helfen? Oder in welche Richtung kann es sich auswirken?

Definieren wir zunächst, was wir unter OOP verstehen. Mit OOP meine ich hauptsächlich:

• Kapselung und Verstecken von Details im Unterricht.
• Polymorphismus des Verhaltens durch Vererbung und virtuelle Methoden.

Um Ihre Frage zu beantworten:

Welche Beziehung besteht zwischen Algorithmen und OOP? Sind das zwei unabhängige Themen?

Ja.

Gibt es einige Probleme, die nur von OOP dargestellt und gelöst werden können?

Nein. OOP Primary bietet dem Programmierer Komfort und die Möglichkeit, über Code nachzudenken. Es erhöht nicht Ihre Ausdruckskraft.

Wie kann OOP Algorithmen helfen? Oder in welche Richtung kann es sich auswirken?

Wie ich oben sagte. Beide Punkte, die ich OOP beschrieben habe, gelten hier. In der Lage zu sein, Details von Algorithmen und deren Datenstrukturen zu verbergen, kann helfen, über das Ganze nachzudenken. Viele Algorithmen enthalten Details, mit denen der Benutzer dieses Algorithmus nicht herumspielen soll. Das Ausblenden dieser Details hilft sehr.

Die Fähigkeit zu polymorphem Verhalten ist ebenfalls großartig. Listist definiert als das Hinzufügen / Entfernen / Löschen von Elementen an einer beliebigen Stelle in der Sammlung. Es kann jedoch als anpassbares Array, doppelt verknüpft oder einfach verknüpft usw. implementiert werden. Eine einzige API für mehrere Implementierungen kann zur Wiederverwendung beitragen.

Warum sind Algorithmen Lehrbücher eher prozedurorientiert?

Wie gesagt, OOP ist nicht erforderlich, um einen Algorithmus zu implementieren. Außerdem sind viele Algorithmen alt und wurden erstellt, als OOP noch nicht weit verbreitet war. Es könnte also auch eine historische Sache sein.

Algorithmen und OOP sind zwei unterschiedliche Begriffe, die nur gemeinsam haben, dass sie CS- Terme sind. Einfach - Ein Algorithmus ist wie ein Kochrezept : Um x zu machen , benötigen Sie die folgenden Zutaten und führen die Schritte 1,2,3,4,5,6 aus ... dann haben Sie Ihre Mahlzeit zubereitet.

Das heißt, es scheint eine natürliche Passform für Algortihm zu sein, prozedural beschrieben zu werden. Procedural bedeutet nichts anderes als: zuerst tun x und tun dann y .

Ein häufiges Problem ist: »Wie sortiere ich eine Menge von x ?«. Eine leicht verständliche Lösung ist bubble-sort:

1. Iterieren Sie vom letzten Element über die Menge, solange Sie das erste Element nicht erreicht haben und während Sie iterieren
2. Starten Sie eine zweite Iteration vom Anfang bis zum aktuellen Element der ersten Iteration und
3. Vergleichen Sie das aktuelle Element von (2) mit seinem Nachfolger
4. Wenn größer, tauschen Sie die Positionen

Das ist die algorithmische / verbale Beschreibung des bubblesortAlgorithmus.

Hier kommt eine prozedurale / Pseudocode-Implementierung

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

Das war einfach.

Wie kommt das zu OOP ? Sie können diesen verwenden Algorithmus zur Behandlung von Sammlungen (ein Objekt selbst) von Objekten :

Beispiel in Javascript (obwohl kein sauberer OO-Lingo , aber mit fast keinem Boilerplate und leicht zu verstehen)

objects =[{"name":"Peter"}, {"name":"Paul"}, {"name":"Mary"}]

compareObjects=function(x,y){ return x.name>y.name };

sorted = objects.sort(compareObjects)

console.log(sorted)

Wir haben a) eine Sammlung objects, b) eine dieser Sammlung gemeinsame Methode, sortdie den Sortieralgorithmus enthält / abstrahiert, und c) unsere Objekte Peter , Paul und Mary . Die Spezifikation für die Sortierung finden Sie hier .

Welche Beziehung besteht zwischen Algorithmen und OOP? Sind das zwei unabhängige Themen?

Aus dem Gesagten sollte klar sein, die Antwort sollte lauten: Ja, sie sind unabhängig.

Wie kann OOP Algorithmen helfen? Oder in welche Richtung kann es sich auswirken?

OOP ist nur ein Programmierstil. Es kann in keiner Weise helfen . Andernfalls könnte ein Algorithmus in einer OO-Sprache implementiert werden, um etwas mit Objekten zu tun (wie gezeigt).

Gibt es einige Probleme, die nur von OOP dargestellt und gelöst werden können?

Ich kann mir keinen vorstellen (aber das heißt nicht, dass es unmöglich ist). Aber wenn Sie es anders herum betrachten: OOP ist nützlich, wenn Sie einige Probleme modellieren und mit einem geeigneten Algorithmus lösen möchten. Sagen Sie eine Aufzeichnung haben friendsSie konnten sie als Modell objectsmit propertiesund wenn Sie ein möchten listvon friends sortiert in irgendeiner Weise können Sie das Beispiel-Code angegeben verwenden oben genau das zu tun.

Warum sind Algorithmen Lehrbücher eher prozedurorientiert?

Wie gesagt: Es ist natürlicher , da prozedural der Charakter von Algorithmen ist.

du hast ein Problem.

Das Geschäftsdomänenmodell beschreibt Ihr Problem und die Konzepte aus der Problemdomäne, mit der Sie sich befassen werden.

Algorithmen beschreiben die Art und Weise, wie Sie Ihre Probleme konzeptionell lösen werden. Wie wird Ihre Implementierung aussehen? und wie gehen Sie mit Ihrem Problem um, nachdem Sie es in "Informatik" übersetzt haben.

Das Programmierparadigma, ob OOP, funktional, logisch, prozedural oder sogar nicht strukturiert, beschreibt, wie Sie Ihre Lösung strukturieren, welche Form sie annehmen wird, welche "Software Engineering" -Konzepte Sie verwenden und welche " Programmiersprachentheorie "Konzepte, die Sie verwenden werden.

Einfacher ausgedrückt beschreiben Algorithmen im Allgemeinen Ihre Lösung des Problems ("Dies ist, was ich tun werde"). Während sich das Programmierparadigma mit Ihrer tatsächlichen Implementierung befasst ("So werde ich es machen").

Algorithmen = erzählen die " Wie " -Geschichte (dh wie man Eingabedaten mithilfe von Datenstrukturen rechtzeitig manipuliert, um die gewünschten Ergebnisse zu erzielen)

OOP = eine " Methodik ", die durch OO-Sprachen das Schreiben von Programmen (= Algorithmen + Datenstrukturen) erleichtert, die Ihnen Speichersicherheit und Abstraktion bieten

OOP ist nur ein Paradigma für die Implementierung von Algorithmen.

Gute Analogie : Filme

Sie können Szenen aufnehmen, indem Sie einen Stuntman beschäftigen oder nicht. Drehbuch (Algorithmus) ändert sich nicht. Die Leute sollten keinen Unterschied im Endergebnis sehen.

BEARBEITEN: Sie könnten ein MOOC von guter Qualität ausprobieren: https://www.coursera.org/course/algs4partI, das die besprochenen Themen (insbesondere den OOP-Ansatz) verschachtelt und die Essenz Ihrer Fragen hier wiedergibt.

Alexander Stepanov ist der ursprüngliche Schöpfer der C ++ Standard Template Library (STL), der grundlegenden Algorithmusbibliothek für C ++. C ++ ist eine Multi-Paradigmen-Sprache, die "objektorientierte" Funktionen enthält, aber Alexander Stepanov hat Folgendes zur Objektorientierung zu sagen:

http://www.stlport.org/resources/StepanovUSA.html

STL ist nicht objektorientiert. Ich denke, dass Objektorientierung fast genauso ein Scherz ist wie künstliche Intelligenz. Ich habe noch keinen interessanten Code gesehen, der von diesen OO-Leuten stammt.

Ich finde OOP technisch nicht gesund. Es wird versucht, die Welt in Schnittstellen zu zerlegen, die von Typ zu Typ unterschiedlich sind. Um die wirklichen Probleme zu lösen, benötigen Sie multisortierte Algebren - Familien von Schnittstellen, die mehrere Typen umfassen. Ich finde OOP philosophisch nicht gesund. Es wird behauptet, dass alles ein Objekt ist. Auch wenn es wahr ist, ist es nicht sehr interessant - zu sagen, dass alles ein Objekt ist, sagt überhaupt nichts. Ich finde OOP methodisch falsch. Es beginnt mit dem Unterricht. Es ist, als würden Mathematiker mit Axiomen beginnen. Sie beginnen nicht mit Axiomen - Sie beginnen mit Beweisen. Nur wenn Sie eine Reihe verwandter Beweise gefunden haben, können Sie Axiome finden. Sie enden mit Axiomen. Das Gleiche gilt für die Programmierung: Sie müssen mit interessanten Algorithmen beginnen. Nur wenn du sie gut verstehst,

Ich habe jahrelang versucht, eine Verwendung für Vererbung und Virtuals zu finden, bevor ich verstanden habe, warum dieser Mechanismus grundlegend fehlerhaft war und nicht verwendet werden sollte.

Stepanov drückte seine Algorithmusbibliothek nicht mit Objekten aus, sondern mit generischen Iteratoren .

Algorithmen beschreiben, was der Computer tun soll. Die Struktur beschreibt, wie der Algorithmus [im Quellcode] aufgebaut ist. OOP ist ein Programmierstil, der bestimmte "objektorientierte" Strukturen nutzt.

Algorithmusbücher meiden häufig OOP, weil sie sich auf Algorithmen und nicht auf Strukturen konzentrieren. Codefragmente, die stark von der Struktur abhängen, sind in der Regel schlechte Beispiele für ein Algorithmusbuch. Ebenso meiden OOP-Bücher häufig Algorithmen, weil sie die Geschichte durcheinander bringen. Das Verkaufsargument von OOP ist seine Fluidität, und wenn es an einen Algorithmus gebunden wird, erscheint es starrer. Es geht mehr um den Fokus des Buches als um alles andere.

Im realen Code verwenden Sie beide nebeneinander. Sie können Computerprobleme per Definition nicht ohne Algorithmen lösen, und es fällt Ihnen schwer, gute Algorithmen ohne Struktur (OOP oder auf andere Weise) zu schreiben.

Nehmen Sie als Beispiel für die Unschärfe die dynamische Programmierung. In einem Algorithmusbuch würden Sie beschreiben, wie Sie einen homogenen Datensatz in ein Array aufnehmen und mithilfe der dynamischen Programmierung zu einer Lösung gelangen. In einem OOP-Buch stoßen Sie möglicherweise auf eine Struktur wie Visitor, mit der Sie beliebige Algorithmen für eine Reihe heterogener Objekte ausführen können. Das DP-Buchbeispiel könnte als ein sehr einfacher Besucher betrachtet werden, der Objekte in einer allgemein von unten nach oben gerichteten Reihenfolge bearbeitet. Das Besuchermuster könnte als das Grundgerüst eines DP-Problems angesehen werden, aber es fehlen Fleisch und Kartoffeln. In der Realität werden Sie häufig beides zusammen benötigen: Sie verwenden das Besuchermuster, um mit der Heterogenität in Ihrem Datensatz umzugehen (DP ist schlecht), und Sie verwenden DP innerhalb der Struktur des Besuchers, um Ihren Algorithmus zu organisieren, um die Laufzeit zu minimieren (Besucher) tut es nicht

Wir sehen auch Algorithmen, die über Entwurfsmustern arbeiten. Es ist schwieriger, Beispiele auf kleinem Raum zu formulieren, aber sobald Sie eine Struktur haben, möchten Sie diese Struktur manipulieren und verwenden dafür Algorithmen.

Gibt es einige Probleme, die nur von OOP dargestellt und gelöst werden können?

Diese Frage ist schwieriger zu beantworten als Sie denken. Bei der ersten Bestellung gibt es keinen rechnerischen Grund, warum Sie OOP benötigen, um ein Problem zu lösen. Der einfache Beweis ist, dass jedes OOP-Programm bis zur Assemblierung kompiliert wird, was eindeutig keine OOP-Sprache ist.

Im größeren Schema der Dinge beginnt die Antwort jedoch, Ja zu sagen. Sie sind selten einfach durch Berechnungsmethoden eingeschränkt. Meistens spielen Dinge wie Geschäftsanforderungen und Entwicklerfähigkeiten eine Rolle. Viele Anwendungen könnten heute nicht ohne OOP geschrieben werden, nicht weil OOP irgendwie grundlegend für die Aufgabe ist, sondern weil die von OOP bereitgestellte Struktur wesentlich war, um das Projekt auf Kurs und im Budget zu halten.

Dies bedeutet nicht, dass wir OOP in Zukunft niemals für eine lustige neue Struktur aufgeben werden. Es heißt lediglich, dass es eines der effektivsten Werkzeuge in unserer Toolbox für einen überraschend großen Teil der heutigen Programmieraufgaben ist. Zukünftige Probleme können dazu führen, dass wir uns der Entwicklung mit unterschiedlichen Strukturen nähern. Zum einen erwarte ich, dass neuronale Netze einen ganz anderen Entwicklungsansatz erfordern, der sich als "objektorientiert" herausstellen kann oder nicht.

Ich sehe nicht, dass OOP in naher Zukunft aufgrund der Denkweise von Algorithmus-Designern verschwindet. Bisher ist das übliche Muster, dass jemand einen Algorithmus entwirft, der OOP nicht nutzt. Die OOP-Community erkennt, dass der Algorithmus nicht wirklich zur OOP-Struktur passt und dies auch nicht muss. Daher packen sie den gesamten Algorithmus in eine OOP-Struktur und beginnen mit der Verwendung. Überlegen Sie boost::shared_ptr. Die darin enthaltenen Referenzzählalgorithmen shared_ptrsind nicht sehr OOP-freundlich. Das Muster wurde jedoch erst populär shared_ptr, als ein OOP-Wrapper erstellt wurde, der die Funktionen der Algorithmen in einem strukturierten OOP-Format enthüllte. Jetzt ist es so beliebt, dass es in die neueste Spezifikation für C ++, C ++ 11 aufgenommen wurde.

Warum ist das so erfolgreich? Algorithmen eignen sich hervorragend zum Lösen von Problemen, erfordern jedoch häufig erhebliche anfängliche Forschungsinvestitionen, um zu verstehen, wie sie verwendet werden. Die objektorientierte Entwicklung ist sehr effektiv, um solche Algorithmen zu verpacken und eine Schnittstelle bereitzustellen, deren Erlernen weniger Anfangsinvestitionen erfordert.

Zusätzlich zu den großartigen Antworten werde ich eine zusätzliche konzeptionelle Gemeinsamkeit zwischen OOP und Algorithmen erwähnen .

Sowohl OOP als auch Algorithmen legen großen Wert auf die Verwendung von Vor- und Nachbedingungen , um die Richtigkeit des Codes sicherzustellen.

Im Allgemeinen ist dies in allen Bereichen der Informatik Standard. Dieses Leitprinzip führt jedoch zu einem Evolutionspfad in OOP, der es für beide Seiten vorteilhaft macht, Algorithmen in OOP-Umgebungen zu implementieren.

In OOP kann eine Gruppe von Objekten, die denselben Vertrag erfüllen können (Vor- und Nachbedingungen), zum Implementieren einer Schnittstelle erstellt werden. Der Benutzer einer solchen Schnittstelle muss nicht wissen, welche Implementierung im zugrunde liegenden Objekt verwendet wird, außer in einigen seltenen Situationen (in denen eine undichte Abstraktion auftritt).

Ein Algorithmus ist eine Implementierung von Schritten, die zur Durchführung einer Berechnung verwendet werden und die die Vorbedingung übernehmen und die Nachbedingung erzeugen.

Daher kann man die Idee der Abstraktion in Form von Vor- und Nachbedingungen ausleihen und auf Algorithmen anwenden. Sie werden feststellen, dass manchmal komplizierte Algorithmen in kleinere Schritte zerlegt werden können und diese kleineren Schritte unterschiedliche Implementierungsstrategien ermöglichen können, solange dieselben Vor- und Nachbedingungen erfüllt sind.

Durch die Implementierung von Algorithmen in OOP können diese kleineren Schritte austauschbar gemacht werden.

Beachten Sie schließlich, dass sich FP und OOP nicht gegenseitig ausschließen. Alles, was oben beschrieben wurde, kann auch auf FP angewendet werden.

What is the relation between algorithms and OOP? Are they two independent topics?

Bei Algorithmen geht es darum, wie ein Problem gelöst werden kann (wie aus der gegebenen Eingabe eine Ausgabe generiert wird). Bei OOP geht es darum, wie unsere Lösung formuliert oder ausgedrückt wird (die Schritte des Algorithmus).

Ein Algorithmus kann in natürlicher Sprache oder in Assemblersprache beschrieben werden, aber die Konzepte, die wir in einer natürlichen Sprache haben, helfen uns, ihn besser zu schreiben und zu verstehen. Zum Beispiel könnte der Algorithmus für die Blasensortierung sein:

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

Um die Details zu verbergen swapund sie mit der von Auns verwendeten OOP-Syntax und -Funktion in Beziehung zu setzen , bringt OO den Algorithmus näher an unsere natürliche Sprache und unser Verständnis heran.

Are there some problems which can only be presented and solved by OOP?

Nein, wenn Sie bedenken, dass ein Programm (oder Algorithmus) auf einem Computer in eine Reihe von Anweisungen übersetzt wird, die auf der CPU ( Turing Machine ) ausgeführt werden, und wenn wir diese Anweisungen als den ultimativen Algorithmus betrachten, der das Problem auf einem Computer löst , dann OOP kann nicht weiter machen. Es bringt es nur näher an das menschliche Verständnis und Denken heran. Auf diese Weise können Sie unsere Prozeduren und Datenstrukturen verpacken.

How OOP can help algorithms? Or in which direction it can affect it?

Es kann hilfreich sein, einen Algorithmus einfacher oder verständlicher anzugeben oder zu formulieren. Es kann Details verbergen und ein Gesamtbild der Lösung liefern.

Theoretisch ist der Algorithmus der erste und der zweite der zweite . In Wirklichkeit können wir jedoch nicht sicher sein, ob unser Algorithmus wie erwartet funktioniert, bis wir ihn verfolgen oder die erwartete Ausgabe generieren. Computer helfen uns dabei, aber Sie erwarten nicht, dass Sie es in Maschinensprache (Assembly) schreiben.

In dieser Hinsicht erleichtert OOP die Implementierung, den Test und die Verfeinerung unseres Algorithmus auf Computern und schreibt ihn für einen Computer in einer Sprache, die unserer natürlichen Sprache nahe kommt.