Was sind die Vorteile von Lazy Evaluation?

Question

Welche Vorteile hat Lazy Evaluation im Gegensatz zu Eager Evaluation?

Welchen Performance Overhead gibt es? Ist Lazy Evaluation langsamer oder schneller? Warum (oder hängt das von der Implementierung ab?)

Wie funktioniert Lazy Evaluation tatsächlich in den meisten Implementierungen arbeiten? Für mich scheint es viel langsamer und speicherintensiver zu sein, da Variablen sowohl Operationen als auch Zahlen speichern müssen. Wie funktioniert das in einer Sprache wie Haskell (ich kenne diese Sprache eigentlich nicht)? Wie ist die Faulheit implementiert und getan, so dass es nicht viel langsamer ist/mehr Platz verbraucht?

Answer 1

Dies bezieht sich auf die Auswertung eines Syntaxbaums. Wenn Sie einen Syntaxbaum träge auswerten (d. H. Wenn der Wert, den er repräsentiert, benötigt wird), müssen Sie ihn vollständig durch die vorhergehenden Schritte Ihrer Berechnung führen. Dies ist der Overhead der faulen Bewertung. Es gibt jedoch zwei Vorteile. 1) Sie werden den Baum nicht unnötigerweise auswerten, wenn das Ergebnis nie verwendet wird, und 2) Sie können einen unendlichen Syntaxbaum in einer rekursiven Form ausdrücken und verwenden, weil Sie ihn nur im Gegensatz zur Auswertung immer auf die erforderliche Tiefe auswerten werden (eifrig) in seiner Gesamtheit, was unmöglich wäre.

Ich weiß nicht haskel, aber so weit ich weiß Programmiersprachen wie Python oder ML begutachten. Um beispielsweise eine verzögerte Bewertung in ML zu simulieren, müssen Sie eine Dummy-Funktion erstellen, die keine Parameter akzeptiert, aber das Ergebnis zurückgibt. Diese Funktion ist dann Ihr Syntaxbaum, den Sie jederzeit bequem durch eine leere Argumentliste aufrufen können.

Answer 2

In Ruby verwenden wir Funktionsmodifikatoren, die normalerweise "einmal" genannt werden, um eine Methode so zu umschließen, dass sie eine faule Auswertung durchführt. Eine solche Methode wird nur einmal ausgewertet, der Wert zwischengespeichert, nachfolgende Aufrufe geben diesen Wert zurück.

Eine Verwendung (oder Missbrauch) der Lazy-Evaluierung besteht darin, die Reihenfolge der Objektinitialisierung implizit statt explizit zu machen. Vorher:

def initialize 
    setup_logging # Must come before setup_database 
    setup_database # Must come before get_addresses 
    setup_address_correction # Must come before get_addresses 
    get_addresses 
end 

def setup_logging 
    @log = Log.new 
end 

def setup_database 
    @db = Db.new(@log) 
end 

def setup_address_correction 
    @address_correction = AddressCorrection.new 
end 

def get_addresses 
    @log.puts ("Querying addresses") 
    @addresses = @address_correction.correct(query_addresses(@db)) 
end 

Mit lazy evaluation:

def initialize 
    get_addresses 
end 

def log 
    Log.new 
end 
once :log 

def db 
    Db.new(log) 
end 
once :db 

def address_corrector 
    AddressCorrection.new 
end 
once :address_corrector 

def get_addresses 
    log.puts ("Querying addresses") 
    @addresses = address_corrector.correct(query_addresses(db)) 
end 

Die Reihenfolge der Initialisierung der verschiedenen voneinander abhängigen Objekten ist jetzt (1) implizit, und (2) automatisch. Auf der anderen Seite kann der Kontrollfluss undurchsichtig sein, wenn dieser Trick zu stark ist.

Answer 3

Lazy Evaluation kann sehr nützlich sein bei der Erstellung von Datenstrukturen mit effizienten amortisierten Grenzen.

Nur um ein Beispiel zu geben, hier ist eine unveränderliche Stapel Klasse:

class Stack<T> 
{ 
    public static readonly Stack<T> Empty = new Stack<T>(); 
    public T Head { get; private set; } 
    public Stack<T> Tail { get; private set; } 
    public bool IsEmpty { get; private set; } 

    private Stack(T head, Stack<T> tail) 
    { 
     this.Head = head; 
     this.Tail = tail; 
     this.IsEmpty = false; 
    } 

    private Stack() 
    { 
     this.Head = default(T); 
     this.Tail = null; 
     this.IsEmpty = true; 
    } 

    public Stack<T> AddFront(T value) 
    { 
     return new Stack<T>(value, this); 
    } 

    public Stack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new Stack<T>(value, this) 
      : new Stack<T>(this.Head, this.Tail.AddRear(value)); 
    } 
} 

Sie ein Element in der Vorderseite des Stapels in O(1) Zeit hinzufügen kann, aber es erfordert O(n) Zeit um ein Element der hinzufügen Rückseite. Da wir unsere gesamte Datenstruktur neu aufbauen müssen, ist AddRear ein monolithischer Betrieb.

