Ähnlich wie C++ - Zugriff durch Referenz?

Question

Ich baue einen Clustering-Algorithmus in C++, aber ich bin nicht gut mit OOP und den Status von Variablen (Member-Daten), die sich ändern. Für einen Algorithmus von einiger Komplexität finde ich das ein Hindernis für meine Entwicklung.

Also habe ich überlegt, die Programmiersprache in eine der funktionalen Sprachen zu ändern: Ocaml oder F #. Abgesehen davon, dass ich meine Einstellung zur Programmierung ändern muss, muss ich etwas klären. In C++ verwende ich eine Doppelend-Warteschlange, um ein Zeitfenster durch die Daten zu schieben. Nach einiger Zeit werden die ältesten Daten entfernt und neuere Daten angehängt. Daten, die noch nicht zu alt sind, verbleiben in der Doppelendeschlange.

Eine andere und anspruchsvollere Aufgabe besteht darin, die Eigenschaften eines jeden Objekts zu vergleichen. Jedes Objekt ist die Daten aus einer bestimmten Zeit. Und wenn ich in einem bestimmten Zeitfenster eintausend Datenobjekte habe, muss ich je nach Bedarf zwischen keinem oder zwanzig oder dreißig vergleichen. Und einige Eigenschaften des zu vergleichenden Objekts können sich als Ergebnis dieses Vergleichs ändern. In C++ benutze ich Referenzen, was bedeutet, dass ich auf Objekte im Speicher zugreife, dass sie niemals kopiert werden, daher läuft der Algorithmus mit voller Geschwindigkeit (für meine Kenntnisse von C++).

Ich habe über funktionale Programmierung gelesen, und die Idee, die ich bekomme, ist, dass jede Funktion einige Operationen ausführt und dass die ursprünglichen Daten (die Eingabe) nicht geändert wird. Dies bedeutet, dass die Sprache die Datenstruktur kopiert und die erforderliche Transformation durchführt. Wenn dies der Fall ist, verzögert die Verwendung der funktionalen Programmierung die Ausführung des Algorithmus sehr. Ist das richtig? Wenn nicht, d. H. Wenn es eine schnelle Möglichkeit gibt, eine Transformation in Daten durchzuführen, ist es möglich, mir zu zeigen, wie es geht? Ein sehr kleines Beispiel wäre großartig.

Ich hoffe, eine Art von Einrichtung zu haben. Ich habe gelesen, dass sowohl Ocaml als auch F # in Forschung und wissenschaftlichen Projekten verwendet werden.

Answer 1

Auf einer hohen Ebene ist Ihre Frage, ob die Verwendung von unveränderlichen Daten langsamer ist als die Verwendung von veränderbaren Daten. Die Antwort darauf ist ja, in manchen Fällen ist es langsamer. Was für mich überraschend ist, ist, wie klein die Strafe ist. In den meisten Fällen (meiner Erfahrung nach) ist die zusätzliche Zeit, die oft ein logarithmischer Faktor ist, die zusätzliche Modularität und Klarheit der Verwendung unveränderlicher Daten wert.Und in vielen anderen Fällen gibt es überhaupt keine Strafe.

Der Hauptgrund, dass es nicht so viel langsamer ist, als Sie erwarten würden, ist, dass Sie beliebige Teile der alten Daten frei wiederverwenden können. Sie müssen sich keine Sorgen machen, dass ein anderer Teil der Berechnung die Daten später ändert: Sie ist unveränderlich!

Aus einem ähnlichen Grund sind alle Zugriffe auf unveränderliche Daten wie Referenzen in C++. Es ist nicht notwendig, Kopien von Daten zu erstellen, da andere Teile der Berechnung es nicht ändern können.

Wenn Sie auf diese Weise arbeiten möchten, müssen Sie Ihre Daten strukturieren, um sie wiederverwenden zu können. Wenn Sie dies nicht leicht tun können, möchten Sie vielleicht eine (kontrollierte) Mutation verwenden.

Sowohl OCaml als auch F # sind gemischte Paradigmensprachen. Sie ermöglichen Ihnen, veränderbare Daten zu verwenden, wenn Sie möchten.

Die aufschlussreichste Beschreibung von Operationen mit unveränderlichen Daten (IMHO) ist Chris Okasakis Buch Purely Functional Data Structures. (Dieser Amazon-Link ist nur für Informationen, nicht unbedingt ein Vorschlag, um das Buch zu kaufen :-) Sie können auch viele dieser Informationen in Okasaki's Phd thesis finden.

Answer 2

Dies bedeutet, dass die Sprache kopiert die Strukturdaten und

Nicht unbedingt die erforderliche Transformation durchführt. Wenn die Objekte unveränderlich sind (wie sie für F # -Aufzeichnungstypen standardmäßig sind, in C++, wenn alle Datenelemente const ohne Verwendung von mutable sind), dann ist die Aufnahme eines Verweises in Ordnung.

Wenn dies der Fall ist, verzögert die Verwendung der funktionalen Programmierung die Ausführung des Algorithmus erheblich. Ist das richtig?

Auch mit dem oben genannten unterstützen funktionale Sprachen faule Operationen. In F # mit den richtigen Datenstrukturen/Methoden ist dies der Fall. Aber es kann auch eifrig sein.

Ein Beispiel (nicht schrecklich idiomatisch, aber ich versuche klar zu sein):

let Square (is : seq<'t>) = is |> Seq.map(fun n -> n*n) 

und dann in

let res = [1; 2; 3; 4] |> Square 

wird jede der Quadrate nicht berechnen, bis Sie die Werte von re lesen.

Answer 3

Sie können in OCaml und F # auf jeden Fall eine pointer machine implementieren. So können Sie direkte Referenzen speichern und aktualisieren. ZB

type 'a cell = { 
    data : 'a; 
    mutable lhs : 'a cell; 
    mutable rhs : 'a cell; 
} 

In OCaml wird dies als Zeiger auf eine Datenstruktur dargestellt werden, mit drei Worten: einen Zeiger auf eine Daten und zwei Zeiger die Geschwister-Knoten:

+--------+   +-------+  +-------+ 
    | cell |-------->| data |----->|  | 
    +--------+   |-------|  +-------+ 
        +---| lhs | 
        | |-------| 
        | | rhs |--+ 
        | +-------+ | 
        | +-------+ | +-------+ 
        +-->| data | --->| data | 
         |-------|  |-------| 
         | lhs |  | lhs | 
         |-------|  |-------| 
         | rhs |  | rhs | 
         +-------+  +-------+ 

So gibt ist hier nichts besonderes. Es ist das gleiche, da Sie zwischen persistenter und imperativer Implementierung in C++ wählen können. In C++ zahlen Sie jedoch in der Regel wegen der mangelnden Unterstützung einer Sprache höhere Kosten für die Persistenz. In OCaml gibt es einen generativen Garbage Collector mit sehr günstigen Zuteilungskosten und anderen Optimierungen.

Also, ja, Sie können Ihre Datenstruktur auf eine normale (imperative) Weise implementieren. Aber bevor Sie das tun, müssen Sie ziemlich sicher sein, dass Sie bereit sind, dafür zu bezahlen. Es ist viel einfacher, über den funktionalen Code nachzudenken als über den Imperativ. Dies ist der Hauptgrund, warum Leute FP-Paradigma wählen und verwenden.

Answer 4

Es ist wichtig, dies in Bezug auf zwei Faktoren zu verstehen: Mutation und Teilen. Sie sind (scheinen) auf den Mutationsaspekt konzentriert und scheinen das Teilen zu vernachlässigen.

Nehmen Sie die Standardliste - Anhängen '@'; kopiert es die linke arg und teilt die rechte

Also, ja, es ist wahr, dass Sie verlieren Effizienz durch Kopieren, aber sie entsprechend Verstärkung durch gemeinsame Nutzung. Und so, wenn Sie Ihre Datenstrukturen so gestalten, dass sie die gemeinsame Nutzung von teilen, profitieren Sie davon, was Sie verlieren, wenn Sie das Kopieren unwandelbar machen.

In den meisten Fällen passiert das einfach. Manchmal müssen Sie es jedoch optimieren.

gängiges Beispiel Einbeziehung Faulheit in Haskell:

ones = 1 : ones 

dies eine unendliche Liste von 1s [1,1,1,...] und die Umsetzung kann erwarten bezeichnet es zu einer Schleife (kreis Diagramm)

 +-----------+ 
    |   | 
    V   | 
+---------+  | 
|   |  | 
| 1 |-->---+ 
|   | 
+---------+ 

optimieren

Wenn wir es jedoch zu einer unendlichen Liste von x-es verallgemeinern

repeat x = x : repeat x 

die Implementierung hat eine härtere Zeit die Schleife Erfassen weil die variable ones jetzt repeat x

Ändern es

repeat x = let repeat_x = x : repeat_x in repeat_x 

und die Schleife (dh sharing) a (rekursiv) Funktionsaufruf geworden ist wieder eingesetzt.