Hier ist das gleiche unveränderlich Stack, aber jetzt seine träge bewertet:

class LazyStack<T> 
{ 
    public static readonly LazyStack<T> Empty = new LazyStack<T>(); 

    readonly Lazy<LazyStack<T>> innerTail; 
    public T Head { get; private set; } 
    public LazyStack<T> Tail { get { return innerTail.Value; } } 
    public bool IsEmpty { get; private set; } 

    private LazyStack(T head, Lazy<LazyStack<T>> tail) 
    { 
     this.Head = head; 
     this.innerTail = tail; 
     this.IsEmpty = false; 
    } 

    private LazyStack() 
    { 
     this.Head = default(T); 
     this.innerTail = null; 
     this.IsEmpty = true; 
    } 

    public LazyStack<T> AddFront(T value) 
    { 
     return new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)); 
    } 

    public LazyStack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)) 
      : new LazyStack<T>(this.Head, new Lazy<LazyStack<T>>(() => this.Tail.AddRear(value), true)); 
    } 
} 

Nun ist die AddRear Funktion läuft deutlich in O(1) Zeit.Wenn wir die Tail Eigenschaft zugreifen, wird es einen faulen Wert bewertet gerade genug den Kopfknoten zurück, dann stoppt sie, so dass sie nicht mehr eine monolithische Funktion.

Answer 4

Verzögerte Auswertung ist eine gemeinsame Eigenschaft von rein funktionalen Programmiersprachen Leistung zurückgewinnen ", es ist ganz einfach funktioniert, bewerten Sie nur einen Ausdruck, wenn Sie es brauchen. Betrachten wir zum Beispiel in Haskell

if x == 1 then x + 3 else x + 2 

In strikter (eifrig) Bewertung, wenn in der Tat x gleich zwei ist, dann x + 3 ausgewertet und zurückgegeben, sonst x + 2, in Haskell, nicht so etwas geschieht, x + 3 wird nur zu dem Ausdruck zusammengesetzt, zum Beispiel, sagen, ich habe:

let x = if x == 1 then x + 3 else x + 2 

Nun, das ich dann speichern Sie in einer variablen, aber was, wenn ich jemals nie jemals diese Variable verwenden, aufgrund einiger anderen conditionals hmm? Ich habe einen sehr teuren ganzzahligen Zusatz auf meiner CPU für nichts verschwendet. (okay, in der Praxis gewinnt man nicht, aber man bekommt die Idee mit größeren Ausdrücken)

Dann stellt sich die Frage, warum nicht alle Sprachen faul sind ?, naja, der einfache Grund ist der rein Funktionssprachen, Ausdrücke haben garantiert keine Nebenwirkungen. Wenn sie hätten, müssten wir sie in der richtigen Reihenfolge bewerten. Deshalb werden sie in den meisten Sprachen eifrig bewertet. In Sprachen, in denen Ausdrücke keine Nebeneffekte haben, besteht bei einer faulen Bewertung kein Risiko. Daher ist es eine logische Entscheidung, die Leistung zurückzugewinnen, die sie auf anderen Gebieten normalerweise verlieren.

Ein weiterer interessanter Nebeneffekt ist, dass if-then-else in Haskell ist wirklich eine Funktion des Typs Bool -> a -> a -> a. In Haskell bedeutet dies, dass ein Argument vom Typ Boolean verwendet wird, ein anderer vom gleichen Typ, ein anderer vom selben Typ wie der erste, und dieser Typ wird erneut zurückgegeben. Sie müssen nicht in unendliche Evaluierung verschiedener Steuer Zweige laufen, weil Werte nur ausgewertet werden, wenn sie benötigt werden, die in der Regel am Ende des Programms ist es, wenn ein großer Ausdruck komponiert worden und dann für das Endergebnis ausgewertet wird, Verwerfen Alle Dinge, die der Compiler denkt, werden für das Endergebnis nicht benötigt. Wenn ich zum Beispiel einen sehr komplexen Ausdruck selbst teile, kann er einfach durch '1' ersetzt werden, ohne beide Teile zu bewerten.

Der Unterschied in Schema zu sehen ist, die traditionell streng ausgewertet wird, aber es ist ein fauler Variante Faule Scheme genannt, in Schema (display (apply if (> x y) "x is larger than y" "x is not larger than y")) ein Fehler ist, weil if keine Funktion ist, dann ist es eine spezielle Syntax (obwohl einige Syntax sagen nicht ganz in Scheme, da es nicht notwendigerweise alle Argumente auswertet, sonst würden wir keinen Speicher mehr haben, wenn wir beispielsweise versuchen würden, eine Fakultät zu berechnen. In Lazy Scheme funktioniert das gut, weil keines dieser Argumente überhaupt ausgewertet wird, bis eine Funktion das Ergebnis wirklich benötigt, damit die Auswertung fortgesetzt werden kann, wie zum Beispiel die Anzeige.